哈希如何幫助存儲和檢索HashMap中的值？

HashMap問題在工作面試中很常見。 這是HashMaps在Java內(nèi)部如何工作的一些深入說明。

HashMap在內(nèi)部如何工作已成為幾乎所有訪談中的一個普遍問題。 幾乎每個人都知道如何使用HashMap或HashMap與Hashtable之間的區(qū)別。 但是，當問題為“ HashMap如何在內(nèi)部工作？”時，許多人會失敗。

這個問題的答案是，它基于哈希原理工作，但聽起來并不那么簡單。 哈希是一種使用算法將唯一代碼分配給變量或?qū)傩缘臋C制，從而可以輕松進行檢索。 真正的哈希機制在應用于同一對象時應始終返回相同的hashCode（）。

然后是一個問題：“哈希如何幫助存儲和檢索HashMap中的值？” 許多人會說該值將存儲在存儲桶中，并使用鍵進行檢索。 如果你認為這是有效的，那么你絕對是錯誤的。 為了證明這一點，讓我們看一下HashMap類：

/**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
     transient Entry[] table;

那么HashMap中Entry []的用途是什么？ HashMap將對象存儲為Entry實例，而不是鍵和值。

什么是入門班？

HashMap有一個稱為Entry Class的內(nèi)部類，其中包含鍵和值。 還有一個叫做next的東西，稍后你將了解。

 static class Entry<K,V> implements Map.Entry<K,V> 
 {
     final K key;
     V value;
     Entry<K,V> next;
     final int hash;
     ........
 }

你知道HashMap將Entry實例存儲在數(shù)組中，而不是作為鍵值對存儲。 為了存儲值，你將使用HashMap的put（）方法。 讓我們深入研究一下，看看它是如何工作的。

Put（）方法如何在內(nèi)部工作？
該代碼將如下所示：

public V put(K key, V value) 
{
    if (key == null)
       return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) 
    {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) 
         {
             V oldValue = e.value;
             e.value = value;
             e.recordAccess(this);
             return oldValue;
          }
     }
     modCount++;
     addEntry(hash, key, value, i);
     return null;
 }

首先，它檢查給定的密鑰是否為null。如果給定鍵為null，則它將存儲在零位置，因為null的哈希碼將為零。

然后通過調(diào)用hashcode方法將哈希碼應用于鍵.hashCode（）。為了在數(shù)組范圍內(nèi)獲得值，調(diào)用了hash（key.hashCode（）），它對哈希碼執(zhí)行一些移位操作。
indexFor（）方法用于獲取存儲Entry對象的確切位置。

接下來是最重要的部分-如果兩個不同的對象具有相同的哈希碼（例如Aa和BB將具有相同的哈希碼），它將存儲在同一存儲桶中嗎？為了解決這個問題，讓我們考慮一下數(shù)據(jù)結構中的LinkedList。它將具有“下一個”屬性，該屬性將始終指向下一個對象，與Entry類中的下一個屬性指向下一個對象的方式相同。使用這種方法，具有相同哈希碼的不同對象將彼此相鄰放置。

對于Collision，HashMap檢查下一個屬性的值。如果為null，則將Entry對象插入該位置。如果下一個屬性不為null，則它將保持循環(huán)運行，直到下一個屬性為null，然后將Entry對象存儲在那里。

如何在HashMap中防止重復密鑰？

眾所周知，HashMap不允許重復鍵，即使當我們插入具有不同值的相同鍵時，也僅返回最新值。

import java.util.HashMap;
import java.util.Map;
public class HashMapEg {
 public static void main(String[] args) {
  Map map = new HashMap();
  map.put(1, "sam");
  map.put(1, "Ian");
  map.put(1, "Scott");
  map.put(null, "asdf");
  System.out.println(map);
 }
}

對于上面的代碼，你將獲得輸出{null = asdf，1 = Scott}，因為值sam和Ian將被替換為Scott。 那么，這是怎么發(fā)生的呢？

LinkedList中的所有Entry對象將具有相同的哈希碼，但是HashMap使用equals（）。 此方法檢查相等性，因此如果key.equals（k）為true，它將替換Entry類中的值對象而不是鍵。 這樣，可以防止插入重復密鑰。

Get（）方法如何在內(nèi)部工作？

將使用put（）方法中幾乎相同的邏輯來檢索值。

public V get(Object key) 
{
    if (key == null)
       return getForNullKey();
     int hash = hash(key.hashCode());
     for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) 
     {
         Object k;
         if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
             return e.value;
     }
         return null;
 }

如果兩個鍵具有相同的Hashcode會發(fā)生什么？

此處將使用相同的沖突解決機制。 key.equals（k）將一直檢查到它為true，如果為true，則返回它的值。