java零基礎入門-高級特性篇(二)? 哈希算法和HashMap
講完了List之后踏施，我們繼續(xù)講集合中的另外兩大巨頭，Map和Set。在講解這兩個巨頭之前剖张，很有必要來了解一下哈希算法，因為Map和Set的無腦實現(xiàn)類就是HashMap和HashSet揩环，所以在這之前了解Hash算法對我們更好的理解這兩個實現(xiàn)類很有幫助搔弄。
哈希算法是什么
哈希算法又叫散列算法，通常用于文件校驗丰滑，數(shù)字簽名等場景顾犹，比如下面這個新聞
不是在說哈希算法，這新聞跟哈希算法有什么關系褒墨？
Hash算法是一種算法思想炫刷，有很多種實現(xiàn)，新聞中的MD5又叫單向散列算法郁妈，是散列算法的一種實現(xiàn)浑玛。看新聞得知一個叫Wow.exe的文件可能中毒了噩咪，而公告叫大家檢測該文件的MD5校驗碼顾彰，這又是個什么意思？
MD5算法對文件進行計算以后胃碾，可以得到一個32位長度的字符串涨享，這個就是新聞中的MD5校驗碼。如果文件被病毒修改過仆百，那么會得到一個完全不同的32位字符串厕隧，所以我們下載這個WOW.exe文件以后，只需要對這個文件使用MD5算法栏账，看看校驗碼是否跟網(wǎng)站給出的MD5校驗碼一致，就可以判斷該文件是否中毒栈源。
相同的文件經(jīng)過哈希算法的計算可以得到相同的編碼，不同的文件甚垦，哪怕只有一點點的修改涣雕，都會得到一個完全不同的編碼。
那么將上面的結論反過來挣郭，具有相同MD5編碼的文件，一定是完全相同的文件嗎兑障？答案是否定的，兩個完全不同的文件得到的MD5編碼可能相同蕉汪，但是概率非常低，也就是說一個被病毒修改過的WOW.exe文件者疤，有可能跟源文件的MD5一樣，但是概率低到可以忽略不計驹马，所以比對MD5是可靠的。
現(xiàn)在我們對哈希算法有了一個大致的了解糯累，那么哈希算法有什么用算利，能解決什么問題呢笔时？
哈希算法解決了什么問題
又要拿快遞說事了，沒辦法仗岸，快遞里很多規(guī)則都是程序員定的借笙，所以用這個來看比較形象。
雙十一剛過不久业稼，大家收快遞有沒有收到手軟盗痒？手機短信有沒有收到手抖？雙十一快遞員可沒時間給你送上門低散，往驛站一扔俯邓，然后驛站入庫以后，就會給你發(fā)送一個像下面這樣的短信熔号。
這個短信其他的信息不重要稽鞭，最重要的是取貨碼這個信息。為什么驛站的帥哥美女看到你這個碼引镊，馬上就能找到你的快遞朦蕴？這個又要來看看驛站的貨架是怎么設計的了篮条。
這里A10就是貨架編號，8是指第8層吩抓，9856是訂單后四位涉茧，這個快遞放在A10架的第8層。每一個快遞放到驛站之后疹娶，根據(jù)在貨架上的存放位置伴栓，就可以得到一串編碼，一旦你去拿快遞，驛站小哥看一眼你的快遞編碼就知道你的快遞在哪個架子的什么地方了。
其實哈希算法跟這個快遞入庫出庫的過程非常相似咏瑟。哈希算法的目的矛双，也就是要解決的問題就是高速存取。
首先线脚，我們要存數(shù)據(jù)必須開辟一塊內(nèi)存空間。（存快遞需要一個XX驛站）
然后，我們需要將數(shù)據(jù)隨機短荐，并且均勻的分布到內(nèi)存空間中。（快遞叹哭，隨機放在快遞架子上忍宋，并且盡可能均勻的分布。這里均勻的意思是盡量保證快遞在架每一個架子风罩，每一層都有糠排，而不是堆在一個架子的一層，如果都堆在一層超升，找的時候還是一個個去對快遞單號入宦，架子沒有起到作用，找起來一樣很慢）室琢。
數(shù)據(jù)就算有沖突乾闰，必須放在一個空間中，也要保證這個空間中的數(shù)據(jù)盡量的少盈滴。（一個架子上每一層的快遞其實不止一個涯肩，但是是有限制的，不能太多巢钓，這樣一來，就算需要一個個的去比對單號后四位症汹，也會很快的找到需要的快遞）。
這里將一個快遞的位置計算成一個編碼A10-8-9856阵幸，其實可以看成是一個哈希算法的實現(xiàn)。但是這個實現(xiàn)不太優(yōu)秀挚赊，因為有過多的快遞擠在一個位置。優(yōu)秀的哈希算法妹卿，既要平局的分配空間蔑鹦，還要盡可能少的將多個數(shù)據(jù)放在同一個空間，比如MD5的哈希算法實現(xiàn)就非常優(yōu)秀铺纽，使用場景很多哟忍。
好了，基礎知識說完了其馏，可以來看看HashMap到底是個什么回事了爆安。
HashMap
上面講到的兩大點，總結一下就是：hash算法是一種計算方法褐奥，將一個文件或者一個值經(jīng)過hash算法的計算翘簇，得到一個值，這個值的特點是在空間上隨機，均勻的分布义桂，以達到高速存取的目的慷吊。
前面說過數(shù)組和鏈表，數(shù)組查詢快急鳄，鏈表增刪快，我現(xiàn)在要高速存（增）燃埠辍（查詢），那么數(shù)組和鏈表都不能滿足要求为牍，怎么辦岩馍？將他們組合起來用唄！
先看看Map的特點疫铜，Map是一種Key-value結構双谆，key-value又是個啥？初學者學習知識一般都處于十萬個為什么狀態(tài)囱井，可以理解趣避。key-value可以這樣理解：快遞編碼就是Key（A10-8-9856），value就是你的快遞包裹住练，通過Key可以找到value愁拭，這樣理解了吧。
key用來計算數(shù)據(jù)存儲的位置盏混，value就是要存放的數(shù)據(jù)许赃。存數(shù)據(jù)的時候，根據(jù)key經(jīng)過哈希算法計算出一個地址混聊，將數(shù)據(jù)扔進去乾巧，取得的時候预愤，通過key計算出地址植康，直接過去拿value拙绊，無需遍歷，直接存取榄攀，這樣就達到了高速存儲的目的金句。
看不懂圖的违寞，這樣理解：數(shù)組就是快遞的架子，這里的架子有10個军浆，從0開始編號挡闰。如果同一個架子的快遞多了，就要分層放了赞季，同一個架子的每一層就組成了鏈表申钩。有沒有感覺很形象瘪阁？（和快遞架那張圖對比看）
前面看到計算文件的哈希算法實現(xiàn)是MD5，驛站放快遞也有自己的編碼實現(xiàn)义黎，那么HashMap如何實現(xiàn)哈希算法伙菜？HashMap的實現(xiàn)是將Key的值計算為一個int值命迈，然后將這個int值作為數(shù)組的下標火的。也就是說key決定了value在數(shù)組的什么位置馏鹤，hash算法就是將需要保存的數(shù)據(jù)娇哆，均勻的分布在數(shù)組之中，避免出現(xiàn)過多的數(shù)據(jù)在數(shù)組的同一個位置治力。
但是上面說過勃黍，hash算法無法保證不重復，這里重復有兩種情況马澈，兩種情況的處理方式不同弄息。
1.如果key的值一樣，比如上圖中涤伐，2個數(shù)據(jù)的key都是111废亭，那么hash算法計算出的hash下標肯定一樣具钥，這種情況，后一個value會直接覆蓋掉前一個value掌动，上圖中就是第二個數(shù)據(jù)的bbb直接覆蓋掉了第一個數(shù)據(jù)aaa宁玫。
2.第二個情況就是兩個不同的值，計算出相同的下標眷射，這個時候會變成鏈表的存儲方式，后來的數(shù)據(jù)在前面涌庭，數(shù)據(jù)中有一部分存了下一個數(shù)據(jù)(前一個數(shù)據(jù)的地址)欧宜。上圖中ddd后插入，但是在鏈表中被添加到最前面席镀，并且指向了先插入的數(shù)據(jù)ccc豪诲。（鏈表使用addFirst()方法頭尾插入效率是非常高的）
有了這個處理方法挂绰，無論計算出的數(shù)組下標值是否一樣，都能保證芳室，任何一個不同的Key都能取到value刹勃，并且是高速獲取。
HashMap的底層實現(xiàn)
HashMap在jdk1.8之前使用的是數(shù)組加鏈表的實現(xiàn)方式伍宦，而在1.8中乏梁，當鏈表長度超過8之后，會轉為使用數(shù)組加紅黑樹的實現(xiàn)方式卖毁。這個知識了解即可亥啦，有興趣的同學可以去看一看紅黑樹這種數(shù)據(jù)結構练链。
HashMap說了這么多 為什么沒有說HashSet
一句話，HashSet的底層其實就是HashMap届吁，驚不驚喜，意不意外疚沐。
下一章介紹HashMap和HashSet的具體用法和Map，Set家族的其他成員。
