網(wǎng)站首頁 編程語言 正文
前言
哈希表是一種 非常重要的數(shù)據(jù)結(jié)構(gòu)，幾乎所有的編程語言都有 直接或者間接 的應(yīng)用這種數(shù)據(jù)結(jié)構(gòu)。
很多學(xué)習(xí)編程的人一直搞不懂哈希表到底是如何實(shí)現(xiàn)的，在這一章中，我們就一點(diǎn)點(diǎn)來實(shí)現(xiàn)一個自己的哈希表。通過實(shí)現(xiàn)來理解哈希表背后的原理和它的優(yōu)勢。
1. 哈希表介紹和特性
哈希表通常是基于數(shù)組進(jìn)行實(shí)現(xiàn)的，相對于數(shù)組，他有很多優(yōu)勢：
- 他可以提供非常快速的 插入-刪除-查找 操作
- 無論多少數(shù)據(jù)，插入和刪除都接近常量的時間：即
O(1)的時間復(fù)雜度 - 哈希表的速度比 樹還要快，基本可以瞬間查找到想要的元素
- 哈希表相對于樹來說編碼要容易很多
PS: 樹也是一種基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，js 中沒有樹，我們下一章就會講樹
哈希表相對于數(shù)組的一些不足：
- 哈希表中的數(shù)據(jù)沒有順序，所以不能以一種固定的方式來遍歷其中的元素
- 通常情況下，哈希表中的
key是不允許重復(fù)的。
那么哈希表到底是什么？
我們上面說了哈希表的優(yōu)勢和不足，似乎還是沒說它到底長什么樣子？
這也是哈希表不好理解的地方，它不像數(shù)組、鏈表和樹等可通過圖形的形式表示其結(jié)構(gòu)和原理。
哈希表結(jié)構(gòu)就是數(shù)組，但它神奇之處在于對下標(biāo)值的一種變換，這種變換我們可以稱之為哈希函數(shù)，通過哈希函數(shù)可以獲取HashCode。
2. 哈希表的一些概念
- 哈希化：將大數(shù)字轉(zhuǎn)化成數(shù)組范圍內(nèi)下標(biāo)的過程，稱之為哈希化；
- 哈希函數(shù)：我們通常會將單詞轉(zhuǎn)化成大數(shù)字，把大數(shù)字進(jìn)行哈希化的代碼實(shí)現(xiàn)放在一個函數(shù)中，該函數(shù)就稱為哈希函數(shù)；
- 哈希表：對最終數(shù)據(jù)插入的數(shù)組進(jìn)行整個結(jié)構(gòu)的封裝，得到的就是哈希表。
仍然需要解決的問題：
- 哈希化過后的下標(biāo)依然可能重復(fù)，如何解決這個問題呢？這種情況稱為沖突，沖突是不可避免的，我們只能解決沖突。
3. 地址沖突解決方案
解決沖突常見的兩種方案：
3.1 方案一：鏈地址法
如下圖所示：
- 鏈地址法解決沖突的辦法是每個數(shù)組單元中存儲的不再是單個數(shù)據(jù)，而是一個鏈條
- 這個鏈條使用什么數(shù)據(jù)結(jié)構(gòu)呢？常見的是數(shù)組或者鏈條
- 比如鏈表，也就是每個數(shù)組單元中存儲著一個鏈表。一旦發(fā)現(xiàn)重復(fù)，將重復(fù)的元素插入到鏈表的首端或者末端即可。
- 當(dāng)查詢時，先根據(jù)哈希化后的下標(biāo)值找到對應(yīng)的位置，再取出鏈表，依次查詢要尋找的數(shù)據(jù)
數(shù)組還是鏈表？
- 數(shù)組或者鏈表在這其實(shí)都可以，效率上也差不多
- 因?yàn)楦鶕?jù)哈希化的
index找出這個數(shù)組或者鏈表時，通常就會使用線性查找，這個時候數(shù)組和鏈表的效率是差不多的。 - 當(dāng)然在某些實(shí)現(xiàn)中，會將新插入的數(shù)據(jù)放在數(shù)組或者鏈表的最前面，因?yàn)橛X得新插入的數(shù)據(jù)用于取出的可能性更大
- 這種情況最好采用鏈表，因?yàn)閿?shù)組在首位插入數(shù)據(jù)是需要所有其他項(xiàng)后移的，鏈表就沒有這樣的問題
3.2 方案二：開放地址法
開放地址法的主要工作方式是尋找空白的單元格來放置沖突的數(shù)據(jù)項(xiàng)。（了解即可，現(xiàn)在很少用到了）
據(jù)探測空白單元格位置方式的不同，可分為三種方法：
- 線性探測：如果發(fā)現(xiàn)要插入的位置已經(jīng)被占據(jù)，則
+1，直到探測到空白位置 - 二次探測：二次探測就是在線性探測的基礎(chǔ)上把步長修改了（
+1 +4 +9） - 再哈希法：如果發(fā)現(xiàn)要插入的位置已經(jīng)被占據(jù)，通過算法將這個位置再次哈希化，直到得到新的位置沒被占據(jù)
4. 哈希函數(shù)代碼實(shí)現(xiàn)
好的哈希函數(shù)應(yīng)該盡可能的讓計算的過程變得簡單，提高計算的效率。
- 哈希表的主要優(yōu)點(diǎn)是它的速度，所以在速度上不能滿足，那么就打不到設(shè)計的目的了。
- 提高速度的一個辦法就是讓哈希函數(shù)中盡量少的有乘法和除法。因?yàn)樗鼈兊男阅苁潜容^低的。
設(shè)計好的哈希函數(shù)應(yīng)該具有的優(yōu)點(diǎn)：
- 快速的計算（霍納法則）
- 均勻的分布
下面我們就來實(shí)現(xiàn)一個哈希函數(shù)：
/**
* 哈希函數(shù)，將 key 映射成 index
* @param key 要轉(zhuǎn)換的 key
* @param max 數(shù)組的長度（最大的數(shù)值）
* @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. 哈希表封裝
經(jīng)過前面這么多內(nèi)容的鋪墊，我們現(xiàn)在終于可以真正實(shí)現(xiàn)自己的哈希表了
5.1 整體框架 v1 版
class HashTable<T = any> {
// 創(chuàng)建一個數(shù)組，用來存放鏈地址法中的鏈
storage: [string, T][][] = [];
// 定義數(shù)組的長度
private length: number = 7;
// 記錄已經(jīng)存放元素的個數(shù)
private count: number = 0;
}
在上面代碼中，我們定義了三個屬性
-
storage：創(chuàng)建一個數(shù)組，用來存放鏈地址法中的鏈 -
length：定義數(shù)組的長度 -
count：記錄已經(jīng)存放元素的個數(shù)
5.2 添加 put 方法 v2 版
put 方法的作用是插入&修改數(shù)據(jù)
在哈希表中，插入和修改操作是同一個函數(shù)。
- 因?yàn)椋?dāng)使用者傳入一個
<key,value>時 - 如果原來不存在該
key，那么就是插入操作 - 如果已經(jīng)存在該
key，那么就是修改操作
put(key: string, value: T) {
// 1.根據(jù)key 獲取數(shù)組中對應(yīng)的索引值
const index = this.hashFunc(key, this.length);
// 2. 取出索引值對應(yīng)位置的數(shù)組
let bucket = this.storage[index];
// 3. 判斷 bucket 是否有值
if (!bucket) {
bucket = [];
this.storage[index] = bucket;
}
// 4. 確定已經(jīng)有一個數(shù)組了，但是數(shù)組中是否已經(jīng)存在 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. 如果上面的代碼沒有進(jìn)行覆蓋，那么在該位置進(jìn)行添加
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 的結(jié)構(gòu)可以用下圖來表示：（aaa、bbb、ccc 可能在一個 bucket 中，也可能不在，具體要看哈希函數(shù)得到的 index）
5.3 添加 get 方法 v3 版
get 方法的作用是根據(jù) key 獲取對應(yīng)的值
get(key: string): T | undefined {
// 1. 根據(jù) key 獲取索引值 index
const index = this.hashFunc(key, this.length);
// 2. 獲取 bucket（桶）
const bucket = this.storage[index];
if (!bucket) return undefined;
// 3. 對 bucket 進(jìn)行遍歷
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. 根據(jù) key 獲取索引值 index
const index = this.hashFunc(key, this.length);
// 2. 獲取 bucket（桶）
const bucket = this.storage[index];
if (!bucket) return undefined;
// 3. 對 bucket 進(jìn)行遍歷
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 方法的作用是根據(jù) key 刪除對應(yīng)的值
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 進(jìn)行遍歷
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. 哈希表的自動擴(kuò)容
目前，我們是將所有的數(shù)據(jù)項(xiàng)放在長度為 7 的數(shù)組中，因?yàn)槲覀兪褂玫氖擎湹刂贩ǎ?code>loadFactor 可以大于 1，所以這個哈希表是可以無限制的插入新數(shù)據(jù)的。
但是，隨著數(shù)據(jù)量的增多，每一個 index 對應(yīng)的 bucket 會越來越長，也就造成效率的降低，所以在合適的情況對數(shù)組進(jìn)行擴(kuò)容是很有必要的。
loadFactor 譯為裝載因子。裝載因子用來衡量 HashMap 滿的程度
如何進(jìn)行擴(kuò)容？
擴(kuò)容可以簡單的將容量增大兩倍，但是這種情況下，所有的數(shù)據(jù)項(xiàng)一定要同時進(jìn)行修改（重新調(diào)用哈希函數(shù)）
1. 調(diào)整代碼，添加 resize 方法
private resize(newLength) {
// 設(shè)置新的長度
this.length = newLength;
// 獲取原來所有的數(shù)據(jù)，并且重新放入到新的容量數(shù)組中
// 1. 對數(shù)據(jù)進(jìn)行的初始化操作
const oldStorage = this.storage;
this.storage = [];
this.count = 0;
// 2. 獲取原來數(shù)據(jù)，放入新的數(shù)組中
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 方法的作用就對 哈希表進(jìn)行擴(kuò)容，但是我們應(yīng)該如何使用 resize 方法呢?
答案就是，我們可以在 put 和 delete 方法的最后判斷一下當(dāng)前哈希表的 loadFactor，比如：
- 當(dāng)
loadFactor大于0.75時，對哈希表進(jìn)行兩倍的擴(kuò)容 - 當(dāng)
loadFactor小于0.25時，對哈希表進(jìn)行兩倍的縮容
2. 修改 put 方法
put(key: string, value: T) {
// 1.根據(jù)key 獲取數(shù)組中對應(yīng)的索引值
const index = this.hashFunc(key, this.length);
console.log({ index });
// 2. 取出索引值對應(yīng)位置的數(shù)組
let bucket = this.storage[index];
// 3. 判斷 bucket 是否有值
if (!bucket) {
bucket = [];
this.storage[index] = bucket;
}
// 4. 確定已經(jīng)有一個數(shù)組了，但是數(shù)組中是否已經(jīng)存在 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. 如果上面的代碼沒有進(jìn)行覆蓋，那么在該位置進(jìn)行添加
if (!isUpdate) {
bucket.push([key, value]);
this.count++;
+ // 發(fā)現(xiàn) loadFactor 比例已經(jīng)大于 0.75，那么就直接擴(kuò)容
+ 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 進(jìn)行遍歷
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--;
+ // 發(fā)現(xiàn) loadFactor 比例已經(jīng)小于 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
相關(guān)推薦
- 2022-09-05 C語言深入淺出分析函數(shù)指針_C 語言
- 2022-11-05 pytest官方文檔解讀之安裝和使用插件的方法_python
- 2022-11-09 SQL語句過濾條件放在on與where子句中的區(qū)別和聯(lián)系淺析_MsSql
- 2023-05-19 Flutter?枚舉值enum和int互相轉(zhuǎn)化總結(jié)_Android
- 2022-07-13 Andorid 自定義 View - 自定義屬性 - 屬性重復(fù)導(dǎo)致沖突
- 2022-09-20 以SortedList為例詳解Python的defaultdict對象使用自定義類型的方法_pyth
- 2022-06-10 Docker部署springboot項(xiàng)目到騰訊云的實(shí)現(xiàn)步驟_docker
- 2024-03-10 @Controller、@Service和@Repository注解詳解
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細(xì)win安裝深度學(xué)習(xí)環(huán)境2025年最新版（
- Linux 中運(yùn)行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎(chǔ)操作-- 運(yùn)算符，流程控制 Flo
- 1. Int 和Integer 的區(qū)別，Jav
- spring @retryable不生效的一種
- Spring Security之認(rèn)證信息的處理
- Spring Security之認(rèn)證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權(quán)
- redisson分布式鎖中waittime的設(shè)
- maven:解決release錯誤：Artif
- restTemplate使用總結(jié)
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實(shí)現(xiàn)加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務(wù)發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結(jié)構(gòu)-簡單動態(tài)字符串（SD
- arthas操作spring被代理目標(biāo)對象命令
- Spring中的單例模式應(yīng)用詳解
- 聊聊消息隊(duì)列，發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠(yuǎn)程分支
提供CDN加速