Java 散列存儲(chǔ)

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

public native int hashCode();

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

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

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

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

　　這里我們需要注意到：hashCode()并不需要總是能夠返回唯一的標(biāo)識(shí)碼，但是equals()方法必須嚴(yán)格地判斷兩個(gè)對(duì)象是否相同。

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

最新評(píng)論