1.什么是哈希表
- 數(shù)組：采用一段連續(xù)的存儲單元來存儲數(shù)據(jù)。通過指定下標(biāo)查找，速度很快；通過給定值查找，需要遍歷數(shù)組。對于有序數(shù)組，可以優(yōu)化查找方法，比如二分法等；對于插入刪除操作，就會設(shè)計增容，數(shù)組元素平移等操作，效率偏低。
- 鏈表：對于新增、刪除的操作在找到元素位置后只需要處理節(jié)點(diǎn)間的引用即可，效率比較高；但是查找需要遍歷鏈表。
-
哈希表：哈希表在添加，刪除，查找上的性能十分高，在不考慮哈希沖突的情況下，僅需要通過hash值做一次定位就可以完成。數(shù)據(jù)結(jié)構(gòu)的物理存儲結(jié)構(gòu)只有兩種：順序存儲結(jié)構(gòu)跟鏈?zhǔn)酱鎯Y(jié)構(gòu)。哈希表通過hash值定位存儲地址，這種特性跟數(shù)組是一樣的，哈希表的主干就是數(shù)組。
1600925026221.jpg - 哈希沖突：一般情況不同元素計算出的hash值是不同的，所以存儲地址也是不同的，每個地址對應(yīng)著一個元素，但是完事沒有完美，如果有元素計算出的hash值相同，那么他們的存儲地址也會相同，這就產(chǎn)生了哈希沖突，這也是不可避免的，因為哈希表主干就是數(shù)組，一個連續(xù)的長度固定的存儲空間，那么就不能完全保證存儲地址絕對不沖突，那么為了解決哈希沖突就出現(xiàn)了數(shù)組+鏈表的方式，HashMap就是采用這個方式。
2.HashMap的實現(xiàn)原理
HashMap的主干是一個Entry數(shù)組，每一個Entry里面包含了key-value鍵值對，hash值，還有鏈表的下一個Entry
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;//存儲指向下一個Entry的引用，單鏈表結(jié)構(gòu)
int hash;//對key的hashcode值進(jìn)行hash運(yùn)算后得到的值，存儲在Entry，避免重復(fù)計算
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
}
因而HashMap的結(jié)構(gòu)如下：
HashMap由數(shù)組+鏈表組成，數(shù)組是主體，鏈表是為了解決哈希沖突。如果HashMap中沒有鏈表，那么查找添加的速度就會非?？欤蝗绻嬖阪湵砭托枰闅v整個鏈表，如果key存在就會覆蓋，如果不存在就會復(fù)雜一點(diǎn)，需要判斷鏈表是否是紅黑樹，如果是紅黑樹就直接插入，如果不是就會遍歷鏈表準(zhǔn)備插入，這時候還要再判斷鏈表長度是不是大于8，如果是的話，鏈表會轉(zhuǎn)為紅黑樹，如果不是就會插入鏈表，當(dāng)然最后還需要看是否需要擴(kuò)容。
（HashMap的默認(rèn)初始長度是16，負(fù)載因子是0.75，當(dāng)超過閾值就會出發(fā)擴(kuò)容，newSize = oldSize*2，size一定是2的n次冪）
3.HashMap的數(shù)組長度一定是2的次冪
為什么要設(shè)計HashMap的數(shù)組長度一定是2的次冪呢，那這個我們就需要看一下HashMap是如何去計算出元素存儲位置的了
static int indexFor(int h, int length) {
return h & (length-1);
}
h是通過元素的hashCode通過計算得出了的hash值，length是Size容量
舉個例子，當(dāng)前容量是16，h計算結(jié)果是11，轉(zhuǎn)二進(jìn)制計算
01011 & 01111 = 01011 = 11
這個下標(biāo)就是11了，這就是當(dāng)前元素存儲位置。
然后假設(shè)這個HashMap發(fā)生了一次擴(kuò)容，那么當(dāng)前容量就是32，h還是11，我們再次計算元素存儲位置
01011 & 11111 = 01011 = 11
這里是不是發(fā)現(xiàn)擴(kuò)容后沒有影響到原來的元素的下標(biāo)，但是如果不是Size不是2的次冪會怎么樣呢，我們也舉個例子，Size=30，h =11
01011 & 11101 = 01001 = 9
擴(kuò)容后存儲位置變了，第一個原因就有了，可以減少擴(kuò)容機(jī)制發(fā)生時老數(shù)組的數(shù)據(jù)位置變換，而且length-1低位都是1的話也可以讓索引更加的均勻，有利于散列良好。
然后我們再來看，舉例：
010101 & 111111 = 010101
010111 & 111111 = 010111
010101 $ 111101 = 010101
010111 $ 111101 = 010101
可以看到低位全是1可以保證不同數(shù)據(jù)計算結(jié)果不通，但是第二種卻不行，這樣一來哈希沖突的幾率就會增加，鏈表數(shù)量也會變多，還會讓散列不均勻浪費(fèi)數(shù)組位置，查詢效率還會降低。
4.重寫equals方法需同時重寫hashCode方法
到了這里HashMap基本分析結(jié)束了，那么也就可以知道為何說重寫equals方法需同時重寫hashCode方法了，我們可以舉個列子：
public class A{
int id;
String name;
public A(int id, String name){
this.id = id;
this.name = name;
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()){
return false;
}
A a = (A) o;
//如果id相等我們就認(rèn)為兩個對象相等
return this.idCard == person.idCard;
}
}
這種情況下會怎樣呢，比如A1對象id是1，name是a1；A2對象id是1，name是a2，這兩個對象id是相等的，在業(yè)務(wù)場景上我們就認(rèn)為兩個對象就是相等的，那么我們將他們保存如HashMap，現(xiàn)存入A1再存入A2，那么我們想要的是什么，例如一個人的身份證是1，開始他叫a1，后來改名了叫a2了，我們在存入的時候肯定是希望覆蓋掉原來的信息，但是因為沒有重寫hashCode方法，他們的hashCode值就不一樣，得到的hash值就不一樣，最后地址下標(biāo)也就不一樣，那么對于HashMap來講他們就是兩個不同的對象，與業(yè)務(wù)不符合。這就是為什么重寫equals方法需同時重寫hashCode方法的原因了。
