Java容器HashMap與HashTable詳解

更新時間：2017年04月14日 09:16:02 作者：siqq

本文主要介紹HashMap 和 Hashtable的工作原理和使用方法，有興趣的朋友可以參考

1、HashMap

HashMap繼承抽象類AbstractMap，實現(xiàn)接口Map、Cloneable, Serializable接口。HashMap是一種以鍵值對存儲數(shù)據(jù)的容器，

由數(shù)組+鏈表組成，其中key和value都可以為空，key的值唯一。HashMap是非線程安全的，對于鍵值對<Key,Value>，

HashMap內(nèi)部會將其封裝成一個對應(yīng)的Entry<Key,Value>對象。HashMap的存儲空間大小是可以動態(tài)改變的：

存儲過程

每個對象都有一個對應(yīng)的HashCode值，根據(jù)HashCode值，調(diào)用hash函數(shù)，計算出一個hash值，根據(jù)該hash值調(diào)用indexFor函數(shù)，計算出在table中的存儲位置，如果該位置已經(jīng)有值，則存儲在該位置對應(yīng)的桶中。

 public V put(K key, V value) {
  if (table == EMPTY_TABLE) {
   inflateTable(threshold);
  }
  if (key == null)
   return putForNullKey(value);
  int hash = hash(key);
  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;
 }
 public final int hash(Object k) {
  int h = hashSeed;
  if (0 != h && k instanceof String) {
   return sun.misc.Hashing.stringHash32((String) k);
  }
  h ^= k.hashCode();
  // This function ensures that hashCodes that differ only by
  // constant multiples at each bit position have a bounded
  // number of collisions (approximately 8 at default load factor).
  h ^= (h >>> 20) ^ (h >>> 12);
  return h ^ (h >>> 7) ^ (h >>> 4);
 }
 public final int hashCode() {
  return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue()) 
 }
 static int indexFor(int h, int length) {
  // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
  return h & (length-1);
 }

獲取值

首先根據(jù)key的HashCode碼計算出hash值，然后調(diào)用indexFor函數(shù)計算該entry對象在table中的存儲位置，遍歷該位置對應(yīng)桶中存儲的entry對象，如果存在對象的hash值和key與要查找的相同，則返回該對象。

 public final Entry<K,V> getEntry(Object key) {
  if (size == 0) {
   return null;
  }
  int hash = (key == null) ? 0 : hash(key);
  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 != null && key.equals(k))))
    return e;
  }
  return null;
 }

兩map相等的判斷

 public final boolean equals(Object o) {
   if (!(o instanceof Map.Entry))
    return false;
   Map.Entry e = (Map.Entry)o;
   Object k1 = getKey();
   Object k2 = e.getKey();
   if (k1 == k2 || (k1 != null && k1.equals(k2))) {
    Object v1 = getValue();
    Object v2 = e.getValue();
    if (v1 == v2 || (v1 != null && v1.equals(v2)))
     return true;
   }
   return false;
  }

自反性：對于任何非空引用值 x，x.equals(x) 都應(yīng)返回 true。

對稱性：對于任何非空引用值 x 和 y，當(dāng)且僅當(dāng) y.equals(x) 返回 true 時，x.equals(y) 才應(yīng)返回 true。

傳遞性：對于任何非空引用值 x、y 和 z，如果 x.equals(y) 返回 true，并且 y.equals(z) 返回

true，那么 x.equals(z) 應(yīng)返回 true。

一致性：對于任何非空引用值 x 和 y，多次調(diào)用 x.equals(y) 始終返回 true 或始終返回 false，前提是對象上

equals 比較中所用的信息沒有被修改。

對于任何非空引用值 x，x.equals(null) 都應(yīng)返回 false。

存儲空間動態(tài)分配

HashMap的桶數(shù)目，即Entry[] table數(shù)組的長度，由于數(shù)組是內(nèi)存中連續(xù)的存儲單元，它的空間代價是很大的，但是它的隨機(jī)存取的速度是Java集合中最快的。我們增大桶的數(shù)量，而減少Entry<Key,Value>鏈表的長度，來提高從HashMap中讀取數(shù)據(jù)的速度。這是典型的拿空間換時間的策略。

但是我們不能剛開始就給HashMap分配過多的桶(即Entry[] table 數(shù)組起始不能太大)，這是因為數(shù)組是連續(xù)的內(nèi)存空間，它的創(chuàng)建代價很大，況且我們不能確定給HashMap分配這么大的空間，它實際到底能夠用多少，為了解決這一個問題，HashMap采用了根據(jù)實際的情況，動態(tài)地分配桶的數(shù)量。

要動態(tài)分配桶的數(shù)量，這就要求要有一個權(quán)衡的策略了，HashMap的權(quán)衡策略是這樣的：

如果 HashMap的大小 > HashMap的容量(即Entry[] table的大小)*加載因子(經(jīng)驗值0.75)

 則 HashMap中的Entry[] table 的容量擴(kuò)充為當(dāng)前的一倍；然后重新將以前桶中的`Entry<Key,Value>`鏈表重新分配到各個桶中

上述的 HashMap的容量(即Entry[] table的大小) * 加載因子(經(jīng)驗值0.75)就是所謂的閥值(threshold)。

2、HashTable

HashTable繼承Dictionary類，實現(xiàn)Map, Cloneable,Serializable接口，不允許key為空，采用拉鏈法實現(xiàn)與HashMap類似。

HashTable是線程安全的（但是在Collections類中存在一個靜態(tài)方法：synchronizedMap()，該方法創(chuàng)建了一個線程安全的Map對象，通過該方法我們可以同步訪問潛在的HashMap，對整個map對象加鎖。CurrentHashMap是線程安全的，并且只對桶加鎖，不會影響map對象上其它桶的操作）。

希望本文對各位朋友有所幫助

您可能感興趣的文章: