目錄介紹
- 1.Hash的作用介紹
- 1.1 Hash的定義
- 1.2 Hash函數(shù)特性
- 1.3 Hash的使用場景
- 2.如何判斷兩個(gè)對象相等
- 2.1 判斷兩個(gè)字符串
- 2.2 判斷兩個(gè)int數(shù)值
- 2.3 其他基本類型
- 3.HashCode深入分析
- 3.0 HashCode是什么
- 3.1 為什么要重寫HashCode
- 3.2 HashCode源代碼分析
- 3.3 HashCode帶來的疑問
- 3.4 HashCode的作用
- 3.5 HashMap中的HashCode
- 3.6 可直接用hashcode判斷兩個(gè)對象是否相等
- 4.Hash表是什么
- 4.1 Hash表定義
- 4.2 Hash表簡單介紹
- 5.Hash中的算法應(yīng)用
- 5.1 基礎(chǔ)算法
- 5.2 經(jīng)典算法[摘自網(wǎng)絡(luò)]
- 5.3 Hash碰撞[摘自網(wǎng)絡(luò)]
- 6.Hash在Java中的應(yīng)用場景
- 6.1 equals與hashCode有兩個(gè)注意點(diǎn)
- 6.2 以HashSet為例說明hashCode()的作用
- 6.3 以HashMap為例說明Hash的作用
- 6.4
- 7.版本更新情況
- 8.其他介紹
好消息
- 博客筆記大匯總【16年3月到至今】稻薇，包括Java基礎(chǔ)及深入知識點(diǎn)胶征，Android技術(shù)博客睛低，Python學(xué)習(xí)筆記等等钱雷，還包括平時(shí)開發(fā)中遇到的bug匯總，當(dāng)然也在工作之余收集了大量的面試題拉庵，長期更新維護(hù)并且修正套蒂，持續(xù)完善……開源的文件是markdown格式的操刀！同時(shí)也開源了生活博客，從12年起撼嗓，積累共計(jì)47篇[近20萬字]静稻，轉(zhuǎn)載請注明出處，謝謝杀迹！
- 鏈接地址：https://github.com/yangchong211/YCBlogs
- 如果覺得好押搪，可以star一下大州，謝謝厦画！當(dāng)然也歡迎提出建議，萬事起于忽微力试，量變引起質(zhì)變排嫌！
1.Hash的作用介紹
1.1 Hash的定義
- 散列（哈希）函數(shù)
- 把任意長度的輸入（又叫做預(yù)映射pre-image）通過散列算法變換成固定長度的輸出淳地，該輸出就是散列值颇象，是一種壓縮映射。
- 或者說一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數(shù)嚷缭。
1.2 Hash函數(shù)特性
- h(k1)≠h(k2)則k1≠k2，即散列值不相同路幸，則輸入值即預(yù)映射不同
- 如果k1≠k2简肴，h(k1)=h(k2) 則發(fā)生碰撞；
- 如果h(k1)=h(k2)能扒，k1不一定等于k2初斑；
1.3 Hash的使用場景
- 比如說我們下載一個(gè)文件见秤，文件的下載過程中會經(jīng)過很多網(wǎng)絡(luò)服務(wù)器、路由器的中轉(zhuǎn)乎澄，如何保證這個(gè)文件就是我們所需要的呢测摔？我們不可能去一一檢測這個(gè)文件的每個(gè)字節(jié)锋八，也不能簡單地利用文件名查库、文件大小這些極容易偽裝的信息，這時(shí)候整慎，就需要一種指紋一樣的標(biāo)志來檢查文件的可靠性裤园，這種指紋就是我們現(xiàn)在所用的Hash算法(也叫散列算法)剂府。
- 散列算法就是一種以較短的信息來保證文件唯一性的標(biāo)志腺占，這種標(biāo)志與文件的每一個(gè)字節(jié)都相關(guān)，而且難以找到逆向規(guī)律铡羡。因此烦周，當(dāng)原有文件發(fā)生改變時(shí)，其標(biāo)志值也會發(fā)生改變漱贱，從而告訴文件使用者當(dāng)前的文件已經(jīng)不是你所需求的文件幅狮。
- 這種標(biāo)志有何意義呢闰靴？之前文件下載過程就是一個(gè)很好的例子蚂且，事實(shí)上杏死，現(xiàn)在大部分的網(wǎng)絡(luò)部署和版本控制工具都在使用散列算法來保證文件可靠性。
2.如何判斷兩個(gè)對象相等
2.1 判斷兩個(gè)字符串
- 使用equals方法判斷兩個(gè)字符串是否相等
String a = "yc1";
String b = "yc2";
boolean isEqual = a.equals(b);
- 當(dāng)然Object的子類可以通過重寫equals的方法腐巢，實(shí)現(xiàn)子類自身的對象是否相等的邏輯冯丙；String是Object的子類胃惜，查看下它的equals方法
//在Object類中
public boolean equals(Object obj) {
//直接比較的是地址
return (this == obj);
}
//在String類中
public boolean equals(Object anObject) {
//直接比較的是地址
if (this == anObject) {
return true;
}
//盤旋是否是字符串String類型
if (anObject instanceof String) {
String anotherString = (String) anObject;
int n = count;
if (n == anotherString.count) {
int i = 0;
//循環(huán)判斷每個(gè)字符是否相等
while (n-- != 0) {
if (charAt(i) != anotherString.charAt(i))
return false;
i++;
}
return true;
}
}
return false;
}
2.2 判斷兩個(gè)int數(shù)值
- Integer類的equals方法又是如何實(shí)現(xiàn)的呢船殉？
Integer a = Integer.valueOf("1");
Integer b = Integer.valueOf("2");
boolean ab = a.equals(b);
public boolean equals(Object obj) {
//先判斷是否是Integer類型
if (obj instanceof Integer) {
//轉(zhuǎn)為int值后進(jìn)行比較
return value == ((Integer)obj).intValue();
}
return false;
}
2.3 其他基本類型
//short類型
@Override
public int hashCode() {
return Short.hashCode(value);
}
public static int hashCode(short value) {
return (int)value;
}
//Byte類型
@Override
public int hashCode() {
return Byte.hashCode(value);
}
public static int hashCode(byte value) {
return (int)value;
}
//Long類型
@Override
public int hashCode() {
return Long.hashCode(value);
}
public static int hashCode(long value) {
return (int)(value ^ (value >>> 32));
}
//long類型作為索引范圍太大利虫，需要轉(zhuǎn)為int類型糠惫。這里簡單的獲取低32位容易導(dǎo)致散列不均钉疫，因?yàn)楦呶徊糠譀]有被利用陌选。所以這里采用邏輯右移32位咨油，讓高32位和低32位進(jìn)行XOR操作，導(dǎo)致高位低位都能被利用到
//Boolean類型
@Override
public int hashCode() {
return Boolean.hashCode(value);
}
public static int hashCode(boolean value) {
return value ? 1231 : 1237;
}
//采用兩個(gè)質(zhì)數(shù)作為true或false的索引赚爵。這兩個(gè)質(zhì)數(shù)足夠大冀膝，用來作為索引時(shí)霎挟，出現(xiàn)碰撞的可能性低酥夭。
3.HashCode深入分析
3.0 HashCode是什么
- HashCode是Object的一個(gè)方法熬北，hashCode方法返回一個(gè)hash code值讶隐，且這個(gè)方法是為了更好的支持hash表，比如String效五，Set火俄，HashTable讲冠、HashMap等;
3.1 為什么要重寫HashCode
- 如果用 equal 去比較的話竿开，如果存在1000個(gè)元素否彩，你 new 一個(gè)新的元素出來，需要去調(diào)用1000次equal去逐個(gè)和他們比較是否是同一個(gè)對象敬尺，這樣會大大降低效率砂吞。hashcode實(shí)際上是返回對象的存儲地址蜻直，如果這個(gè)位置上沒有元素，就把元素直接存儲在上面呼巷，如果這個(gè)位置上已經(jīng)存在元素王悍，這個(gè)時(shí)候才去調(diào)用equal方法與新元素進(jìn)行比較配名，相同的話就不存了晋辆，散列到其他地址上
3.2 HashCode源代碼分析
public int hashCode() {
int lockWord = shadow$_monitor_;
final int lockWordStateMask = 0xC0000000; // Top 2 bits.
final int lockWordStateHash = 0x80000000; // Top 2 bits are value 2 (kStateHash).
final int lockWordHashMask = 0x0FFFFFFF; // Low 28 bits.
if ((lockWord & lockWordStateMask) == lockWordStateHash) {
return lockWord & lockWordHashMask;
}
//返回的是對象引用地址
return System.identityHashCode(this);
}
public int hashCode() {
int h = hash;
if (h == 0 && count > 0) {
for (int i = 0; i < count; i++) {
h = 31 * h + charAt(i);
}
hash = h;
}
return h;
}
public int hashCode() {
//int值
return value;
}
3.3 HashCode帶來的疑問
- 為何重寫equals建議同時(shí)重寫hashCode芋膘？
- hashCode是什么为朋？
- hashCode作用厚脉？
- hash code（hash值）是什么傻工？
- hash table（hash表）是什么中捆？
- hashCode方法對hash表有益處？
- hashCode方法對不是hash有益處嗎?
3.4 HashCode的作用
- 減少查找次數(shù)殴蓬，提高程序效率
- 例如查找是否存在重復(fù)值
- h(k1)≠h(k2)則k1≠k2
- 首先查看h(k2)輸出值（內(nèi)存地址）染厅，查看該內(nèi)存地址是否存在值肖粮；
- 如果無尿赚，則表示該值不存在重復(fù)值蕉堰；
- 如果有屋讶，則進(jìn)行值比較，相同則表示該值已經(jīng)存在散列列表中斩芭，如果不相同則再進(jìn)行一個(gè)一個(gè)值比較划乖；而無需一開始就一個(gè)一個(gè)值的比較琴庵，減少了查找次數(shù)
3.5 HashMap中的HashCode
- 在Java中也一樣迷殿，hashCode方法的主要作用是為了配合基于散列的集合一起正常運(yùn)行咖杂，這樣的散列集合包括HashSet诉字、HashMap以及HashTable奏窑。
- 為什么這么說呢导披？考慮一種情況，當(dāng)向集合中插入對象時(shí)埃唯，如何判別在集合中是否已經(jīng)存在該對象了撩匕？（注意：集合中不允許重復(fù)的元素存在）
- 也許大多數(shù)人都會想到調(diào)用equals方法來逐個(gè)進(jìn)行比較，這個(gè)方法確實(shí)可行墨叛。但是如果集合中已經(jīng)存在一萬條數(shù)據(jù)或者更多的數(shù)據(jù)止毕，如果采用equals方法去逐一比較模蜡，效率必然是一個(gè)問題。
- 此時(shí)hashCode方法的作用就體現(xiàn)出來了忍疾，當(dāng)集合要添加新的對象時(shí)，先調(diào)用這個(gè)對象的hashCode方法谨朝，得到對應(yīng)的hashcode值卤妒，實(shí)際上在HashMap的具體實(shí)現(xiàn)中會用一個(gè)table保存已經(jīng)存進(jìn)去的對象的hashcode值，如果table中沒有該hashcode值字币，它就可以直接存進(jìn)去则披，不用再進(jìn)行任何比較了；如果存在該hashcode值洗出， 就調(diào)用它的equals方法與新元素進(jìn)行比較士复，相同的話就不存了，不相同就散列其它的地址翩活，所以這里存在一個(gè)沖突解決的問題阱洪，這樣一來實(shí)際調(diào)用equals方法的次數(shù)就大大降低了，說通俗一點(diǎn)：Java中的hashCode方法就是根據(jù)一定的規(guī)則將與對象相關(guān)的信息（比如對象的存儲地址菠镇，對象的字段等）映射成一個(gè)數(shù)值冗荸，這個(gè)數(shù)值稱作為散列值。下面這段代碼是java.util.HashMap的中put方法的具體實(shí)現(xiàn)：
- put方法是用來向HashMap中添加新的元素利耍，從put方法的具體實(shí)現(xiàn)可知俏竞，會先調(diào)用hashCode方法得到該元素的hashCode值，然后查看table中是否存在該hashCode值堂竟，如果存在則調(diào)用equals方法重新確定是否存在該元素魂毁，如果存在，則更新value值出嘹，否則將新的元素添加到HashMap中席楚。從這里可以看出，hashCode方法的存在是為了減少equals方法的調(diào)用次數(shù)税稼，從而提高程序效率烦秩。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
3.6 可直接用hashcode判斷兩個(gè)對象是否相等
- 肯定是不可以的，因?yàn)椴煌膶ο罂赡軙上嗤膆ashcode值郎仆。雖然不能根據(jù)hashcode值判斷兩個(gè)對象是否相等只祠，但是可以直接根據(jù)hashcode值判斷兩個(gè)對象不等，如果兩個(gè)對象的hashcode值不等扰肌，則必定是兩個(gè)不同的對象抛寝。如果要判斷兩個(gè)對象是否真正相等，必須通過equals方法。
- 也就是說對于兩個(gè)對象盗舰，如果調(diào)用equals方法得到的結(jié)果為true晶府，則兩個(gè)對象的hashcode值必定相等；
- 如果equals方法得到的結(jié)果為false钻趋，則兩個(gè)對象的hashcode值不一定不同川陆；
- 如果兩個(gè)對象的hashcode值不等，則equals方法得到的結(jié)果必定為false蛮位；
- 如果兩個(gè)對象的hashcode值相等较沪，則equals方法得到的結(jié)果未知。
4.Hash表是什么
4.1 Hash表定義
- 根據(jù)關(guān)鍵碼值（KEY-VALUE）而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)失仁；它通過把關(guān)鍵碼值（KEY-VALUE）映射到表中一個(gè)位置來訪問記錄购对，以加快查找的速度。這個(gè)映射函數(shù)叫做散列函數(shù)陶因，存放記錄的數(shù)組叫做散列表。
4.2 Hash表簡單介紹
- 將k作為輸入值垂蜗，h(k)輸出值作為內(nèi)存地址楷扬，該內(nèi)存地址用來存放value，然后可以通過k獲取到value存放的地址贴见，從而獲取value信息烘苹。
5.Hash中的算法應(yīng)用
5.1 基礎(chǔ)算法
- 比如，Java中的String.hashCode使用乘法和加法
public int hashCode() {
int h = hash;
if (h == 0 && count > 0) {
for (int i = 0; i < count; i++) {
//乘法與加法
h = 31 * h + charAt(i);
}
hash = h;
}
return h;
}
5.2 經(jīng)典算法[摘自網(wǎng)絡(luò)]
- MD4片部，MD5镣衡，SHA-1或SHA-2等其他
5.3 Hash碰撞[摘自網(wǎng)絡(luò)]
- hash是存在碰撞的，如果k1≠k2档悠，h(k1)=h(k2) 則發(fā)生碰撞廊鸥；
6.Hash在Java中的應(yīng)用場景
6.1 equals與hashCode有兩個(gè)注意點(diǎn)
- equals相同，則hashCode相同辖所；而hashCode相同惰说，equals不一定相同
- 如果equals相同，hashCode不相同缘回，有可能會造成上述重復(fù)值等情況吆视，這種情況是不允許的；
- 而hasCode相同酥宴，但是equals不一定相同啦吧，有可能是因?yàn)榘l(fā)生了碰撞而碰撞是有可能性發(fā)生的
6.2 以HashSet為例說明hashCode()的作用
- 假設(shè)，HashSet中已經(jīng)有1000個(gè)元素拙寡。當(dāng)插入第1001個(gè)元素時(shí)授滓，需要怎么處理？
- 因?yàn)镠ashSet是Set集合，它允許有重復(fù)元素褒墨§潘ⅲ“將第1001個(gè)元素逐個(gè)的和前面1000個(gè)元素進(jìn)行比較”？
- 顯然郁妈，這個(gè)效率是相等低下的浑玛。散列表很好的解決了這個(gè)問題，它根據(jù)元素的散列碼計(jì)算出元素在散列表中的位置噩咪，然后將元素插入該位置即可顾彰。對于相同的元素，自然是只保存了一個(gè)胃碾。
- 由此可知涨享，若兩個(gè)元素相等，它們的散列碼一定相等仆百；但反過來確不一定食磕。在散列表中怕敬，
- 1、如果兩個(gè)對象相等，那么它們的hashCode()值一定要相同歉提；
- 2粥庄、如果兩個(gè)對象hashCode()相等份乒，它們并不一定相等腿堤。
- 注意：這是在散列表中的情況。在非散列表中一定如此波势！
6.3 以HashMap為例說明Hash的作用
//put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//remove方法
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
//get方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
//上面這幾個(gè)方法都用到了這個(gè)方法
static final int hash(Object key) {
int h;
//計(jì)算hashCode翎朱，并無符號移動到低位
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
舉個(gè)例子: h = 363771819^(363771819 >>> 16)
0001 0101 1010 1110 1011 0111 1010 1011(363771819)
0000 0000 0000 0000 0001 0101 1010 1110(5550) XOR
--------------------------------------- =
0001 0101 1010 1110 1010 0010 0000 0101(363766277)
這樣做可以實(shí)現(xiàn)了高地位更加均勻地混到一起
參考博客
關(guān)于其他內(nèi)容介紹
01.關(guān)于博客匯總鏈接
02.關(guān)于我的博客
