前言

最近在讀Java核心技術(shù) 卷1，和大家分享一下集合篇有關(guān)散列表的感悟。

正文節(jié)選

散列表為每個(gè)對(duì)象計(jì)算一個(gè)整數(shù)，稱為散列碼（hashcode)。散列碼是由對(duì)象的實(shí)例域產(chǎn)生的一個(gè)整數(shù)。更準(zhǔn)確地說，具有不同數(shù)據(jù)域的對(duì)象將產(chǎn)生不同的散列碼。

在 Java 中，散列表用鏈表數(shù)組實(shí)現(xiàn)。每個(gè)列表被稱為桶（bucket) (參看圖 9-10)。要想査找表中對(duì)象的位置，就要先計(jì)算它的散列碼，然后與桶的總數(shù)取余，所得到的結(jié)果就是保存這個(gè)元素的桶的索引。
例如，如果某個(gè)對(duì)象的散列碼為76268, 并且有128個(gè)桶，對(duì)象應(yīng)該保存在第108號(hào)桶中（76268除以128余108)。或許會(huì)很幸運(yùn)，在這個(gè)桶中沒有其他元素，此時(shí)將元素直接插人到桶中就可以了。

當(dāng)然，有時(shí)候會(huì)遇到桶被占滿的情況，這也是不可避免的。這種現(xiàn)象被稱為散列沖突（hash collision)。這時(shí)，需要用新對(duì)象與桶中的所有對(duì)象進(jìn)行比較，査看這個(gè)對(duì)象是否已經(jīng)存在。如果散列碼是合理且隨機(jī)分布的，桶的數(shù)目也足夠大，需要比較的次數(shù)就會(huì)很少。

如果想更多地控制散列表的運(yùn)行性能，就要指定一個(gè)初始的桶數(shù)。桶數(shù)是指用于收集具有相同散列值的桶的數(shù)目。如果要插入到散列表中的元素太多，就會(huì)增加沖突的可能性，降低運(yùn)行性能。
如果大致知道最終會(huì)有多少個(gè)元素要插人到散列表中，就可以設(shè)置桶數(shù)。通常，將桶數(shù)設(shè)置為預(yù)計(jì)元素個(gè)數(shù)的75% ~ 150%。有些研究人員認(rèn)為：盡管還沒有確鑿的證據(jù)，但最好將桶數(shù)設(shè)置為一個(gè)素?cái)?shù)，以防鍵的集聚。
標(biāo)準(zhǔn)類庫使用的桶數(shù)是2的冪，默認(rèn)值為16(為表大小提供的任何值都將被自動(dòng)地轉(zhuǎn)換為2的下一個(gè)冪)。當(dāng)然，并不是總能夠知道需要存儲(chǔ)多少個(gè)元素的， 也有可能最初的估計(jì)過低。如果散列表太滿，就需要再散列（rehashed)。如果要對(duì)散列表再散列， 就需要?jiǎng)?chuàng)建一個(gè)桶數(shù)更多的表，并將所有元素插入到這個(gè)新表中，然后丟棄原來的表。
裝填因子（load factor) 決定何時(shí)對(duì)散列表進(jìn)行再散列。例如，如果裝填因子為0.75 (默認(rèn)值)而表中超過75%的位置已經(jīng)填人元素， 這個(gè)表就會(huì)用雙倍的桶數(shù)自動(dòng)地進(jìn)行再散列。對(duì)于大多數(shù)應(yīng)用程序來說， 裝填因子為0.75 是比較合理的。

思考

原文中提到了幾個(gè)關(guān)鍵詞

性能，桶數(shù)，裝填因子

還提到了一個(gè)前提條件，也就是我們能大約估計(jì)出散列表的大小，或者不妨更大膽一點(diǎn)，這個(gè)散列表就是固定的，那我們就可以從桶數(shù)和裝填因子下手，對(duì)性能進(jìn)行優(yōu)化，防止觸發(fā)不必要的擴(kuò)容機(jī)制。

舉個(gè)栗子，我們現(xiàn)在有10個(gè)桶要插入散列表里，我們應(yīng)該如何選擇桶數(shù)和裝填因子？

// 一個(gè)存放10個(gè)水果的列表，現(xiàn)在要以中英文名放入散列表里
List<String> fruits = Arrays.asList("蘋果", "橘子", "梨子", "葡萄", "香蕉", "西瓜", "檸檬", "橙子", "芭樂", "藍(lán)莓");

是選擇默認(rèn)的大小嗎？

HashMap<String, String> fruitsMap = new HashMap<>();

讓我們計(jì)算一下桶數(shù)*裝填因子 = 16 * 0.75 = 12 > 10。
剛好滿足要求，不會(huì)觸發(fā)擴(kuò)容！
但是我們的前提是固定的桶數(shù)！請(qǐng)注意上文代碼的Arrays.asList（），創(chuàng)建的是一個(gè)不可變的列表，那么我們多出的16 - 10 = 6個(gè)空間不就浪費(fèi)了嗎？

現(xiàn)在讓我們來重新考慮一下這個(gè)設(shè)計(jì)，我們能不能把裝填因子設(shè)置為1呢？也就是當(dāng)桶滿了才觸發(fā)擴(kuò)容，正因?yàn)槲覀兊耐皵?shù)不變，所以當(dāng)我們?cè)O(shè)置桶數(shù)為10 + 1 = 11時(shí)，就永遠(yuǎn)不會(huì)觸發(fā)擴(kuò)容機(jī)制，而且11正好是一個(gè)素?cái)?shù)，剛好滿足了原文中帶有不確定性的小建議。

后話

在實(shí)際開發(fā)過程中，可以不必過于苛求這種細(xì)節(jié)，但是在提交前代碼審視的時(shí)候，就可以對(duì)這些使用的數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化，精益求精。