Java 散列存儲

　Java中散列存儲的數(shù)據(jù)結(jié)構(gòu)主要是指HashSet、HashMap、LinkedHashSet、LinkedHashMap以及HashTable等。要理解Java中的散列存儲機制，那么我們必須先理解兩個方法：equals()和hashCode()。關(guān)于equals()方法以及其與“==”關(guān)系操作符的區(qū)別，我們在另一篇文章中已經(jīng)說明了。而對于hashCode()，它是在Object類中定義的一個方法：

public native int hashCode();

這是一個返回int值的本地方法，在Object類中沒有被實現(xiàn)。這個方法主要被應用于使用散列的數(shù)據(jù)結(jié)構(gòu)中，配合基于散列的集合一起正常運行，例如，在向一個容器(我們假設(shè)是HashMap)中插入一個對象時，怎樣判斷容器中是否已經(jīng)存在該對象了呢？由于容器中的元素可能成千上萬，使用equals()方法依次進行比較是非常低效的。散列的價值在于速度，它將鍵保存在某處，以便能夠很快找到。存儲一組元素最快的數(shù)據(jù)結(jié)構(gòu)是數(shù)組，所以使用它來存儲鍵的信息（注意是鍵的信息，而非鍵本身）。但是因為數(shù)組不能調(diào)整容量，因此就有一個問題：我們希望在Map中保存數(shù)量不確定的值，但是如果鍵的數(shù)量被數(shù)組的容量限制了，該怎么辦呢？

　　答案就是:數(shù)組不保存鍵本身，而是通過鍵對象生成一個數(shù)字，將其作為數(shù)組的下標，這個數(shù)字就是散列碼（hashcode），由定義在Object中的、且可能由你的類覆蓋的hashCode()方法生成。為解決數(shù)組容量被固定的問題，不同的鍵可以產(chǎn)生相同的下標，這種現(xiàn)象被稱為沖突。于是，在容器中查詢一個值的過程是：先通過hashCode()計算待插入對象的散列碼，然后使用散列碼查詢數(shù)組。對于沖突的處理，常常是通過外部鏈接，即數(shù)組并不直接保存值，而是保存值的list，然后對list中的值進行線性查詢，這部分查詢自然會比較慢。但是，如果散列函數(shù)足夠好的話，數(shù)組的每個位置就只有較少的值。因此，散列機制便可以快速地跳到數(shù)組的某個位置，只對很少的元素進行比較。這就是HashMap會如此快的原因，我們可以通過HashMap.put()方法體會到：

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;
 }

其主要思想便是：在鍵不為空時，根據(jù)鍵對象獲取到散列碼hash，然后通過散列碼得到數(shù)組的下標i。在table[i]所表示的list中進行迭代，通過equals()判斷該鍵是否存在，如果存在，則用新的值更新舊的值，返回舊的值；否則將新的鍵值對添加到HashMap中。從這里可以看出，hashCode方法的存在是為了減少equals方法的調(diào)用次數(shù)，從而提高程序效率。

　　這里我們需要注意到：hashCode()并不需要總是能夠返回唯一的標識碼，但是equals()方法必須嚴格地判斷兩個對象是否相同。

感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！

最新評論