Hash函數(shù)
什么是Hash
散列算法舔亭，也稱哈希算法蝗碎。實(shí)際中的Hash函數(shù)是指將一個大范圍映射到小范圍剃袍。把大范圍映射到一個小范圍的目的往往是節(jié)省空間，使得數(shù)據(jù)容易保存黔漂。除此之外诫尽，Hash函數(shù)往往應(yīng)用于加密與查找。
哈希表是一種以鍵-值（key-indexed）存儲的數(shù)據(jù)結(jié)構(gòu)炬守，通過輸入待查找的值牧嫉，獲取到對應(yīng)的值。
HashMap中的hash算法
算法回顧
-
<<:左移運(yùn)算符 num << n 丟棄最高位劳较，0補(bǔ)最低位
在數(shù)字沒有溢出的前提下驹止，無論正數(shù)和負(fù)數(shù)浩聋，左移n位，相當(dāng)于num乘以2的n次方
2.>>:右移運(yùn)算符 num >> n 符號位不變臊恋，左邊補(bǔ)上符號位
在數(shù)字沒有溢出的前提下右移n位衣洁，相當(dāng)于num除以2的n次方，取商
3.>>>: 無符號右移抖仅，忽略符號位坊夫，空位都以0補(bǔ)齊
%:模運(yùn)算 取余
^:位異或 第一個操作數(shù)的第n位與第二個操作數(shù)的第n位相反，那么結(jié)果的第n位也為1撤卢，否則為0
&:與運(yùn)算 第一個操作數(shù)的第n位與第二個操作數(shù)的第n位如果都為1环凿，那么結(jié)果的第n位也為1，否則為0
|:或運(yùn)算 第一個操作數(shù)的第n位與第二個操作數(shù)的第n位只要有一個為1放吩，那么結(jié)果的第n位也為1智听，否則為0
~:非運(yùn)算 操作數(shù)的第n位為1，那么結(jié)果的第n位為0
前提：HashMap中定義到桶的位置是根據(jù)key的hash值與數(shù)組的長度取模來計算的渡紫。
取模：hash%length=hashCode & （length - 1）
jdk1.8中的hash方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
取key的hashCode算法到推，然后對16進(jìn)行異或運(yùn)算和右移運(yùn)算。
key.hashCode()) ^ (h >>> 16)擾動函數(shù)減少了hash沖突的幾率惕澎。
