哈希表原理以及面試中的常見(jiàn)考點(diǎn)
來(lái)源：blog.csdn.net/m0_55221239/article/details/1145324039
首先得看java最基本的兩種數(shù)據(jù)結(jié)構(gòu)，數(shù)組和鏈表的區(qū)別：
而哈希表的出現(xiàn)是為了解決鏈表訪問(wèn)不快速的弱點(diǎn)，為了達(dá)到這一個(gè)目的：
哈希表中有一個(gè)哈希函數(shù)(散列函數(shù))。即構(gòu)建一個(gè)確定的映射，它能把關(guān)鍵字映射到一個(gè)唯一的存儲(chǔ)位置。這種映射應(yīng)該是我們可以進(jìn)行計(jì)算的。已知關(guān)鍵字，我們應(yīng)該能算出其地址；反之，已知地址，我們可以檢索到對(duì)應(yīng)的關(guān)鍵字。一旦建立起這種關(guān)系，那么給定關(guān)鍵字，我就能直接利用這個(gè)映射(即所謂的哈希函數(shù))直接算出其地址并尋址。這可大大縮減確定關(guān)鍵字存儲(chǔ)位置所花的時(shí)間。
HashMap和HashSet的區(qū)別
HashSet是通過(guò)HashMap來(lái)實(shí)現(xiàn)的，HashMap的輸入?yún)?shù)有Key、Value兩個(gè)組成，在實(shí)現(xiàn)HashSet的時(shí)候，保持HashMap的Value為常量，相當(dāng)于在HashMap中只對(duì)Key對(duì)象進(jìn)行處理。
HashMap的底層是一個(gè)數(shù)組結(jié)構(gòu)，數(shù)組中的每一項(xiàng)對(duì)應(yīng)了一個(gè)鏈表，這種結(jié)構(gòu)稱“鏈表散列”的數(shù)據(jù)結(jié)構(gòu)，即數(shù)組和鏈表的結(jié)合體；也叫散列表、哈希表。
想要了解HashMap和HashSet這樣兩個(gè)不同存儲(chǔ)結(jié)構(gòu)的區(qū)別，就得熟知他們的存儲(chǔ)過(guò)程：
HashMap存儲(chǔ)對(duì)象的過(guò)程
對(duì)HashMap的Key調(diào)用hashCode()方法，返回int值，即對(duì)應(yīng)的hashCode； 把此hashCode作為哈希表的索引，查找哈希表的相應(yīng)位置，若當(dāng)前位置內(nèi)容為NULL，則把HashMap的Key、Value包裝成Entry數(shù)組，放入當(dāng)前位置； 若當(dāng)前位置內(nèi)容不為空，則繼續(xù)查找當(dāng)前索引處存放的鏈表，利用equals方法，找到Key相同的Entry數(shù)組，則用當(dāng)前Value去替換舊的Value； 若未找到與當(dāng)前Key值相同的對(duì)象，則把當(dāng)前位置的鏈表后移（Entry數(shù)組持有一個(gè)指向下一個(gè)元素的引用），把新的Entry數(shù)組放到鏈表表頭；
HashSet存儲(chǔ)對(duì)象的過(guò)程
往HashSet添加元素的時(shí)候，HashSet會(huì)先調(diào)用元素的hashCode方法得到元素的哈希值 ， 然后通過(guò)元素 的哈希值經(jīng)過(guò)移位等運(yùn)算，就可以算出該元素在哈希表中的存儲(chǔ)位置，存儲(chǔ)時(shí)會(huì)出現(xiàn)兩種情況： 情況1：如果算出元素存儲(chǔ)的位置目前沒(méi)有任何元素存儲(chǔ)，那么該元素可以直接存儲(chǔ)到該位置上。 情況2：如果算出該元素的存儲(chǔ)位置目前已經(jīng)存在有其他的元素了，那么會(huì)調(diào)用該元素的equals方法與該位置的元素再比較一次，如果equals返回的是true，那么該元素與這個(gè)位置上的元素就視為重復(fù)元素，不允許添加，如果equals方法返回的是false，那么該元素允許添加。
小結(jié)
HashSet和HashMap的區(qū)別
常見(jiàn)考點(diǎn)
它的主要考點(diǎn)有：
是否會(huì)靈活的使用哈希表解決問(wèn)題 是否熟練掌握哈希表的基本原理 哈希沖突解決方法
小提示：
HashSet實(shí)現(xiàn)了Set接口，其內(nèi)部不允許出現(xiàn)重復(fù)的值，如果我們將一個(gè)對(duì)象存入HashSet，必須重寫equals()和hashCode()方法，這樣才能確保集合中不存在同一個(gè)元素。HashSet的內(nèi)部是無(wú)序的，因此不能使用 hashset.get(index) 來(lái)獲取元素。 HashMap實(shí)現(xiàn)了Map接口，其內(nèi)容是鍵值對(duì)的映射（key->value），不允許出現(xiàn)相同的鍵（key）。在查詢的時(shí)候會(huì)根據(jù)給出的鍵來(lái)查詢對(duì)應(yīng)的值。 我們可以認(rèn)為，HashSet和HashMap增查操作的時(shí)間復(fù)雜度都是常數(shù)級(jí)的。推薦：250期面試題匯總
哈希沖突解決方法
沖突（Collision），是說(shuō)兩個(gè)不同的 key 經(jīng)過(guò)哈希函數(shù)的計(jì)算后，得到了兩個(gè)相同的值。解決沖突的方法，主要有兩種：
開(kāi)散列法（Open Hashing）。是指哈希表所基于的數(shù)組中，每個(gè)位置是一個(gè) Linked List 的頭結(jié)點(diǎn)。這樣沖突的 閉散列法（Closed Hashing）是指在發(fā)生沖突的時(shí)候，后來(lái)的元素，往下一個(gè)位置去找空位。
哈希表的擴(kuò)容
哈希表容量的大小在一開(kāi)始是不確定的。如果哈希表存儲(chǔ)的元素太多（如超過(guò)容量的30%），我們應(yīng)該將哈希表容量擴(kuò)大一倍，并將所有的哈希值重新安排。
擴(kuò)展：HashFunction的實(shí)現(xiàn)
public class Solution {
/**
* @param key: A string you should hash
* @param HASH_SIZE: An integer
* @return: An integer
*/
public int hashCode(char[] key, int HASH_SIZE) {
// write your code here
long ans = 0;
for(int i = 0; i < key.length; i++){
ans = (ans * 33 + (int)(key[i])) % HASH_SIZE;
}
return (int)(ans);
}
}