網站首頁 編程語言 正文
前言
哈希表是一種 非常重要的數據結構，幾乎所有的編程語言都有 直接或者間接 的應用這種數據結構。
很多學習編程的人一直搞不懂哈希表到底是如何實現的，在這一章中，我們就一點點來實現一個自己的哈希表。通過實現來理解哈希表背后的原理和它的優勢。
1. 哈希表介紹和特性
哈希表通常是基于數組進行實現的，相對于數組，他有很多優勢：
- 他可以提供非?？焖俚?插入-刪除-查找 操作
- 無論多少數據，插入和刪除都接近常量的時間：即
O(1)的時間復雜度 - 哈希表的速度比 樹還要快，基本可以瞬間查找到想要的元素
- 哈希表相對于樹來說編碼要容易很多
PS: 樹也是一種基礎的數據結構，js 中沒有樹，我們下一章就會講樹
哈希表相對于數組的一些不足：
- 哈希表中的數據沒有順序，所以不能以一種固定的方式來遍歷其中的元素
- 通常情況下，哈希表中的
key是不允許重復的。
那么哈希表到底是什么？
我們上面說了哈希表的優勢和不足，似乎還是沒說它到底長什么樣子？
這也是哈希表不好理解的地方，它不像數組、鏈表和樹等可通過圖形的形式表示其結構和原理。
哈希表結構就是數組，但它神奇之處在于對下標值的一種變換，這種變換我們可以稱之為哈希函數，通過哈希函數可以獲取HashCode。
2. 哈希表的一些概念
- 哈希化：將大數字轉化成數組范圍內下標的過程，稱之為哈?；?/li>
- 哈希函數：我們通常會將單詞轉化成大數字，把大數字進行哈?；拇a實現放在一個函數中，該函數就稱為哈希函數；
- 哈希表：對最終數據插入的數組進行整個結構的封裝，得到的就是哈希表。
仍然需要解決的問題：
- 哈?；^后的下標依然可能重復，如何解決這個問題呢？這種情況稱為沖突，沖突是不可避免的，我們只能解決沖突。
3. 地址沖突解決方案
解決沖突常見的兩種方案：
3.1 方案一：鏈地址法
如下圖所示：
- 鏈地址法解決沖突的辦法是每個數組單元中存儲的不再是單個數據，而是一個鏈條
- 這個鏈條使用什么數據結構呢？常見的是數組或者鏈條
- 比如鏈表，也就是每個數組單元中存儲著一個鏈表。一旦發現重復，將重復的元素插入到鏈表的首端或者末端即可。
- 當查詢時，先根據哈希化后的下標值找到對應的位置，再取出鏈表，依次查詢要尋找的數據
數組還是鏈表？
- 數組或者鏈表在這其實都可以，效率上也差不多
- 因為根據哈?；?
index找出這個數組或者鏈表時，通常就會使用線性查找，這個時候數組和鏈表的效率是差不多的。 - 當然在某些實現中，會將新插入的數據放在數組或者鏈表的最前面，因為覺得新插入的數據用于取出的可能性更大
- 這種情況最好采用鏈表，因為數組在首位插入數據是需要所有其他項后移的，鏈表就沒有這樣的問題
3.2 方案二：開放地址法
開放地址法的主要工作方式是尋找空白的單元格來放置沖突的數據項。（了解即可，現在很少用到了）
據探測空白單元格位置方式的不同，可分為三種方法：
- 線性探測：如果發現要插入的位置已經被占據，則
+1，直到探測到空白位置 - 二次探測：二次探測就是在線性探測的基礎上把步長修改了（
+1 +4 +9） - 再哈希法：如果發現要插入的位置已經被占據，通過算法將這個位置再次哈?；钡降玫叫碌奈恢脹]被占據
4. 哈希函數代碼實現
好的哈希函數應該盡可能的讓計算的過程變得簡單，提高計算的效率。
- 哈希表的主要優點是它的速度，所以在速度上不能滿足，那么就打不到設計的目的了。
- 提高速度的一個辦法就是讓哈希函數中盡量少的有乘法和除法。因為它們的性能是比較低的。
設計好的哈希函數應該具有的優點：
- 快速的計算（霍納法則）
- 均勻的分布
下面我們就來實現一個哈希函數：
/**
* 哈希函數，將 key 映射成 index
* @param key 要轉換的 key
* @param max 數組的長度（最大的數值）
* @returns
*/
function hashFunc(key: string, max: number): number {
// 1. 計算 hashCode cats => 60337 （27為底的時候）
let hashCode = 0;
const length = key.length;
for (let i = 0; i < length; i++) {
// 霍納法則計算 hashCode
hashCode = 31 * hashCode + key.charCodeAt(i);
}
// 2. 求出索引值
const index = hashCode % max;
return index;
}
5. 哈希表封裝
經過前面這么多內容的鋪墊，我們現在終于可以真正實現自己的哈希表了
5.1 整體框架 v1 版
class HashTable<T = any> {
// 創建一個數組，用來存放鏈地址法中的鏈
storage: [string, T][][] = [];
// 定義數組的長度
private length: number = 7;
// 記錄已經存放元素的個數
private count: number = 0;
}
在上面代碼中，我們定義了三個屬性
-
storage：創建一個數組，用來存放鏈地址法中的鏈 -
length：定義數組的長度 -
count：記錄已經存放元素的個數
5.2 添加 put 方法 v2 版
put 方法的作用是插入&修改數據
在哈希表中，插入和修改操作是同一個函數。
- 因為，當使用者傳入一個
<key,value>時 - 如果原來不存在該
key，那么就是插入操作 - 如果已經存在該
key，那么就是修改操作
put(key: string, value: T) {
// 1.根據key 獲取數組中對應的索引值
const index = this.hashFunc(key, this.length);
// 2. 取出索引值對應位置的數組
let bucket = this.storage[index];
// 3. 判斷 bucket 是否有值
if (!bucket) {
bucket = [];
this.storage[index] = bucket;
}
// 4. 確定已經有一個數組了，但是數組中是否已經存在 key 時不確定的
let isUpdate = false;
for (let i = 0; i < bucket.length; i++) {
const tuple = bucket[i];
const tupleKey = tuple[0];
if (tupleKey === key) {
// 修改/更新的操作
tuple[1] = value;
isUpdate = true;
}
}
// 5. 如果上面的代碼沒有進行覆蓋，那么在該位置進行添加
if (!isUpdate) {
bucket.push([key, value]);
this.count++
}
}
測試：
const hashTable = new HashTable();
hashTable.put("aaa", 200);
hashTable.put("bbb", 300);
hashTable.put("ccc", 400);
上面 hashTable 的結構可以用下圖來表示：（aaa、bbb、ccc 可能在一個 bucket 中，也可能不在，具體要看哈希函數得到的 index）
5.3 添加 get 方法 v3 版
get 方法的作用是根據 key 獲取對應的值
get(key: string): T | undefined {
// 1. 根據 key 獲取索引值 index
const index = this.hashFunc(key, this.length);
// 2. 獲取 bucket（桶）
const bucket = this.storage[index];
if (!bucket) return undefined;
// 3. 對 bucket 進行遍歷
for (let i = 0; i < bucket.length; i++) {
const tuple = bucket[i];
const tupleKey = tuple[0];
const tupleValue = tuple[1];
if (tupleKey === key) {
return tupleValue;
}
}
return undefined;
}
測試：
get(key: string): T | undefined {
// 1. 根據 key 獲取索引值 index
const index = this.hashFunc(key, this.length);
// 2. 獲取 bucket（桶）
const bucket = this.storage[index];
if (!bucket) return undefined;
// 3. 對 bucket 進行遍歷
for (let i = 0; i < bucket.length; i++) {
const tuple = bucket[i];
const tupleKey = tuple[0];
const tupleValue = tuple[1];
if (tupleKey === key) {
return tupleValue;
}
}
return undefined;
}
5.4 添加 delete 方法 v4 版
delete 方法的作用是根據 key 刪除對應的值
delete(key: string): T | undefined {
// 1. 獲取索引值的位置
const index = this.hashFunc(key, this.length);
// 2. 獲取 bucket（桶）
const bucket = this.storage[index];
if (!bucket) return undefined;
// 3. 對 bucket 進行遍歷
for (let i = 0; i < bucket.length; i++) {
const tuple = bucket[i];
const tupleKey = tuple[0];
const tupleValue = tuple[1];
if (tupleKey === key) {
bucket.splice(i, 1);
this.count--;
return tupleValue;
}
}
return undefined;
}
測試：
const hashTable = new HashTable();
hashTable.put("aaa", 200);
hashTable.put("bbb", 300);
hashTable.put("ccc", 400);
hashTable.delete('aaa')
console.log(hashTable.get("aaa")); // undefined
console.log(hashTable.get("bbb")); // 300
console.log(hashTable.get("ccc")); // 400
6. 哈希表的自動擴容
目前，我們是將所有的數據項放在長度為 7 的數組中，因為我們使用的是鏈地址法，loadFactor 可以大于 1，所以這個哈希表是可以無限制的插入新數據的。
但是，隨著數據量的增多，每一個 index 對應的 bucket 會越來越長，也就造成效率的降低，所以在合適的情況對數組進行擴容是很有必要的。
loadFactor 譯為裝載因子。裝載因子用來衡量 HashMap 滿的程度
如何進行擴容？
擴容可以簡單的將容量增大兩倍，但是這種情況下，所有的數據項一定要同時進行修改（重新調用哈希函數）
1. 調整代碼，添加 resize 方法
private resize(newLength) {
// 設置新的長度
this.length = newLength;
// 獲取原來所有的數據，并且重新放入到新的容量數組中
// 1. 對數據進行的初始化操作
const oldStorage = this.storage;
this.storage = [];
this.count = 0;
// 2. 獲取原來數據，放入新的數組中
oldStorage.forEach((bucket) => {
if (!bucket) return;
for (let i = 0; i < bucket.length; i++) {
const tuple = bucket[i];
this.put(tuple[0], tuple[1]);
}
});
}
上面的 resize 方法的作用就對 哈希表進行擴容，但是我們應該如何使用 resize 方法呢?
答案就是，我們可以在 put 和 delete 方法的最后判斷一下當前哈希表的 loadFactor，比如：
- 當
loadFactor大于0.75時，對哈希表進行兩倍的擴容 - 當
loadFactor小于0.25時，對哈希表進行兩倍的縮容
2. 修改 put 方法
put(key: string, value: T) {
// 1.根據key 獲取數組中對應的索引值
const index = this.hashFunc(key, this.length);
console.log({ index });
// 2. 取出索引值對應位置的數組
let bucket = this.storage[index];
// 3. 判斷 bucket 是否有值
if (!bucket) {
bucket = [];
this.storage[index] = bucket;
}
// 4. 確定已經有一個數組了，但是數組中是否已經存在 key 時不確定的
let isUpdate = false;
for (let i = 0; i < bucket.length; i++) {
const tuple = bucket[i];
const tupleKey = tuple[0];
if (tupleKey === key) {
// 修改/更新的操作
tuple[1] = value;
isUpdate = true;
}
}
// 5. 如果上面的代碼沒有進行覆蓋，那么在該位置進行添加
if (!isUpdate) {
bucket.push([key, value]);
this.count++;
+ // 發現 loadFactor 比例已經大于 0.75，那么就直接擴容
+ const loadFactor = this.count / this.length;
+ if (loadFactor > 0.75) {
+ this.resize(this.length * 2);
+ }
}
}
3. 修改 delete 方法
delete(key: string): T | undefined {
// 1. 獲取索引值的位置
const index = this.hashFunc(key, this.length);
// 2. 獲取 bucket（桶）
const bucket = this.storage[index];
if (!bucket) return undefined;
// 3. 對 bucket 進行遍歷
for (let i = 0; i < bucket.length; i++) {
const tuple = bucket[i];
const tupleKey = tuple[0];
const tupleValue = tuple[1];
if (tupleKey === key) {
bucket.splice(i, 1);
this.count--;
+ // 發現 loadFactor 比例已經小于 0.75，那么就直接縮容
+ const loadFactor = this.count / this.length;
+ if (loadFactor < 0.25 && this.length > 7) {
+ this.resize(Math.floor(this.length / 2));
+ }
return tupleValue;
}
}
return undefined;
}
測試：
const hashTable = new HashTable();
hashTable.put("aaa", 200);
hashTable.put("bbb", 300);
hashTable.put("ccc", 400);
hashTable.put("ddd", 500);
hashTable.put("eee", 600);
console.log(hashTable.storage.length); // 7
hashTable.put("fff", 600);
console.log(hashTable.storage.length); // 14
hashTable.delete("fff");
hashTable.delete("eee");
console.log(hashTable.storage.length); // 14
hashTable.delete("ddd");
console.log(hashTable.storage.length); // 7原文鏈接：https://juejin.cn/post/7196322025114796087
相關推薦
- 2023-07-16 uniapp 微信小程序導航功能（從地址列表內點擊某一個地址）
- 2022-03-25 在?ASP.NET?Core?中為?gRPC?服務添加全局異常處理_ASP.NET
- 2023-03-15 Android?Studio?全局查找問題_Android
- 2024-07-13 spring-cloud和spring-cloud-alibaba的關系
- 2022-07-11 Android?Studio實現注冊頁面跳轉登錄頁面的創建_Android
- 2022-11-16 C++實現中綴轉后綴的示例詳解_C 語言
- 2022-05-20 PyQt5實現數據的增刪改查功能詳解_python
- 2022-04-28 Python的命令行參數實例詳解_python
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速