Java哈希表HashTable(又稱散列表)的實現(xiàn)及練習(xí)題
一、概念
關(guān)鍵詞及重點：【 哈希函數(shù)（散列函數(shù)）、哈希沖突、負(fù)載因子、哈希桶 】
1.1 哈希表概念
用順序結(jié)構(gòu)或平衡樹存放數(shù)據(jù)時，需要查找的時候必須經(jīng)過關(guān)鍵碼的多次比較，順序查找的時間復(fù)雜度為 O(N)，平衡樹時間復(fù)雜度為樹的高度，即 O(log?N)。
但理想的搜索方法是不經(jīng)過任何比較，一次直接從表中得到想要搜索的元素。而哈希表（或者稱散列表）結(jié)構(gòu)就是通過哈希（散列）函數(shù)使元素的存儲位置與它的關(guān)鍵碼之間建立一一映射的關(guān)系，從而在查找時不用進(jìn)行比較，時間復(fù)雜度為 O(1)。當(dāng)向該結(jié)構(gòu)中：
插入元素：根據(jù)待插入元素的關(guān)鍵碼，以哈希函數(shù)計算出該元素的存儲位置并按此位置進(jìn)行存放；
搜索元素：對元素的關(guān)鍵碼進(jìn)行同樣的計算，把求得的函數(shù)值當(dāng)做元素的存儲位置，在結(jié)構(gòu)中按此位置取元素比較，若關(guān)鍵碼相等，則搜索成功。
1.2 哈希函數(shù)
哈希函數(shù)設(shè)置為 hash(key) = key % capacity，capacity是指存儲元素底層空間總的大小。
1.3 沖突
不同關(guān)鍵字通過相同哈希函數(shù)計算出相同的哈希地址，該種現(xiàn)象稱為哈希沖突或哈希碰撞。 把具有不同關(guān)鍵碼而具有相同哈希地址的數(shù)據(jù)元素稱為 “同義詞”。
1.4 避免沖突
1、設(shè)計哈希函數(shù)；
2、調(diào)節(jié)負(fù)載因子。
散列表的負(fù)載因子（載荷因子）定義為：ɑ = 填入表中的元素個數(shù) / 哈希表的長度。
ɑ 越大，表明填入表中的元素越多，產(chǎn)生沖突的可能性越大；而 ɑ 與哈希表長度成反比，因此當(dāng)逼近或等于負(fù)載因子時需立即擴(kuò)容降低負(fù)載因子?！綣ava的系統(tǒng)庫限制負(fù)載因子為 0.75?！?/span>
1.5 解決沖突
1、 閉散列 / 開放定址法
當(dāng)發(fā)生哈希沖突時，如果哈希表未被裝滿，說明在哈希表中必然還有空位置，那么可以 把key存放到?jīng)_突位置中的“下一個” 空位置中去。而尋找下一個空位置的方法如下：
① 線性探測：從發(fā)生沖突的位置開始，依次向后探測，直到尋找到下一個空位置為止。缺點：不能隨便物理刪除哈希表中已有的元素，若直接刪除元素會影響其他元素的搜索。比如刪除元素4，如果直接刪除掉，14查找起來可能會受影響。因此線性探測采用標(biāo)記的偽刪除法來刪除一個元素。
② 二次探測：線性探測的缺陷是產(chǎn)生沖突的數(shù)據(jù)堆積在一塊，這與其找下一個空位置有關(guān)系，因為找空位置的方式就是挨著往后逐個去找，因此二次探測為了避免該問題，找下一個空位置的方法為
或
其中，i = 1,2...，H?是通過散列函數(shù)對關(guān)鍵碼 key 進(jìn)行運(yùn)算得到的位置，m 是表的大小。
研究表明：當(dāng)表的長度為質(zhì)數(shù)且表負(fù)載因子 ɑ 不超過 0.5 時，新的表項一定能夠插入，而且任何一個位置都不會被探查兩次。因此只要表中有一半的空位置，就不會存在表滿的問題。
因此，閉散列最大的缺陷就是空間利用率比較低，這也是哈希的缺陷。（消耗空間節(jié)省時間）
2、開散列 / 哈希桶 / 鏈地址法 / 開鏈法
首先對關(guān)鍵碼集合用散列函數(shù)計算散列地址，具有相同地址的關(guān)鍵碼歸于同一子集合，每一個子集合稱為一個桶，各個桶中的元素通過一個單鏈表鏈接起來，各鏈表的頭結(jié)點存儲在哈希表中。簡單來說就算 數(shù)組+鏈表 的形式。
1.6 沖突嚴(yán)重時
剛才我們提到了，哈希桶其實可以看作將大集合的搜索問題轉(zhuǎn)化為小集合的搜索問題了，那如果沖突嚴(yán)重，就意味著小集合的搜索性能其實也時不佳的，這個時候我們就可以將這個所謂的小集合搜索問題繼續(xù)進(jìn)行轉(zhuǎn)化，例如：
1、每個桶的背后是另一個哈希表；
2、每個桶的背后是一棵搜索樹。
1.7 tips
哈希函數(shù)作用是：建立元素與其存儲位置之前的對應(yīng)關(guān)系的，在存儲元素時，先通過哈希函數(shù)計算元素在哈希表格中的存儲位置，然后存儲元素。好的哈希函數(shù)可以減少沖突的概率，但是不能夠絕對避免，萬一發(fā)生哈希沖突，得需要借助哈希沖突處理方法來解決。
只要想哈希表格中存儲的元素超過兩個，就有可能存在哈希沖突；
常見的哈希函數(shù)有：直接定址法、除留余數(shù)法、平方取中法、隨機(jī)數(shù)法、數(shù)字分析法、疊加法等；
常見哈希沖突處理：閉散列（線性探測、二次探測）、開散列(鏈地址法)、多次散列。
二、哈希表的實現(xiàn)
數(shù)組 + 鏈表（數(shù)組存放鏈表首節(jié)點地址，節(jié)點形成單鏈表）
準(zhǔn)備工作：
定義內(nèi)部類節(jié)點 Node 、哈希表的成員變量：
public class HashBucket {
static class Node{
public int key;
public int val;
public Node next;
public Node(int key, int val){
this.key = key;
this.val = val;
}
}
public Node[] array = new Node[10];
public int usedSize;
}2.1 插入、擴(kuò)容
2.1.1 基本思想
// 默認(rèn)負(fù)載因子的限制值
public static final double DEFAULT_LOAD_FACTOR = 0.75;
public void push(int key, int val){
int index = key % array.length;
Node cur = array[index];
// 找到有無該節(jié)點
while(cur != null){
if (cur.key == key){
cur.val = val; // 更新 value值
return;
}
cur = cur.next;
}
// 沒有找到該節(jié)點，那么插入
Node node = new Node(key,val);
node.next = array[index];
array[index] = node;
usedSize++;
if (doLoadFactor() >= DEFAULT_LOAD_FACTOR){
resize();
}
}
private double doLoadFactor(){ // 計算當(dāng)前的負(fù)載因子
return usedSize*1.0 / array.length; // 乘1.0的目的是將整型隱式轉(zhuǎn)換為浮點型
}
private void resize(){
// 錯誤寫法，擴(kuò)容不僅僅是將容器放大容量，還應(yīng)該重新哈希
//array = Arrays.copyOf(array,2*array.length);
Node[] newArray = new Node[2*array.length]; // 存放到新的數(shù)組
// 遍歷原來的數(shù)組，重新哈希
for (int i = 0; i < array.length; i++) {
Node cur = array[i];
while (cur != null) {
int newIndex = cur.key % newArray.length;
Node curNext = cur.next; // 記錄原先數(shù)組的下一個節(jié)點
cur.next = newArray[newIndex];
newArray[newIndex] = cur;
cur = curNext; // 回到原先數(shù)組的下一個節(jié)點，而不是新數(shù)組的下一個節(jié)點
}
}
array = newArray;
}2.1.2 測試示例：
1、push()
public class Test {
public static void main(String[] args) {
HashBucket h = new HashBucket();
h.push(1,111);
h.push(2,222);
h.push(4,444);
h.push(14,141414);
h.push(21,212121);
h.push(12,121212);
h.push(24,242424);
}當(dāng)前存放元素個數(shù)為 7，負(fù)載因子為 0.7，未超過 0.75，不擴(kuò)容。測試結(jié)果：
2、擴(kuò)容之后
2.2 查找，獲取value值
// 查找有無key，與push方法中的查找類似
public int getVal(int key){
int index = key % array.length;
Node cur = array[index];
while (cur != null){
if (cur.key == key){
return cur.val;
}
cur = cur.next;
}
return -1;
}上述的代碼中 key 和 value 的類型都是整型，如果想要其他類型，就定義泛型結(jié)構(gòu)：
package hash;
public class HashBucket2<K, V> {
static class Node<K,V>{
public K key;
public V val;
public Node<K, V> next;
public Node(K key, V val){
this.key = key;
this.val = val;
}
}
public Node<K, V>[] array = (Node<K, V>[])new Node[10]; // 強(qiáng)轉(zhuǎn)
public int usedSize;
public static final double DEFAULT_LOAD_FACTOR = 0.75;
public void push(K key, V val){
int hashcode = key.hashCode(); // 調(diào)用 hashCode，使引用類型轉(zhuǎn)換為整數(shù)類型
int index = hashcode % array.length;
Node<K,V> cur = array[index];
while(cur != null){
if (cur.key.equals(key)){ // 引用類型用 .equals()
cur.val = val;
return;
}
cur = cur.next;
}
Node<K, V> node = new Node<>(key,val);
node.next = array[index];
array[index] = node;
usedSize++;
if (doLoadFactor() >= DEFAULT_LOAD_FACTOR){
resize();
}
}
private double doLoadFactor() { // 計算當(dāng)前的負(fù)載因子
return usedSize * 1.0 / array.length;
}
private void resize(){
Node<K,V>[] newArray = (Node<K, V>[])new Node[2*array.length]; // 存放到新的數(shù)組
// 遍歷原來的數(shù)組，重新哈希
for (int i = 0; i < array.length; i++) {
Node<K,V> cur = array[i];
while (cur != null) {
int hashcode = cur.key.hashCode();
int newIndex = hashcode % newArray.length;
Node<K,V> curNext = cur.next; // 記錄原先數(shù)組的下一個節(jié)點
cur.next = newArray[newIndex];
newArray[newIndex] = cur;
cur = curNext; // 回到原先數(shù)組的下一個節(jié)點，而不是新數(shù)組的下一個節(jié)點
}
}
array = newArray;
}
public V getVal(K key){
int hashcode = key.hashCode();
int index = hashcode % array.length;
Node<K,V> cur = array[index];
while(cur != null){
if (cur.key.equals(key)){
return cur.val;
}
cur = cur.next;
}
return null;
}
}測試：
package hash;
import java.util.Objects;
class Student{
public String id;
public Student(String id){
this.id = id;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Student student = (Student) o;
return Objects.equals(id, student.id);
}
@Override
public int hashCode() {
return Objects.hash(id);
}
}
public class Test {
public static void main(String[] args) {
Student student1 = new Student("409");
Student student2 = new Student("409");
System.out.println(student1.hashCode());
System.out.println(student2.hashCode());
// 當(dāng)自定義類沒有重寫 equals() 和 hashCode() 方法時，下面輸出false
System.out.println(student1.equals(student2));
HashBucket2<Student, String> h = new HashBucket2<>();
h.push(student1,"Li");
h.push(student2,"NAZA");
System.out.println(h.getVal(student1));
}
}輸出結(jié)果：
51548
51548
true
NAZA
（此處插入一個面試題：對于HashMap，如果一個對象為 key 時，hashCode 和 equals 方法的用法要注意什么？）
2.3 性能分析
雖然哈希表一直在和沖突做斗爭，但在實際使用過程中，我們認(rèn)為哈希表的沖突率是不高的，沖突個數(shù)是可控的，也就是每個桶中的鏈表的長度是一個常數(shù)，所以，通常意義下，我們認(rèn)為哈希表的插入/刪除/查找時間復(fù)雜度是 O(1) 。
2.4 和Java集合類的關(guān)系
1、HashMap 和 HashSet 即 java 中利用哈希表實現(xiàn)的 Map 和 Set
2、java 中使用的是哈希桶方式解決沖突的
3、java 會在沖突鏈表長度大于一定閾值后，將鏈表轉(zhuǎn)變?yōu)樗阉鳂洌t黑樹）
4、java 中計算哈希值實際上是調(diào)用類的 hashCode 方法，進(jìn)行 key 的相等性比較是調(diào)用 key 的 equals 方法。
所以如果要用自定義類作為 HashMap 的 key 或者 HashSet 的值，必須重寫 hashCode 和 equals 方法，而且要做到 equals 相等的對象，hashCode 產(chǎn)生的整數(shù)結(jié)果一定是一致的。但是 hashCode 一樣時，equals 得到的結(jié)果可能一樣也可能不一樣，因為 hashCode 一樣只能說明存放在表中的位置是一樣的，key 不一定一樣。
簡而言之：如果兩個對象根據(jù) equals() 方法比較是相等的，那么調(diào)用這兩個對象的 hashCode() 方法必須產(chǎn)生相同的整數(shù)結(jié)果。反之，兩個對象的 hashCode() 相同，它們并不一定 equals()。（面試題解答的核心原則）
【用哈希時使用的自定義類型不需要實現(xiàn)可比較，但是用 TreeMap 或 TreeSet 時需要可比較的類型】
三、Map 和 Set 練習(xí)題
3.1 統(tǒng)計英文閱讀中的單詞詞頻
使用 Map 的核心邏輯：如果 map 中存在該單詞，則計數(shù)+1；否則放入 map 并設(shè)置計數(shù)為1。
package hash;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
public class Test {
public static Map<String, Integer> countWords(String[] str) {
Map<String, Integer> map = new HashMap<>();
for (String s : str) {
if (map.get(s) != null){
int val = map.get(s); // 取得當(dāng)前的value值
map.put(s,val+1);
}else{
map.put(s,1);
}
}
return map;
}
public static void main(String[] args) {
String[] str = {"Long","Long","Long","time","age","there","is","a","pig","live","in","a","house"};
Map<String, Integer> map = countWords(str);
Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
for (Map.Entry<String, Integer> s : entrySet) {
System.out.println("word: "+s.getKey() + " nums: "+s.getValue());
}
}
}3.2 找出單身狗/只出現(xiàn)一次的數(shù)字
解法有多種，除了使用異或的方法，還能使用集合來解決。
使用集合的基本思想：遍歷數(shù)組，第一次出現(xiàn)的放到 Set 中，第二次出現(xiàn)的就將其移出，最后 Set 里面得到的就是只出現(xiàn)一次的數(shù)字。
public int singleNumber(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (int n : nums) {
if (set.contains(n)){
set.remove(n);
}else {
set.add(n);
}
}
for (int n : nums) {
if (set.contains(n)){
return n;
}
}
return -1;
}3.3復(fù)制帶隨機(jī)指針的鏈表
采用 Map 會非常方便，但是如果不使用 Map 該如何復(fù)制？
public Node copyRandomList(Node head) {
HashMap<Node, Node> map = new HashMap<>();
// 1、根據(jù)val值新建節(jié)點
Node cur = head;
while (cur != null){
Node node = new Node(cur.val);
map.put(cur,node); // 將舊節(jié)點地址和新節(jié)點地址一起放到map中
cur = cur.next;
}
// 2、重新遍歷,設(shè)置next和random
cur = head;
while (cur != null){
// get()返回的是val值，即返回的是存放在map中的 新地址
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
return map.get(head); // 返回的是頭節(jié)點的新地址
}3.4寶石與石頭
解法可以用數(shù)組也可以采用集合的方法。使用數(shù)組的方法執(zhí)行用時會比使用集合的方法用時短。
采用集合：將一顆顆“寶石”存放到 Set 中，遍歷“石頭”，查看“石頭”里面是否包含了“寶石”。
public int numJewelsInStones(String jewels, String stones) {
HashSet<Character> jewelsSet = new HashSet<>();
for(int i = 0; i < jewels.length(); i++){
char s = jewels.charAt(i);
jewelsSet.add(s);
}
int count = 0;
for(int i = 0; i < stones.length(); i++){
char s = stones.charAt(i);
if(jewelsSet.contains(s)){
count++;
}
}
return count;
}3.5壞鍵盤打字
基本思想：將實際輸出的字符存放到 Set 中，遍歷應(yīng)該輸入的字符串，注意有重復(fù)輸出的情況。
public static void findBrokenKey(String str1, String str2){
// 1、先全部轉(zhuǎn)化為大寫
str1 = str1.toUpperCase();
str2 = str2.toUpperCase();
// 2、將實際輸出的按鍵存儲到 set 中
HashSet<Character> setAct = new HashSet<>();
for (int i = 0; i < str2.length(); i++) {
char c2 = str2.charAt(i);
setAct.add(c2);
}
// 3、遍歷應(yīng)該輸出的字符串
/*for (int i = 0; i < str1.length(); i++) {
char c1 = str1.charAt(i);
if (!setAct.contains(c1)) {
System.out.print(c1);
}
}*/ // 存在問題：重復(fù)輸出
// 4、修正，避免重復(fù)輸出的情況
HashSet<Character> setBroken = new HashSet<>();
for (int i = 0; i < str1.length(); i++) {
char c1 = str1.charAt(i);
// 如果已經(jīng)存放到 setBroken ，即已經(jīng)被包含，就跳過if語句塊
if (!setAct.contains(c1) && !setBroken.contains(c1)) {
setBroken.add(c1);
System.out.print(c1);
}
}
}
public static void main(String[] args) {
String s1 = "7_This_is_a_test";
String s2 = "_hs_s_a_es";
findBrokenKey(s1,s2);
}3.6前K個高頻單詞
基本思想：類似 Top-K：統(tǒng)計所有單詞的詞頻，前K個建小根堆，比較交換重建小根堆……
不過題目要求說“如果不同的單詞有相同出現(xiàn)頻率， 按字典順序 排序”，因此除了關(guān)注詞頻，還得關(guān)注單詞的大小比較，因此使用 Map 存放兩個值。
重點是建立 PriorityDeque 時傳入的比較器的方法重寫。
public List<String> topKFrequent(String[] words, int k) {
// 1、統(tǒng)計單詞詞頻
HashMap<String, Integer> wordFrequency = new HashMap<>();
for (String word: words) {
if (wordFrequency.get(word) == null){
wordFrequency.put(word,1);
}else{
int val = wordFrequency.get(word);
wordFrequency.put(word,val+1);
}
}
// 2、建堆
PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
@Override
public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
if (o1.getValue().compareTo(o2.getValue()) == 0){ // 如果詞頻一樣，就按照字典順序比較
return o2.getKey().compareTo(o1.getKey()); // 此處應(yīng)該建大根堆，因為如果建立小根堆，后面reverse之后與題目要求不符
}
return o1.getValue().compareTo(o2.getValue()); // 根據(jù)詞頻建堆
}
});
// 3、遍歷HashMap
for (Map.Entry<String,Integer> entry: wordFrequency.entrySet()) {
if (minHeap.size() < k) { // 前k個單詞建立小根堆
minHeap.offer(entry);
}else{
Map.Entry<String, Integer> top = minHeap.peek(); // 得到目前堆頂?shù)脑?
// 進(jìn)行比較
if (top.getValue().compareTo(entry.getValue()) < 0){ // 如果后面的元素詞頻大于前面最小的單詞的詞頻，就“交換”
minHeap.poll();
minHeap.add(entry);
}else if(top.getValue().compareTo(entry.getValue()) == 0){ // 如果字母詞頻相同
if (top.getKey().compareTo(entry.getKey()) > 0){ // 字母較大的，存放到堆里面
minHeap.poll();
minHeap.add(entry);
}
}
}
}
ArrayList<String> list = new ArrayList<>();
for (int i = 0; i < k; i++) {
Map.Entry<String, Integer> tmp = minHeap.poll();
list.add(tmp.getKey());
}
Collections.reverse(list); // ArrayList 繼承的Collections接口可以翻轉(zhuǎn)
return list;
}通過上面的練習(xí)，我發(fā)現(xiàn)似乎涉及同一個元素出現(xiàn)次數(shù) / 統(tǒng)計頻率 / 有無某元素 / 復(fù)制等類型都能使用到 Map 和 Set ，因此在處理超過2個以上的數(shù)據(jù)時，就得應(yīng)用集合的知識，發(fā)散性思考。
總結(jié)
到此這篇關(guān)于Java哈希表HashTable(又稱散列表)實現(xiàn)及練習(xí)題的文章就介紹到這了,更多相關(guān)Java哈希表HashTable內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
mybatis如何獲取剛剛新插入數(shù)據(jù)的主鍵值id
這篇文章主要介紹了mybatis如何獲取剛剛新插入數(shù)據(jù)的主鍵值id問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-08-08
這篇文章主要介紹了hashmap為什么查詢時間復(fù)雜度為O(1)，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-08-08
StateMachine 狀態(tài)機(jī)機(jī)制深入解析
這篇文章主要介紹了,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-08-08
mybatis-plus批處理IService的實現(xiàn)示例
這篇文章主要介紹了mybatis-plus批處理IService的實現(xiàn)示例，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-08-08
SpringBoot參數(shù)校驗的一些實戰(zhàn)應(yīng)用
這篇文章主要給大家介紹了關(guān)于SpringBoot參數(shù)校驗的一些實戰(zhàn)應(yīng)用,包括使用內(nèi)置的參數(shù)校驗注解、嵌套對象校驗、分組校驗以及自定義校驗注解,通過這些方法,可以有效地提高系統(tǒng)的穩(wěn)定性和安全性,需要的朋友可以參考下2024-11-11
Spring Boot 2.4版本前后的分組配置變化及對多環(huán)境配置結(jié)構(gòu)的影響(推薦)
這篇文章主要介紹了Spring Boot 2.4版本前后的分組配置變化及對多環(huán)境配置結(jié)構(gòu)的影響,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-12-12
這篇文章主要介紹了java8中l(wèi)amba表達(dá)式的使用,非常不錯，具有參考借鑒價值，需要的朋友可以參考下2017-02-02
關(guān)于SpringBoot配置文件加載位置的優(yōu)先級
這篇文章主要介紹了關(guān)于SpringBoot配置文件加載位置的優(yōu)先級,我們也可以通過spring.config.location來改變默認(rèn)的配置文件位置,項目打包好后,我們可以通過命令行的方式在啟動時指定配置文件的位置,需要的朋友可以參考下2023-10-10
本文主要講解了java中對象基礎(chǔ)Object類，文中運(yùn)用大量代碼講解的非常詳細(xì)，想學(xué)習(xí)相關(guān)知識的小伙伴可以參考一下這篇文章2021-09-09
Java中的NoClassDefFoundError報錯含義解析
這篇文章主要為大家介紹了Java中的NoClassDefFoundError含義詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助2023-11-11