當前位置：
首頁 >
前端技术
> javascript
>内容正文
javascript
【从蛋壳到满天飞】JS 数据结构解析和算法实现-哈希表
生活随笔
收集整理的這篇文章主要介紹了
【从蛋壳到满天飞】JS 数据结构解析和算法实现-哈希表
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
前言
【從蛋殼到滿天飛】JS 數(shù)據(jù)結(jié)構(gòu)解析和算法實現(xiàn)，全部文章大概的內(nèi)容如下： Arrays(數(shù)組)、Stacks(棧)、Queues(隊列)、LinkedList(鏈表)、Recursion(遞歸思想)、BinarySearchTree(二分搜索樹)、Set(集合)、Map(映射)、Heap(堆)、PriorityQueue(優(yōu)先隊列)、SegmentTree(線段樹)、Trie(字典樹)、UnionFind(并查集)、AVLTree(AVL 平衡樹)、RedBlackTree(紅黑平衡樹)、HashTable(哈希表)
源代碼有三個：ES6（單個單個的 class 類型的 js 文件） | JS + HTML（一個 js 配合一個 html）| JAVA (一個一個的工程)
全部源代碼已上傳 github，點擊我吧，光看文章能夠掌握兩成，動手敲代碼、動腦思考、畫圖才可以掌握八成。
本文章適合 對數(shù)據(jù)結(jié)構(gòu)想了解并且感興趣的人群，文章風格一如既往如此，就覺得手機上看起來比較方便，這樣顯得比較有條理，整理這些筆記加源碼，時間跨度也算將近半年時間了，希望對想學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的人或者正在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的人群有幫助。
哈希表
哈希表相對于之前實現(xiàn)的那些數(shù)據(jù)結(jié)構(gòu)來說
通過 leetcode 上的題目來看哈希表
哈希表是對于你所關(guān)注的內(nèi)容將它轉(zhuǎn)化成索引
這種情況下很多時候就不得不處理一個在哈希表中非常關(guān)鍵的問題
哈希表充分的體現(xiàn)了算法設(shè)計領(lǐng)域的經(jīng)典思想
對哈希表整體來說這個數(shù)組能開多大空間是非常重要的
哈希函數(shù)的設(shè)計
哈希表這種數(shù)據(jù)結(jié)構(gòu)
對于哈希表來說，關(guān)心的主要有兩部分內(nèi)容
哈希函數(shù)的設(shè)計
最一般的哈希函數(shù)設(shè)計原則
取模的數(shù)字選擇很重要，
浮點型的哈希函數(shù)設(shè)計
將浮點型的數(shù)據(jù)轉(zhuǎn)化為一個整數(shù)的索引，
在計算機中都 32 位或者 64 位的二進制表示，只不過計算機解析成了浮點數(shù)，
如果鍵是浮點型的話，那么就可以使用浮點型所存儲的這個空間，
把它當作是整型來進行處理，
也就是把這個浮點型所占用的 32 位空間或 64 位空間使用整數(shù)的方式來解析，
那么這篇空間同樣可以可以表示一個整數(shù)，
之后就可以將一個大的整數(shù)轉(zhuǎn)成整數(shù)相應(yīng)的方式，也就是取模的方式，
這樣就解決了浮點型的哈希函數(shù)的設(shè)計的問題
// // 單精度 // 8-bit 23-bit // 0 | 0 1 1 1 1 1 0 0 | 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 // 31 23 0// //雙進度 // 11-bit 52-bit // 0|011111111100|0100000000000000000000000000000000000000000000000000 // 63 52 0 復(fù)制代碼字符串的哈希函數(shù)設(shè)計
復(fù)合類型的哈希函數(shù)設(shè)計
哈希函數(shù)設(shè)計一般來說對任何數(shù)據(jù)類型都是將它轉(zhuǎn)換成整型來處理。
哈希函數(shù)的設(shè)計，通常要遵循三個原則
js 中 自定義 hashCode 方法
在 js 中自定義數(shù)據(jù)類型
Student
// Student class Student {constructor(grade, classId, studentName, studentScore) {this.name = studentName;this.score = studentScore;this.grade = grade;this.classId = classId;}//@Override hashCode 2018-11-25-jwlhashCode() {// 選擇進制const B = 31;// 計算hash值let hash = 0;hash = hash * B + this.getCode(this.name.toLowerCase());hash = hash * B + this.getCode(this.score);hash = hash * B + this.getCode(this.grade);hash = hash * B + this.getCode(this.classId);// 返回hash值return hash;}//@Override equals 2018-11-25-jwlequals(obj) {// 三重判斷if (!obj) return false;if (this === obj) return true;if (this.valueOf() !== obj.valueOf()) return false;// 對屬性進行判斷return (this.name === obj.name &&this.score === obj.score &&this.grade === obj.grade &&this.classId === obj.classId);}// 拆分字符生成數(shù)字 -getCode(s) {s = s + '';let result = 0;// 遍歷字符 計算結(jié)果for (const c of s) result += c.charCodeAt(0);// 返回結(jié)果return result;}//@Override toString 2018-10-19-jwltoString() {let studentInfo = `Student(name: ${this.name}, score: ${this.score})`;return studentInfo;} } 復(fù)制代碼Main
// main 函數(shù) class Main {constructor() {// var s = "leetcode";// this.show(new Solution().firstUniqChar(s) + " =====> 返回 0.");// var s = "loveleetcode";// this.show(new Solution().firstUniqChar(s) + " =====> 返回 2.");const jwl = new Student(10, 4, 'jwl', 99);this.show(jwl.hashCode());console.log(jwl.hashCode());const jwl2 = new Student(10, 4, 'jwl', 99);this.show(jwl2.hashCode());console.log(jwl2.hashCode());}// 將內(nèi)容顯示在頁面上show(content) {document.body.innerHTML += `${content}<br /><br />`;}// 展示分割線alterLine(title) {let line = `--------------------${title}----------------------`;console.log(line);document.body.innerHTML += `${line}<br /><br />`;} }// 頁面加載完畢 window.onload = function() {// 執(zhí)行主函數(shù)new Main(); }; 復(fù)制代碼哈希沖突的處理-鏈地址法(Seperate Chaining)
實現(xiàn)自己的哈希表
代碼示例
MyHashTable
// 自定義的hash生成類。 class MyHash {constructor() {this.store = new Map();}// 生成hashhashCode(key) {let hash = this.store.get(key);if (hash !== undefined) return hash;else {// 如果 這個hash沒有進行保存 就生成，并且記錄let hash = this.calcHashTwo(key);// 記錄this.store.set(key, hash);// 返回hashreturn hash;}}// 得到的數(shù)字比較小 六七位數(shù) 以下 輔助函數(shù)：生成hash -calcHashOne(key) {// 生成hash 隨機小數(shù) * 當前日期毫秒 * 隨機小數(shù)let hash = Math.random() * Date.now() * Math.random();// hash 取小數(shù)部分的字符串hash = hash.toString().replace(/^\d*\.\d*?([1-9]+)$/, '$1');hash = parseInt(hash); // 取整return hash;}// 得到的數(shù)字很大 十幾位數(shù) 左右 輔助函數(shù)：生成hash -calcHashTwo(key) {// 生成hash 隨機小數(shù) * 當前日期毫秒 * 隨機小數(shù)let hash = Math.random() * Date.now() * Math.random();// hash 向下取整hash = Math.floor(hash);return hash;} }class MyHashTableBySystem {constructor(M = 97) {this.M = M; // 空間大小this.size = 0; // 實際元素個數(shù)this.hashTable = new Array(M); // 哈希表this.hashCalc = new MyHash(); // 哈希值計算// 初始化哈希表for (var i = 0; i < M; i++) {// this.hashTable[i] = new MyAVLTree();this.hashTable[i] = new Map();}}// 根據(jù)key生成 哈希表索引hash(key) {// 獲取哈希值let hash = this.hashCalc.hashCode(key);// 對哈希值轉(zhuǎn)換為32位的整數(shù) 再進行取模運算return (hash & 0x7fffffff) % this.M;}// 獲取實際存儲的元素個數(shù)getSize() {return this.size;}// 添加元素add(key, value) {const map = this.hashTable[this.hash(key)];// 如果存在就覆蓋if (map.has(key)) map.set(key, value);else {// 不存在就添加map.set(key, value);this.size++;}}// 刪除元素remove(key) {const map = this.hashTable[this.hash(key)];let value = null;// 存在就刪除if (map.has(key)) {value = map.delete(key);this.size--;}return value;}// 修改操作set(key, value) {const map = this.hashTable[this.hash(key)];if (!map.has(key)) throw new Error(key + " doesn't exist!");map.set(key, value);}// 查找是否存在contains(key) {return this.hashTable[this.hash(key)].has(key);}// 查找操作get(key) {return this.hashTable[this.hash(key)].get(key);} }// 自定義的哈希表 HashTable 基于使系統(tǒng)的Map 底層是哈希表+紅黑樹 // 自定義的哈希表 HashTable 基于自己的AVL樹 class MyHashTableByAVLTree {constructor(M = 97) {this.M = M; // 空間大小this.size = 0; // 實際元素個數(shù)this.hashTable = new Array(M); // 哈希表this.hashCalc = new MyHash(); // 哈希值計算// 初始化哈希表for (var i = 0; i < M; i++) {// this.hashTable[i] = new MyAVLTree();this.hashTable[i] = new MyAVLTreeMap();}}// 根據(jù)key生成 哈希表索引hash(key) {// 獲取哈希值let hash = this.hashCalc.hashCode(key);// 對哈希值轉(zhuǎn)換為32位的整數(shù) 再進行取模運算return (hash & 0x7fffffff) % this.M;}// 獲取實際存儲的元素個數(shù)getSize() {return this.size;}// 添加元素add(key, value) {const map = this.hashTable[this.hash(key)];// 如果存在就覆蓋if (map.contains(key)) map.set(key, value);else {// 不存在就添加map.add(key, value);this.size++;}}// 刪除元素remove(key) {const map = this.hashTable[this.hash(key)];let value = null;// 存在就刪除if (map.contains(key)) {value = map.remove(key);this.size--;}return value;}// 修改操作set(key, value) {const map = this.hashTable[this.hash(key)];if (!map.contains(key)) throw new Error(key + " doesn't exist!");map.set(key, value);}// 查找是否存在contains(key) {return this.hashTable[this.hash(key)].contains(key);}// 查找操作get(key) {return this.hashTable[this.hash(key)].get(key);} } 復(fù)制代碼Main
// main 函數(shù) class Main {constructor() {this.alterLine('HashTable Comparison Area');const n = 2000000;const random = Math.random;let arrNumber = new Array(n);// 循環(huán)添加隨機數(shù)的值for (let i = 0; i < n; i++) arrNumber[i] = Math.floor(n * random());const hashTable = new MyHashTableByAVLTree(1572869);const hashTable1 = new MyHashTableBySystem(1572869);const performanceTest1 = new PerformanceTest();const that = this;const hashTableInfo = performanceTest1.testCustomFn(function() {// 添加for (const word of arrNumber)hashTable.add(word, String.fromCharCode(word));that.show('size : ' + hashTable.getSize());console.log('size : ' + hashTable.getSize());// 刪除for (const word of arrNumber) hashTable.remove(word);// 查找for (const word of arrNumber)if (hashTable.contains(word))throw new Error("doesn't remove ok.");});// 總毫秒數(shù)：console.log(hashTableInfo);console.log(hashTable);this.show(hashTableInfo);const hashTableInfo1 = performanceTest1.testCustomFn(function() {// 添加for (const word of arrNumber)hashTable1.add(word, String.fromCharCode(word));that.show('size : ' + hashTable1.getSize());console.log('size : ' + hashTable1.getSize());// 刪除for (const word of arrNumber) hashTable1.remove(word);// 查找for (const word of arrNumber)if (hashTable1.contains(word))throw new Error("doesn't remove ok.");});// 總毫秒數(shù)：console.log(hashTableInfo1);console.log(hashTable1);this.show(hashTableInfo1);}// 將內(nèi)容顯示在頁面上show(content) {document.body.innerHTML += `${content}<br /><br />`;}// 展示分割線alterLine(title) {let line = `--------------------${title}----------------------`;console.log(line);document.body.innerHTML += `${line}<br /><br />`;} }// 頁面加載完畢 window.onload = function() {// 執(zhí)行主函數(shù)new Main(); }; 復(fù)制代碼哈希表的動態(tài)空間處理與復(fù)雜度分析
哈希表的時間復(fù)雜度
哈希表的動態(tài)空間處理
代碼示例
MyHashTable
// 自定義的hash生成類。 class MyHash {constructor() {this.store = new Map();}// 生成hashhashCode(key) {let hash = this.store.get(key);if (hash !== undefined) return hash;else {// 如果 這個hash沒有進行保存 就生成，并且記錄let hash = this.calcHashTwo(key);// 記錄this.store.set(key, hash);// 返回hashreturn hash;}}// 得到的數(shù)字比較小 六七位數(shù) 以下 輔助函數(shù)：生成hash -calcHashOne(key) {// 生成hash 隨機小數(shù) * 當前日期毫秒 * 隨機小數(shù)let hash = Math.random() * Date.now() * Math.random();// hash 取小數(shù)部分的字符串hash = hash.toString().replace(/^\d*\.\d*?([1-9]+)$/, '$1');hash = parseInt(hash); // 取整return hash;}// 得到的數(shù)字很大 十幾位數(shù) 左右 輔助函數(shù)：生成hash -calcHashTwo(key) {// 生成hash 隨機小數(shù) * 當前日期毫秒 * 隨機小數(shù)let hash = Math.random() * Date.now() * Math.random();// hash 向下取整hash = Math.floor(hash);return hash;} }class MyHashTableBySystem {constructor(M = 97) {this.M = M; // 空間大小this.size = 0; // 實際元素個數(shù)this.hashTable = new Array(M); // 哈希表this.hashCalc = new MyHash(); // 哈希值計算// 初始化哈希表for (var i = 0; i < M; i++) {// this.hashTable[i] = new MyAVLTree();this.hashTable[i] = new Map();}}// 根據(jù)key生成 哈希表索引hash(key) {// 獲取哈希值let hash = this.hashCalc.hashCode(key);// 對哈希值轉(zhuǎn)換為32位的整數(shù) 再進行取模運算return (hash & 0x7fffffff) % this.M;}// 獲取實際存儲的元素個數(shù)getSize() {return this.size;}// 添加元素add(key, value) {const map = this.hashTable[this.hash(key)];// 如果存在就覆蓋if (map.has(key)) map.set(key, value);else {// 不存在就添加map.set(key, value);this.size++;}}// 刪除元素remove(key) {const map = this.hashTable[this.hash(key)];let value = null;// 存在就刪除if (map.has(key)) {value = map.delete(key);this.size--;}return value;}// 修改操作set(key, value) {const map = this.hashTable[this.hash(key)];if (!map.has(key)) throw new Error(key + " doesn't exist!");map.set(key, value);}// 查找是否存在contains(key) {return this.hashTable[this.hash(key)].has(key);}// 查找操作get(key) {return this.hashTable[this.hash(key)].get(key);} }// 自定義的哈希表 HashTable // 自定義的哈希表 HashTable class MyHashTableByAVLTree {constructor(M = 97) {this.M = M; // 空間大小this.size = 0; // 實際元素個數(shù)this.hashTable = new Array(M); // 哈希表this.hashCalc = new MyHash(); // 哈希值計算// 初始化哈希表for (var i = 0; i < M; i++) {// this.hashTable[i] = new MyAVLTree();this.hashTable[i] = new MyAVLTreeMap();}// 設(shè)定擴容的上邊界this.upperTolerance = 10;// 設(shè)定縮容的下邊界this.lowerTolerance = 2;// 初始容量大小為 97this.initCapcity = 97;}// 根據(jù)key生成 哈希表索引hash(key) {// 獲取哈希值let hash = this.hashCalc.hashCode(key);// 對哈希值轉(zhuǎn)換為32位的整數(shù) 再進行取模運算return (hash & 0x7fffffff) % this.M;}// 獲取實際存儲的元素個數(shù)getSize() {return this.size;}// 添加元素add(key, value) {const map = this.hashTable[this.hash(key)];// 如果存在就覆蓋if (map.contains(key)) map.set(key, value);else {// 不存在就添加map.add(key, value);this.size++;// 平均元素個數(shù) 大于等于 當前容量的10倍// 擴容就翻倍if (this.size >= this.upperTolerance * this.M)this.resize(2 * this.M);}}// 刪除元素remove(key) {const map = this.hashTable[this.hash(key)];let value = null;// 存在就刪除if (map.contains(key)) {value = map.remove(key);this.size--;// 平均元素個數(shù) 小于容量的2倍 當然無論怎么縮容，縮容之后都要大于初始容量if (this.size < this.lowerTolerance * this.M &&this.M / 2 > this.initCapcity)this.resize(Math.floor(this.M / 2));}return value;}// 修改操作set(key, value) {const map = this.hashTable[this.hash(key)];if (!map.contains(key)) throw new Error(key + " doesn't exist!");map.set(key, value);}// 查找是否存在contains(key) {return this.hashTable[this.hash(key)].contains(key);}// 查找操作get(key) {return this.hashTable[this.hash(key)].get(key);}// 重置空間大小resize(newM) {// 初始化新空間const newHashTable = new Array(newM);for (var i = 0; i < newM; i++) newHashTable[i] = new MyAVLTree();const oldM = this.M;this.M = newM;// 方式一// let map;// let keys;// for (var i = 0; i < oldM; i++) {// // 獲取所有實例// map = this.hashTable[i];// keys = map.getKeys();// // 遍歷每一對鍵值對 實例// for(const key of keys)// newHashTable[this.hash(key)].add(key, map.get(key));// }// 方式二let etities;for (var i = 0; i < oldM; i++) {etities = this.hashTable[i].getEntitys();for (const entity of etities)newHashTable[this.hash(entity.key)].add(entity.key,entity.value);}// 重新設(shè)置當前hashTablethis.hashTable = newHashTable;} } 復(fù)制代碼Main
// main 函數(shù) class Main {constructor() {this.alterLine('HashTable Comparison Area');const n = 2000000;const random = Math.random;let arrNumber = new Array(n);// 循環(huán)添加隨機數(shù)的值for (let i = 0; i < n; i++) arrNumber[i] = Math.floor(n * random());this.alterLine('HashTable Comparison Area');const hashTable = new MyHashTableByAVLTree();const hashTable1 = new MyHashTableBySystem();const performanceTest1 = new PerformanceTest();const that = this;const hashTableInfo = performanceTest1.testCustomFn(function() {// 添加for (const word of arrNumber)hashTable.add(word, String.fromCharCode(word));that.show('size : ' + hashTable.getSize());console.log('size : ' + hashTable.getSize());// 刪除for (const word of arrNumber) hashTable.remove(word);// 查找for (const word of arrNumber)if (hashTable.contains(word))throw new Error("doesn't remove ok.");});// 總毫秒數(shù)：console.log('HashTableByAVLTree' + ':' + hashTableInfo);console.log(hashTable);this.show('HashTableByAVLTree' + ':' + hashTableInfo);const hashTableInfo1 = performanceTest1.testCustomFn(function() {// 添加for (const word of arrNumber)hashTable1.add(word, String.fromCharCode(word));that.show('size : ' + hashTable1.getSize());console.log('size : ' + hashTable1.getSize());// 刪除for (const word of arrNumber) hashTable1.remove(word);// 查找for (const word of arrNumber)if (hashTable1.contains(word))throw new Error("doesn't remove ok.");});// 總毫秒數(shù)：console.log('HashTableBySystem' + ':' + hashTableInfo1);console.log(hashTable1);this.show('HashTableBySystem' + ':' + hashTableInfo1);}// 將內(nèi)容顯示在頁面上show(content) {document.body.innerHTML += `${content}<br /><br />`;}// 展示分割線alterLine(title) {let line = `--------------------${title}----------------------`;console.log(line);document.body.innerHTML += `${line}<br /><br />`;} }// 頁面加載完畢 window.onload = function() {// 執(zhí)行主函數(shù)new Main(); }; 復(fù)制代碼哈希表更復(fù)雜的動態(tài)空間處理方法
哈希表的復(fù)雜度分析
更復(fù)雜的動態(tài)空間處理方法
代碼示例
MyHashTable
// 自定義的hash生成類。 class MyHash {constructor() {this.store = new Map();}// 生成hashhashCode(key) {let hash = this.store.get(key);if (hash !== undefined) return hash;else {// 如果 這個hash沒有進行保存 就生成，并且記錄let hash = this.calcHashTwo(key);// 記錄this.store.set(key, hash);// 返回hashreturn hash;}}// 得到的數(shù)字比較小 六七位數(shù) 以下 輔助函數(shù)：生成hash -calcHashOne(key) {// 生成hash 隨機小數(shù) * 當前日期毫秒 * 隨機小數(shù)let hash = Math.random() * Date.now() * Math.random();// hash 取小數(shù)部分的字符串hash = hash.toString().replace(/^\d*\.\d*?([1-9]+)$/, '$1');hash = parseInt(hash); // 取整return hash;}// 得到的數(shù)字很大 十幾位數(shù) 左右 輔助函數(shù)：生成hash -calcHashTwo(key) {// 生成hash 隨機小數(shù) * 當前日期毫秒 * 隨機小數(shù)let hash = Math.random() * Date.now() * Math.random();// hash 向下取整hash = Math.floor(hash);return hash;} }class MyHashTableBySystem {constructor(M = 97) {this.M = M; // 空間大小this.size = 0; // 實際元素個數(shù)this.hashTable = new Array(M); // 哈希表this.hashCalc = new MyHash(); // 哈希值計算// 初始化哈希表for (var i = 0; i < M; i++) {// this.hashTable[i] = new MyAVLTree();this.hashTable[i] = new Map();}}// 根據(jù)key生成 哈希表索引hash(key) {// 獲取哈希值let hash = this.hashCalc.hashCode(key);// 對哈希值轉(zhuǎn)換為32位的整數(shù) 再進行取模運算return (hash & 0x7fffffff) % this.M;}// 獲取實際存儲的元素個數(shù)getSize() {return this.size;}// 添加元素add(key, value) {const map = this.hashTable[this.hash(key)];// 如果存在就覆蓋if (map.has(key)) map.set(key, value);else {// 不存在就添加map.set(key, value);this.size++;}}// 刪除元素remove(key) {const map = this.hashTable[this.hash(key)];let value = null;// 存在就刪除if (map.has(key)) {value = map.delete(key);this.size--;}return value;}// 修改操作set(key, value) {const map = this.hashTable[this.hash(key)];if (!map.has(key)) throw new Error(key + " doesn't exist!");map.set(key, value);}// 查找是否存在contains(key) {return this.hashTable[this.hash(key)].has(key);}// 查找操作get(key) {return this.hashTable[this.hash(key)].get(key);} }// 自定義的哈希表 HashTable // 基于系統(tǒng)的哈希表，用來測試 // 自定義的哈希表 HashTable // 基于自己實現(xiàn)的AVL樹 class MyHashTableByAVLTree {constructor() {// 設(shè)定擴容的上邊界this.upperTolerance = 10;// 設(shè)定縮容的下邊界this.lowerTolerance = 2;// 哈希表合理的素數(shù)表this.capacity = [53,97,193,389,769,1543,3079,6151,12289,24593,49157,98317,196613,393241,786433,1572869,3145739,6291469,12582917,25165843,50331653,100663319,201326611,402653189,805306457,1610612741];// 初始容量的索引this.capacityIndex = 0;this.M = this.capacity[this.capacityIndex]; // 空間大小this.size = 0; // 實際元素個數(shù)this.hashTable = new Array(this.M); // 哈希表this.hashCalc = new MyHash(); // 哈希值計算// 初始化哈希表for (var i = 0; i < this.M; i++) {// this.hashTable[i] = new MyAVLTree();this.hashTable[i] = new MyAVLTreeMap();}}// 根據(jù)key生成 哈希表索引hash(key) {// 獲取哈希值let hash = this.hashCalc.hashCode(key);// 對哈希值轉(zhuǎn)換為32位的整數(shù) 再進行取模運算return (hash & 0x7fffffff) % this.M;}// 獲取實際存儲的元素個數(shù)getSize() {return this.size;}// 添加元素add(key, value) {const map = this.hashTable[this.hash(key)];// 如果存在就覆蓋if (map.contains(key)) map.set(key, value);else {// 不存在就添加map.add(key, value);this.size++;// 平均元素個數(shù) 大于等于 當前容量的10倍，同時防止索引越界// 就以哈希表合理的素數(shù)表 為標準進行 索引的推移if (this.size >= this.upperTolerance * this.M &&this.capacityIndex + 1 < this.capacity.length)this.resize(this.capacity[++this.capacityIndex]);}}// 刪除元素remove(key) {const map = this.hashTable[this.hash(key)];let value = null;// 存在就刪除if (map.contains(key)) {value = map.remove(key);this.size--;// 平均元素個數(shù) 小于容量的2倍 當然無論怎么縮容，索引都不能越界if (this.size < this.lowerTolerance * this.M &&this.capacityIndex > 0)this.resize(this.capacity[--this.capacityIndex]);}return value;}// 修改操作set(key, value) {const map = this.hashTable[this.hash(key)];if (!map.contains(key)) throw new Error(key + " doesn't exist!");map.set(key, value);}// 查找是否存在contains(key) {return this.hashTable[this.hash(key)].contains(key);}// 查找操作get(key) {return this.hashTable[this.hash(key)].get(key);}// 重置空間大小resize(newM) {// 初始化新空間const newHashTable = new Array(newM);for (var i = 0; i < newM; i++) newHashTable[i] = new MyAVLTree();const oldM = this.M;this.M = newM;// 方式一// let map;// let keys;// for (var i = 0; i < oldM; i++) {// // 獲取所有實例// map = this.hashTable[i];// keys = map.getKeys();// // 遍歷每一對鍵值對 實例// for(const key of keys)// newHashTable[this.hash(key)].add(key, map.get(key));// }// 方式二let etities;for (var i = 0; i < oldM; i++) {etities = this.hashTable[i].getEntitys();for (const entity of etities)newHashTable[this.hash(entity.key)].add(entity.key,entity.value);}// 重新設(shè)置當前hashTablethis.hashTable = newHashTable;} } 復(fù)制代碼Main
// main 函數(shù) class Main {constructor() {this.alterLine('HashTable Comparison Area');const n = 2000000;const random = Math.random;let arrNumber = new Array(n);// 循環(huán)添加隨機數(shù)的值for (let i = 0; i < n; i++) arrNumber[i] = Math.floor(n * random());this.alterLine('HashTable Comparison Area');const hashTable = new MyHashTableByAVLTree();const hashTable1 = new MyHashTableBySystem();const performanceTest1 = new PerformanceTest();const that = this;const hashTableInfo = performanceTest1.testCustomFn(function() {// 添加for (const word of arrNumber)hashTable.add(word, String.fromCharCode(word));that.show('size : ' + hashTable.getSize());console.log('size : ' + hashTable.getSize());// 刪除for (const word of arrNumber) hashTable.remove(word);// 查找for (const word of arrNumber)if (hashTable.contains(word))throw new Error("doesn't remove ok.");});// 總毫秒數(shù)：13249console.log('HashTableByAVLTree' + ':' + hashTableInfo);console.log(hashTable);this.show('HashTableByAVLTree' + ':' + hashTableInfo);const hashTableInfo1 = performanceTest1.testCustomFn(function() {// 添加for (const word of arrNumber)hashTable1.add(word, String.fromCharCode(word));that.show('size : ' + hashTable1.getSize());console.log('size : ' + hashTable1.getSize());// 刪除for (const word of arrNumber) hashTable1.remove(word);// 查找for (const word of arrNumber)if (hashTable1.contains(word))throw new Error("doesn't remove ok.");});// 總毫秒數(shù)：5032console.log('HashTableBySystem' + ':' + hashTableInfo1);console.log(hashTable1);this.show('HashTableBySystem' + ':' + hashTableInfo1);}// 將內(nèi)容顯示在頁面上show(content) {document.body.innerHTML += `${content}<br /><br />`;}// 展示分割線alterLine(title) {let line = `--------------------${title}----------------------`;console.log(line);document.body.innerHTML += `${line}<br /><br />`;} }// 頁面加載完畢 window.onload = function() {// 執(zhí)行主函數(shù)new Main(); }; 復(fù)制代碼哈希表的更多話題
更多哈希沖突的處理方法
總結(jié)
以上是生活随笔為你收集整理的【从蛋壳到满天飞】JS 数据结构解析和算法实现-哈希表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 2018-2019 Exp2 后门原理与
- 下一篇： [JVM]常用JVM工具使用