hash表功能
hash表是一種表棘利，用于快速查找。在程序運行時灶搜，可以通過空間來換取時間，hash表就是這樣一種工窍，使用空間來換取時間的數(shù)據(jù)結(jié)構(gòu)割卖。hash表通過<key-value>的鍵值對的方式來訪問數(shù)據(jù)。通過key值來訪問數(shù)據(jù)患雏，實現(xiàn)最快的訪問鹏溯。
hash表本質(zhì)上，就是數(shù)組淹仑。鏈表也是可以用數(shù)組的方式來實現(xiàn)的丙挽，本質(zhì)也是數(shù)組。
hash表的構(gòu)成
思考一下匀借，如果hash表的key就是從1颜阐、2、3的方式排序吓肋，那么查找value值是不是很簡單凳怨。然而實際使用的時候并不容易這么剛好的情況，如果可以把key的值轉(zhuǎn)換為1、2肤舞、3這樣的中間值紫新，通過中間值來進行排序，再去數(shù)組的對應(yīng)位置找數(shù)據(jù)豈不是更快了呢李剖。
即將原本的key-value芒率，加一個中間商 hash值，對應(yīng)關(guān)系就變?yōu)?/p>
hash值是為了更快查找到目標數(shù)據(jù)而來的篙顺。
hash表的查找
這是一個簡單的hash表偶芍，hash函數(shù)為取十位作為hash值，通過這樣的hash轉(zhuǎn)換后慰安，每個值都有一個更容易查找的位置腋寨。
hash表沖突
由于hash值是通過hash函數(shù)轉(zhuǎn)換而來的，無法保證每個key都會有獨一無二的hash值化焕，可能有多個key對應(yīng)同一個hash值，這種情況就叫做hash沖突铃剔，hash沖突有多種解決方案撒桨。
后移法
如果想要放置的key位置被放置了，則將當前的key對應(yīng)數(shù)據(jù)放在后面最近的一個位置上键兜。記住凤类，hash的本質(zhì)就是數(shù)組，此時的數(shù)組并不是每個位置都是滿的普气，會有空位谜疤，這個位置被占了，就往后面一個位置挪就好了现诀。
鏈表法
將對應(yīng)同一個hash值的key都放在同一個節(jié)點后續(xù)夷磕，使用鏈表的方式進行保存。
hash表查找
hash查找仔沿，最終目的是通過key查找到目標value坐桩，先通過hash值快速定位大概位置。如果hash值位置的key值與查找key是一致的封锉，則查找到了绵跷。如果不對，則根據(jù)保存方法成福，去下一個節(jié)點查找碾局，直到對應(yīng)key的位置，就找到了對應(yīng)value奴艾。
以鏈表法的hash方式為例净当，如要查找key為15的數(shù)據(jù)
第一步，先去hash值為1的位置查找握侧。發(fā)現(xiàn)此處key不為15蚯瞧，則去下一個鏈表節(jié)點查找嘿期。
第二步，查找到此處key為15埋合，查找完成备徐，否則繼續(xù)去鏈表下一個節(jié)點查找。
hash表的擴容
hash本質(zhì)是數(shù)組甚颂，這個數(shù)組大小是變化的蜜猾，不能夠讓這個數(shù)組塞得滿滿的，數(shù)組不夠大的話振诬，每個位置下面鏈表很長蹭睡，那還是需要一個個遍歷，就無法達到快速查找的目的了赶么。HashMap的擴容方式肩豁，是當負載因子達到0.75的時候，將數(shù)組擴大為原來的兩倍辫呻，再重新排列hash表清钥。負載因子表示占用位置/總位置的比例，比如數(shù)組大小10放闺，被占用7個祟昭，則負載因子為0.7。
