什么是哈希表冈在？
哈希表（Hash table, 也叫散列表）醒陆，是根據(jù)鍵（Key）來直接訪問在內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)宴凉。它通過一個哈希函數(shù)將所需要查詢的數(shù)據(jù)映射到一張哈希表中稍刀，來提升查詢效率帐萎。
哈希函數(shù)的實現(xiàn)方法：
1.除留余數(shù)法
取關(guān)鍵字被某個不大于哈希表表長的數(shù)除后所得的余數(shù)為散列地址比伏。
2.折疊法
將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同），然后取這幾部分的疊加和（舍去進(jìn)位）作為哈希地址疆导。
3.平方取中法
取關(guān)鍵字平方后的中間幾位為哈希地址赁项。
4.直接定址法
取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為哈希地址。
哈希沖突
不管用什么哈希函數(shù)去計算哈希地址澈段，都是會產(chǎn)生哈希沖突的悠菜，因此我們需要想辦法解決哈希沖突，并且在設(shè)計哈希函數(shù)時败富，盡可能減少哈希沖突李剖。
1.單獨的鏈表法
在哈希表的后面單獨鏈上一個單鏈表來存儲沖突的元素，JDK 1.8 里的 HashMap 就是選擇的這種方式解決沖突的囤耳，不過它對鏈表做了一層優(yōu)化篙顺。當(dāng)元素個數(shù)大于等于 8 時，會把鏈表轉(zhuǎn)換成紅黑樹充择，提升查詢效率德玫。
2.線性探測法
當(dāng)發(fā)生哈希沖突時，逐個探測存放地址的表椎麦，直到查找到一個空單元宰僧。這個方式不便于查找，不建議使用观挎。
3.建立一個公共溢出區(qū)
當(dāng)發(fā)生哈希沖突時琴儿，就把元素存入到公用的溢出區(qū)段化，查詢時遍歷溢出區(qū)。
從上面這幾種處理方法來說造成，還是鏈表法效率比較高显熏，推薦使用。不過都有現(xiàn)成的工具類使用晒屎，因此只需要知道實現(xiàn)原理喘蟆，最好自己可以去寫代碼實現(xiàn)它。
哈希表有什么用鼓鲁？
哈希表在日常開發(fā)中還是比較常用的蕴轨，因為它最優(yōu)的查詢時間復(fù)雜度是 O(1)，當(dāng)哈希沖突比較嚴(yán)重的時候骇吭，查詢效率就相當(dāng)于線性的橙弱，因此哈希算法直接影響到查詢的效率。
哈希表怎么實現(xiàn)的燥狰？
哈希表的結(jié)構(gòu)
public class HashMap<K,V> {
//用節(jié)點數(shù)組當(dāng)作哈希表
Node<K,V>[] table;
int size;
//節(jié)點
static class Node<K,V> {
//哈希值
final int hash;
//鍵
final K key;
//值
V value;
//哈希值沖突時存儲
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
}
總結(jié)
哈希表是一個鍵值對的存儲結(jié)構(gòu)棘脐，并且根據(jù)鍵進(jìn)行哈希算法找到對應(yīng)的存儲位置。哈希算法會直接影響到哈希表的查詢效率碾局，一般選擇哈希沖突小的實現(xiàn)方式荆残，以便提升查詢效率。當(dāng)哈希沖突時净当，一般選擇鏈表來存儲沖突的元素内斯，當(dāng)沖突的元素增多時，可以采用紅黑樹來存儲像啼，以提升查詢效率俘闯。JDK 1.8 版本的 HashMap，當(dāng)鏈表個數(shù)大于等于 8 時忽冻，就是采用紅黑樹來存儲的真朗。在知道元素個數(shù)時，初始化哈希表時直接指定哈希表大小僧诚，因為當(dāng)元素達(dá)到哈希表大小時遮婶，會做 resize 操作。當(dāng)元素越來越多時湖笨，resize 是很耗時的旗扑，相當(dāng)于重建哈希表。因此直接指定哈希表大小慈省，減少 resize 次數(shù)以便提升插入性能臀防。
