4.4 1.8 hash方法
作者：诺婢海客7380095號
鏈接：https://www.nowcoder.com/discuss/151172?source_id=profile_create&channel=-2
來源：牛客網(wǎng)
Java 8中的散列值優(yōu)化函數(shù)
只做一次16位右位移異或
key.hashCode()函數(shù)調(diào)用的是key鍵值類型自帶的哈希函數(shù)，返回int型散列值
理論上散列值是一個int型听想，如果直接拿散列值作為下標訪問HashMap主數(shù)組的話，考慮到2進制32位帶符號的int范圍大概40億的映射空間混移。只要哈希函數(shù)映射得比較均勻松散倔毙，一般應用是很難出現(xiàn)碰撞的。
但問題是一個40億長度的數(shù)組评肆，內(nèi)存是放不下的.HashMap擴容之前的數(shù)組初始大小才16,所以這個散列值是不能直接拿來用的.
用之前還要先做對數(shù)組的長度取模運算债查，得到的余數(shù)才能用來訪問數(shù)組下標
源碼中模運算就是把散列值和數(shù)組長度做一個"與"操作，
這也正好解釋了為什么HashMap的數(shù)組長度要取2的整次冪
因為這樣（數(shù)組長度-1）正好相當于一個“低位掩碼”
“與”操作的結(jié)果就是散列值的高位全部歸零瓜挽，只保留低位值盹廷，用來做數(shù)組下標訪問
以初始長度16為例，16-1=15
2進制表示是00000000 00000000 00001111
和某散列值做“與”操作如下久橙，結(jié)果就是截取了最低的四位值
但這時候問題就來了,這樣就算我的散列值分布再松散,要是只取最后幾位的話,碰撞也會很嚴重
這時候“擾動函數(shù)”的價值就體現(xiàn)出來了
右位移16位俄占，正好是32位一半，自己的高半?yún)^(qū)和低半?yún)^(qū)做異或淆衷，就是為了混合原始hashCode的高位和低位缸榄，以此來加大低位的隨機性
而且混合后的低位摻雜了高位的部分特征，這樣高位的信息也被變相保留下來祝拯。
index的運算規(guī)則是
e.hash & (newCap - 1)
newCap是2的冪,所以newCap - 1的高位全0
若e.hash值只用自身的hashcode,index只會和e.hash的低位做&操作.這樣一來,index的值就只有低位參與運算,高位毫無存在感,從而會帶來哈希沖突的風險
所以在計算key的hashCode時,用其自身hashCode與其低16位做異或操作
這也就讓高位參與到index的計算中來了,即降低了哈希沖突的風險又不會帶來太大的性能問題
三甚带、為何HashMap的數(shù)組長度一定是2的次冪？
我們來繼續(xù)看上面提到的resize方法
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
如果數(shù)組進行擴容，數(shù)組長度發(fā)生變化，而存儲位置 index = h&(length-1),index也可能會發(fā)生變化，需要重新計算index鹰祸，我們先來看看transfer這個方法
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
//for循環(huán)中的代碼，逐個遍歷鏈表籽前，重新計算索引位置，將老數(shù)組數(shù)據(jù)復制到新數(shù)組中去（數(shù)組不存儲實際數(shù)據(jù)腊瑟，所以僅僅是拷貝引用而已）
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
//將當前entry的next鏈指向新的索引位置,newTable[i]有可能為空聚假，有可能也是個entry鏈，如果是entry鏈闰非，直接在鏈表頭部插入膘格。
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
這個方法將老數(shù)組中的數(shù)據(jù)逐個鏈表地遍歷，扔到新的擴容后的數(shù)組中财松，我們的數(shù)組索引位置的計算是通過 對key值的hashcode進行hash擾亂運算后瘪贱，再通過和 length-1進行位運算得到最終數(shù)組索引位置。
HashMap的數(shù)組長度一定保持2的次冪辆毡，比如16的二進制表示為 10000菜秦，那么length-1就是15，二進制為01111舶掖，同理擴容后的數(shù)組長度為32球昨，二進制表示為100000，length-1為31眨攘，二進制表示為011111主慰。從下圖可以我們也能看到這樣會保證低位全為1，而擴容后只有一位差異鲫售，也就是多出了最左位的1共螺，這樣在通過 h&(length-1)的時候，只要h對應的最左邊的那一個差異位為0情竹，就能保證得到的新的數(shù)組索引和老數(shù)組索引一致(大大減少了之前已經(jīng)散列良好的老數(shù)組的數(shù)據(jù)位置重新調(diào)換)藐不，個人理解。
還有秦效，數(shù)組長度保持2的次冪雏蛮，length-1的低位都為1，會使得獲得的數(shù)組索引index更加均勻
我們看到棉安，上面的&運算底扳，高位是不會對結(jié)果產(chǎn)生影響的（hash函數(shù)采用各種位運算可能也是為了使得低位更加散列），我們只關(guān)注低位bit贡耽，如果低位全部為1，那么對于h低位部分來說，任何一位的變化都會對結(jié)果產(chǎn)生影響蒲赂，也就是說阱冶，要得到index=21這個存儲位置，h的低位只有這一種組合滥嘴。這也是數(shù)組長度設計為必須為2的次冪的原因木蹬。
如果不是2的次冪，也就是低位不是全為1此時若皱，要使得index=21镊叁，h的低位部分不再具有唯一性了，哈希沖突的幾率會變的更大走触，同時晦譬，index對應的這個bit位無論如何不會等于1了，而對應的那些數(shù)組位置也就被白白浪費了互广。
get方法：
public V get(Object key) {
//如果key為null,則直接去table[0]處去檢索即可敛腌。
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
get方法通過key值返回對應value，如果key為null惫皱，直接去table[0]處檢索像樊。我們再看一下getEntry這個方法
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
//通過key的hashcode值計算hash值
int hash = (key == null) ? 0 : hash(key);
//indexFor (hash&length-1) 獲取最終數(shù)組索引，然后遍歷鏈表旅敷，通過equals方法比對找出對應記錄
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
可以看出生棍，get方法的實現(xiàn)相對簡單，key(hashcode)–>hash–>indexFor–>最終索引位置媳谁，找到對應位置table[i]涂滴，再查看是否有鏈表，遍歷鏈表韩脑，通過key的equals方法比對查找對應的記錄氢妈。要注意的是，有人覺得上面在定位到數(shù)組位置之后然后遍歷鏈表的時候段多，e.hash == hash這個判斷沒必要首量，僅通過equals判斷就可以。其實不然进苍，試想一下加缘，如果傳入的key對象重寫了equals方法卻沒有重寫hashCode，而恰巧此對象定位到這個數(shù)組位置觉啊，如果僅僅用equals判斷可能是相等的拣宏，但其hashCode和當前對象不一致，這種情況杠人，根據(jù)Object的hashCode的約定勋乾，不能返回當前對象宋下，而應該返回null，后面的例子會做出進一步解釋辑莫。
四学歧、重寫equals方法需同時重寫hashCode方法
最后我們再聊聊老生常談的一個問題，各種資料上都會提到各吨，“重寫equals時也要同時覆蓋hashcode”枝笨，我們舉個小例子來看看，如果重寫了equals而不重寫hashcode會發(fā)生什么樣的問題
public class MyTest {
private static class Person{
int idCard;
String name;
public Person(int idCard, String name) {
this.idCard = idCard;
this.name = name;
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()){
return false;
}
Person person = (Person) o;
//兩個對象是否等值揭蜒，通過idCard來確定
return this.idCard == person.idCard;
}
}
public static void main(String []args){
HashMap<Person,String> map = new HashMap<Person, String>();
Person person = new Person(1234,"喬峰");
//put到hashmap中去
map.put(person,"天龍八部");
//get取出横浑，從邏輯上講應該能輸出“天龍八部”
System.out.println("結(jié)果:"+map.get(new Person(1234,"蕭峰")));
}
}
實際輸出結(jié)果：null
https://www.cnblogs.com/vi3nty/p/10642456.html
所以，在重寫equals的方法的時候屉更，必須注意重寫hashCode方法徙融，同時還要保證通過equals判斷相等的兩個對象，調(diào)用hashCode方法要返回同樣的整數(shù)值偶垮。而如果equals判斷不相等的兩個對象张咳，其hashCode可以相同（只不過會發(fā)生哈希沖突，應盡量避免）似舵。
五脚猾、JDK1.8中HashMap的性能優(yōu)化
假如一個數(shù)組槽位上鏈上數(shù)據(jù)過多（即拉鏈過長的情況）導致性能下降該怎么辦？
JDK1.8在JDK1.7的基礎上針對增加了紅黑樹來進行優(yōu)化砚哗。即當鏈表超過8時龙助，鏈表就轉(zhuǎn)換為紅黑樹，利用紅黑樹快速增刪改查的特點提高HashMap的性能蛛芥，其中會用到紅黑樹的插入提鸟、刪除、查找等算法仅淑。
關(guān)于這方面的探討我們以后的文章再做說明称勋。
