圖5-1是完美情況的一個典型。在這個例子中，john散列到3，phil散列到4，dave散列到6，mary散列到7。

這就是散列的基本想法。剩下的問題就是要選擇一個函數(shù)，決定當(dāng)兩個關(guān)鍵字散列到同一個值的時候（這叫作沖突(collision))應(yīng)該做什么以及如何確定散列表的大小。

散列函數(shù)

這個散列函數(shù)利用到事實：允許溢出。這可能會引進負的數(shù)，因此在末尾有附加的測試。圖5-4所描述的散列函數(shù)就表的分布而言未必是最好的，但確實具有極其簡單的優(yōu)點而且速度也很快。如果關(guān)鍵字特別長，那么該散列函數(shù)計算起來將會花費過多的時間。在這種情況下通常的經(jīng)驗是不使用所有的字符。此時關(guān)鍵字的長度和性質(zhì)將影響選擇。例如，關(guān)鍵字可能是完整的街道地址，散列函數(shù)可以包括街道地址的幾個字符，也許還有城市名和郵政編碼的幾個字符。有些程序設(shè)計人員通過只使用奇數(shù)位置上的字符來實現(xiàn)他們的散列函數(shù)，這里有這么一層想法：用計算散列函數(shù)節(jié)省下的時間來補償由此產(chǎn)生的對均勻地分布的函數(shù)的輕微干擾。

解決collision哈希沖突（碰撞）

剩下的主要編程細節(jié)是解決沖突的消除問題。如果當(dāng)一個元素被插入時與一個已經(jīng)插入的元素散列到相同的值，那么就產(chǎn)生一個沖突，這個沖突需要消除。解決這種沖突的方法有幾種，我們將討論其中最簡單的兩種：分離鏈接法和開放定址法。

分離鏈接法(separate chaining)

分離鏈接法(separate chaining)

解決沖突的第一種方法通常叫作分離鏈接法(separate chaining),其做法是將散列到同一個值的所有元素保留到一個表中。我們可以使用標準庫表的實現(xiàn)方法。如果空間很緊，則更可取的方法是避免使用它們（因為這些表是雙向鏈接的并且浪費空間）。本節(jié)我們假設(shè)關(guān)鍵字是前10個完全平方數(shù)并設(shè)散列函數(shù)就是hash(x)=xmod10(表的大小不是素數(shù)，用在這里是為了簡單)。

探測散列表(probing hash table)

探測散列表(probing hash table)

分離鏈接散列算法的缺點是使用一些鏈表。由于給新單元分配地址需要時間（特別是在其他語言中)，因此這就導(dǎo)致算法的速度有些減慢，同時算法實際上還要求對第二種數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)。另有一種不用鏈表解決沖突的方法是嘗試另外一些單元，直到找出空的單元為止。更常見的是，單元h（x),h,(x),h2（x),…相繼被試選，其中h:(x)=(hash(x)+f(i)mod
TableSize,且f(0)=0。函數(shù)f是沖突解決方法。因為所有的數(shù)據(jù)都要置入表內(nèi)，所以這種解決方案所需要的表要比分離鏈接散列的表大。一般說來，對于不使用分離鏈接的散列表來說，其裝填因子應(yīng)該低于入=0.5。我們把這樣的表叫作探測散列表(probing hash table)?，F(xiàn)在我們就來考察三種通常的沖突解決方案。

第一個沖突在插人關(guān)鍵字49時產(chǎn)生；它被放入下一個空閑地址，即地址0，該地址是開放的。關(guān)鍵字58先與18沖突，再與89沖突，然后又和49沖突，試選三次之后才找到一個空單元。對69的沖突用類似的方法處理。只要表足夠大，總能夠找到一個自由單元，但是如此花費的時間是相當(dāng)多的。更糟的是，即使表相對較空，這樣占據(jù)的單元也會開始形成一些區(qū)塊，其結(jié)果稱為一次聚集(primary clustering),就是說，散列到區(qū)塊中的任何關(guān)鍵字都需要多次試選單元才能夠解決沖突，然后該關(guān)鍵字被添加到相應(yīng)的區(qū)塊中。

平方探針

平方探測是消除線性探測中一次聚集問題的沖突解決方法。平方探測就是沖突函數(shù)為二次的探測方法。流行的選擇是f(i)=i**2。圖5-13顯示與前面線性探測例子相同的輸人使用該沖突函數(shù)所得到的散列表。

當(dāng)49與89沖突時，其下一個位置為下一個單元，該單元是空的，因此49就被放在那里。此后，58在位置8處產(chǎn)生沖突，其后相鄰的單元經(jīng)探測得知發(fā)生了另外的沖突。下一個探測的單元在距位置8為2=4遠處，這個單元是個空單元。因此，關(guān)鍵字58就放在單元2處。對于關(guān)鍵字69，處理的過程也一樣。

雖然平方探測排除了一次聚集，但是散列到同一位置上的那些元素將探測相同的備選單元。這叫作二次聚集(secondary clustering)。二次聚集是理論上的一個小缺憾。模擬結(jié)果指出，對每次查找，它一般要引起另外的少于一半的探測。下面的技術(shù)將會排除這個缺撼，不過這要付出計算一個附加的散列函數(shù)的代價。

雙散列(double hashing)

我們將要考察的最后一個沖突解決方法是雙散列(double hashing)。對于雙散列，一種流行的選擇是f(i)=i·hash2(x)。這個公式是說，我們將第二個散列函數(shù)應(yīng)用到x并在距離hash2(x),2hash(x),…等處探測。hash2(x)選擇得不好將會是災(zāi)難性的。例如，若把99插入到前面例子中的輸入中去，則通常的選擇hash2（x)=xmod9將不起作用。因此，函數(shù)一定不要算得0值。另外，保證所有的單元都能被探測到也是很重要的（但在下面的例子中這是不可能的，因為表的大小不是素數(shù))。諸如hash2(x)=R-(x mod R)這樣的函數(shù)將起到良好的作用，其中R為小于TableSize的素數(shù)。如果我們選擇R=7,則圖5-18顯示插入與前面相同的一些關(guān)鍵字的結(jié)果。

