Java 散列存儲
Java中散列存儲的數據結構主要是指HashSet、HashMap、LinkedHashSet、LinkedHashMap以及HashTable等。要理解Java中的散列存儲機制，那么我們必須先理解兩個方法：equals()和hashCode()。關于equals()方法以及其與“==”關系操作符的區別，我們在另一篇文章中已經說明了。而對于hashCode()，它是在Object類中定義的一個方法：
|
1
|
public native int hashCode(); |
這是一個返回int值的本地方法，在Object類中沒有被實現。這個方法主要被應用于使用散列的數據結構中，配合基于散列的集合一起正常運行，例如，在向一個容器(我們假設是HashMap)中插入一個對象時，怎樣判斷容器中是否已經存在該對象了呢？由于容器中的元素可能成千上萬，使用equals()方法依次進行比較是非常低效的。散列的價值在于速度，它將鍵保存在某處，以便能夠很快找到。存儲一組元素最快的數據結構是數組，所以使用它來存儲鍵的信息（注意是鍵的信息，而非鍵本身）。但是因為數組不能調整容量，因此就有一個問題：我們希望在Map中保存數量不確定的值，但是如果鍵的數量被數組的容量限制了，該怎么辦呢？
答案就是:數組不保存鍵本身，而是通過鍵對象生成一個數字，將其作為數組的下標，這個數字就是散列碼（hashcode），由定義在Object中的、且可能由你的類覆蓋的hashCode()方法生成。為解決數組容量被固定的問題，不同的鍵可以產生相同的下標，這種現象被稱為沖突。于是，在容器中查詢一個值的過程是：先通過hashCode()計算待插入對象的散列碼，然后使用散列碼查詢數組。對于沖突的處理，常常是通過外部鏈接，即數組并不直接保存值，而是保存值的list，然后對list中的值進行線性查詢，這部分查詢自然會比較慢。但是，如果散列函數足夠好的話，數組的每個位置就只有較少的值。因此，散列機制便可以快速地跳到數組的某個位置，只對很少的元素進行比較。這就是HashMap會如此快的原因，我們可以通過HashMap.put()方法體會到：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
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()方法必須嚴格地判斷兩個對象是否相同。
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
原文鏈接：http://blog.csdn.net/xiangwanpeng/article/details/52842629
