Java 雜湊儲存詳解及簡單範例

Java 雜湊儲存

　Java中雜湊儲存的資料結構主要是指HashSet、HashMap、LinkedHashSet、LinkedHashMap以及HashTable等。要理解Java中的雜湊儲存機制，那麼我們必須先理解兩個方法：equals()和hashCode()。關於equals()方法以及其與「==」關係運算元的區別，我們在另一篇文章中已經說明了。而對於hashCode()，它是在Object類別中定義的一個方法：

public native int hashCode();

這是一個傳回int值的本地方法，在Object類別中沒有被實作。這個方法主要被應用於使用雜湊的資料結構中，配合基於雜湊的集合一起正常運行，例如，在向一個容器(我們假設是HashMap)中插入一個物件時，怎樣判斷容器中是否已經存在該對象了呢？由於容器中的元素可能成千上萬，使用equals()方法依序進行比較是非常低效的。散列的價值在於速度，它將鍵保存在某處，以便能夠很快找到。儲存一組元素最快的資料結構是數組，所以使用它來儲存鍵的資訊（注意是鍵的訊息，而非鍵本身）。但是因為數組不能調整容量，因此就有一個問題：我們希望在Map中保存數量不確定的值，但是如果鍵的數量被數組的容量限制了，該怎麼辦呢？

　　答案就是:數組不保存鍵本身，而是透過鍵物件產生一個數字，將其作為數組的下標，這個數字就是散列碼（hashcode），由定義在Object中的、且可能由你的類別覆蓋的hashCode()方法產生。為解決數組容量被固定的問題，不同的鍵可以產生相同的下標，這種現象稱為衝突。於是，在容器中查詢一個值的過程是：先透過hashCode()計算待插入物件的雜湊碼，然後使用雜湊碼查詢陣列。對於衝突的處理，常常是透過外部鏈接，即數組並不直接保存值，而是保存值的list，然後對list中的值進行線性查詢，這部分查詢自然會比較慢。但是，如果雜湊函數夠好的話，數組的每個位置就只有較少的值。因此，雜湊機製便可以快速地跳到陣列的某個位置，只對很少的元素進行比較。這就是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;
 }

   

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

　　這裡我們需要注意到：hashCode()並不需要總是能夠傳回唯一的識別碼，但是equals()方法必須嚴格地判斷兩個物件是否相同。

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

更多Java 雜湊儲存詳情及簡單範例相關文章請關注PHP中文網！