第一個沖突發(fā)生在49被插入的時候。hash2(49)=7-0=7,故49被插入到位置6。hash2(58)7-2=5,于是58被插人到位置3。最后，69產(chǎn)生沖突，從而被插入到距離為hash2(69)=7-6=1遠的地方。如果我們試圖將60插入到位置0處，那么就會產(chǎn)生一個沖突。由于hash2（60)=74=3,因此我們嘗試位置3、6、9，然后是2，直到找出一個空的單元。一般是有可能發(fā)現(xiàn)某個壞

Java標準庫中的散列表

標準庫包括Set和Map的散列表的實現(xiàn)，即HashSet類和HashMap類。HashSet中的項（或HashSet中的關(guān)鍵字）必須提供equals方法和hashCode方法，如較早我們在節(jié)5.3所描述的那樣。HashSet和HashMap通常是用分離鏈接散列實現(xiàn)的。

如果這些表項是否可以依有序方式查看這一點并不重要，那么這些類可以使用。例如，在4.8節(jié)的單詞變換例子中，存在三種映射：

1.其中關(guān)鍵字為單詞長度(word length),而關(guān)鍵字的值是長為該單詞長度的所有單詞的集合。

2.關(guān)鍵字是一個代表(representative),而關(guān)鍵字的值是具有該代表的所有單詞的集合。

3.關(guān)鍵字是一個單詞(wod),而關(guān)鍵字的值是與該單詞只有一個字母不同的所有單詞的集合。

因為單詞長度被處理的順序并不重要，所以第1個映射可以是HashMap。而由于第2個映射建立以后甚至不需要代表，因此第2個映射也可以是HashMap。第3個映射還可以是HashMap,除非我們想要printHighChangeables依字母順序列出單詞的子集（這些單詞可以被變換成許多其他單詞)。

HashMap的性能常常優(yōu)于TreeMap的性能，不過不按這兩種方式編寫代碼很難有把握肯定。因此，在HashMap或TreeMap可以接受的情況下，更可取的方法是：使用接口類型Map進行變量的聲明，然后，將TreeMap的實例變成HashMap的實例并進行計時測試。

在Java中，能夠被合理地插人到一個HashSet中去或是所謂關(guān)鍵字被插入到HashMap中去的那些庫類型已經(jīng)被定義了equals和hashCode方法。

特別是String類中有一個hashCode方法。

總結(jié)

1.散列表，key，散列函數(shù)；
2.哈希沖突的解決；
3.string中的hashCode;

到了這里，關(guān)于Java學(xué)數(shù)據(jù)結(jié)構(gòu)（4）——散列表Hash table & 散列函數(shù) & 哈希沖突的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！