一般想法
理想的散列表數(shù)據(jù)結(jié)構(gòu)只不過是一個包含有關(guān)鍵字的具有固定大小的數(shù)組贞岭。
每個關(guān)鍵字被映射到從~
這個范圍中的某個數(shù)又憨，并且被放到合適的單元中袜炕。這個映射就叫做散列函數(shù)。理想情況下它應(yīng)該計(jì)算起來簡單献酗，并且應(yīng)該保證任何兩個不同的關(guān)鍵字映射到不同的單元寝受。不過這是不可能的，因?yàn)閱卧臄?shù)目是有限的罕偎，而關(guān)鍵字實(shí)際上是用不完的羡蛾。因此，我們尋找一個散列函數(shù)锨亏，該函數(shù)要在單元間均勻地分配關(guān)鍵字痴怨。
這就是散列的基本想法。剩下的問題就是要選擇一個函數(shù)器予，決定當(dāng)兩個關(guān)鍵字散列到同一個值的時候（這就叫做沖突）浪藻，應(yīng)該做什么以及如何確定散列表的大小。
散列函數(shù)（Hash函數(shù)）
JDK中String的hashCode函數(shù)：
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value; // value即String的字符數(shù)組
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
散列函數(shù)選擇完成之后爱葵，剩下的主要編程細(xì)節(jié)就是如何解決沖突的消除問題。如果當(dāng)一個元素被插入時與一個已經(jīng)插入的元素散列到相同的值反浓，那么就會產(chǎn)生一個沖突萌丈。解決這種沖突的方法有幾種，下面討論其中最簡單的兩種：分離鏈接法和開放定址法雷则。
分離鏈接法
其做法是將散列到同一個值的所有元素保留到一個表中辆雾。
分離鏈接法的實(shí)現(xiàn)：
除鏈表外，很多方案都可以解決沖突現(xiàn)象：一顆二叉查找樹或者另一個散列表等都將勝任這個工作月劈。但是度迂，我們期望散列表是大的并且散列函數(shù)是好的，那么所有的鏈表都應(yīng)該是短的猜揪，從而任何復(fù)雜的嘗試就都不值得考慮了惭墓。
因?yàn)橐淮尾檎业臅r間是計(jì)算散列函數(shù)值（對應(yīng)數(shù)組下標(biāo)）所需要的常數(shù)時間加上遍歷鏈表所用的時間，所以我們希望鏈表盡可能的短而姐。通過定義散列表的裝填因子以及適當(dāng)時候執(zhí)行rehash函數(shù)腊凶，可以保證鏈表盡可能的短。
我們定義散列表的裝填因子（load factor）為：散列表中元素的個數(shù)與該表大小的比拴念。分離鏈接法中的一般法則是使得表的大小與預(yù)料的元素個數(shù)大致相等（即讓
）钧萍。在上面的程序中，可以看出對應(yīng)的裝填因子大小為1：
if(++currentSize > theLists.length)
rehash();
如果裝填因子超過1丈莺，那么我們將調(diào)用rehash函數(shù)擴(kuò)大散列表的大谢蟆（即程序中數(shù)組的大小）缔俄。
不用鏈表的散列表（開放地址法）
線性探測法
平方探測法
雙散列
再散列（rehash）
分離鏈接表的再散列：
探測散列表的再散列：
標(biāo)準(zhǔn)庫中的散列表
HashMap的工作原理：
https://blog.csdn.net/suifeng629/article/details/82179996
https://zhuanlan.zhihu.com/p/28501879
ConcurrentHashMap底層實(shí)現(xiàn)原理：
http://www.reibang.com/p/865c813f2726
最壞情形下O(1)訪問的散列表
- 完美散列
- 布谷鳥散列
- 跳房子散列
