【從蛋殼到滿天飛】JS 資料結構解析和演算法實現-雜湊表

摘要： 【從蛋殼到滿天飛】JS 資料結構解析和演算法實現，全部文章大概的內容如下： Arrays(陣列)、Stacks(棧)、Queues(佇列)、LinkedList(連結串列)、Recursion(遞迴思想)、BinarySearchTree(二分搜尋樹)、Set(集合)、Map(對映)、Heap...

【從蛋殼到滿天飛】JS 資料結構解析和演算法實現，全部文章大概的內容如下： Arrays(陣列)、Stacks(棧)、Queues(佇列)、LinkedList(連結串列)、Recursion(遞迴思想)、BinarySearchTree(二分搜尋樹)、Set(集合)、Map(對映)、Heap(堆)、PriorityQueue(優先佇列)、SegmentTree(線段樹)、Trie(字典樹)、UnionFind(並查集)、AVLTree(AVL 平衡樹)、RedBlackTree(紅黑平衡樹)、HashTable(雜湊表)

原始碼有三個：ES6（單個單個的 class 型別的 js 檔案） | JS + HTML（一個 js 配合一個 html）| JAVA (一個一個的工程)

全部原始碼已上傳 github，點選我吧 ，光看文章能夠掌握兩成，動手敲程式碼、動腦思考、畫圖才可以掌握八成。

本文章適合 對資料結構想了解並且感興趣的人群，文章風格一如既往如此，就覺得手機上看起來比較方便，這樣顯得比較有條理，整理這些筆記加原始碼，時間跨度也算將近半年時間了，希望對想學習資料結構的人或者正在學習資料結構的人群有幫助。

雜湊表

1. 雜湊表相對於之前實現的那些資料結構來說

   1. 雜湊表是一個相對比較簡單的資料結構，
   2. 對於雜湊表來說也有許多相對比較複雜的研究，
   3. 不過對於這些研究大多數都是比較偏數學的，
   4. 對於普通的軟體工程軟體開發來講，
   5. 使用雜湊表瞭解雜湊表的底層實現，並不需要知道那麼多的複雜深奧的內容，

2. 通過 leetcode 上的題目來看雜湊表

   1. leetcode 上第 387 號問題，在解決這個問題的時候，
   2. 開闢的一個 26 個空間的陣列就是雜湊表，
   3. 實際上真正想做是每一個字元和一個數字之間進行一個對映的關係，
   4. 這個數字是這個字元在字串中出現的頻率，
   5. 使用一個數組就可以解決這個問題，
   6. 那是因為將每一個字元都和一個索引進行了對應，
   7. 之後直接用這個索引去陣列中尋找相應的對應資訊，也就是對映的內容，
   8. 二十六的字元對應的索引就是陣列中的索引下標，
   9. 當每一個字元與索引對應了，
   10. 那麼對這個字元所對應的對應的內容增刪改查都是 O(1)級別的，
   11. 那麼這就是雜湊表這種資料結構的巨大優勢，
   12. 它的本質其實就是將你真正關心的內容轉換成一個索引，
   13. 如字元對應的內容轉換成一個索引，然後直接使用陣列來儲存相應的內容，
   14. 由於陣列本身是支援隨機訪問的，
   15. 所以可以使用 O(1)的時間複雜度來完成各項操作，
   16. 這就是雜湊表。

   // 答題
   class Solution {
   // leetcode 387. 字串中的第一個唯一字元
   firstUniqChar(s) {
   /**
   * @param {string} s
   * @return {number}
   */
   var firstUniqChar = function(s) {
   const hashTable = new Array(26);
   
   for (var i = 0; i < hashTable.length; i++) hashTable[i] = 0;
   
   for (const c of s) hashTable[c.charCodeAt(0) - 97]++;
   
   for (var i = 0; i < hashTable.length; i++)
   if (hashTable[s[i].charCodeAt(0) - 97] === 1) return i;
   
   return -1;
   };
   /**
   * @param {string} s
   * @return {number}
   */
   var firstUniqChar = function(s) {
   const hashTable = new Array(26);
   const letterTable = {};
   
   for (var i = 0; i < hashTable.length; i++) {
   letterTable[String.fromCharCode(i + 97)] = i;
   hashTable[i] = 0;
   }
   
   for (const c of s) hashTable[letterTable[c]]++;
   
   for (var i = 0; i < s.length; i++)
   if (hashTable[letterTable[s[i]]] === 1) return i;
   
   return -1;
   };
   
   return firstUniqChar(s);
   }
   }
   複製程式碼

3. 雜湊表是對於你所關注的內容將它轉化成索引

   fn(char1) = char1 -'a'
   char1 -'a'
   編號-1
   鍵
   

4. 這種情況下很多時候就不得不處理一個在雜湊表中非常關鍵的問題

   1. 兩個不同的鍵通過雜湊函式它能對應同樣一個索引，
   2. 這就是雜湊衝突，
   3. 所以在雜湊表上的操作也就是在解決這種雜湊衝突，
   4. 如果設計的雜湊函式非常好都是一一對應的，
   5. 那麼對雜湊表的操作也會非常的簡單，
   6. 不過對於更一般的情況，在雜湊表上的操作主要考慮怎麼解決雜湊衝突問題。

5. 雜湊表充分的體現了演算法設計領域的經典思想

   O(1)
   O(n)
   O(1)
   O(n)
   

6. 對雜湊表整體來說這個陣列能開多大空間是非常重要的

   1. 雖然如此，雜湊表整體，雜湊函式的設計依然是非常重要的，
   2. 很多資料型別本身並不能非常自然的和一個整型索引相對應，
   3. 所以必須想辦法讓諸如字串、浮點數、複合型別日期
   4. 能夠跟一個整型把它當作索引來對應。
   5. 就算你能開無限的空間，但是把身份證號作為索引，
   6. 但是 18 位以下及 18 位以上的空間全部都是浪費掉的，
   7. 所以對於雜湊表來說，還希望，
   8. 對於每一個鍵 通過雜湊函式得到索引 後，
   9. 這個索引的分佈越均勻越好。

雜湊函式的設計

1. 雜湊表這種資料結構

   1. 其實就是把所關心的鍵通過雜湊函式轉化成一個索引，
   2. 然後直接把內容存到一個數組中就好了。

2. 對於雜湊表來說，關心的主要有兩部分內容

   1. 第一部分就是雜湊函式的設計，
   2. 第二部分就是解決雜湊函式生成的索引相同的衝突，
   3. 也就是解決雜湊衝突如何處理的問題。

3. 雜湊函式的設計

   1. 鍵 通過雜湊函式得到的索引 分佈越均勻越好。
   2. 雖然很好理解，但是想要達到這樣的條件是非常難的，
   3. 對於資料的儲存的資料型別是五花八門，
   4. 所以對於一些特殊領域，有特殊領域的雜湊函式設計方式，
   5. 甚至有專門的論文來討論如何設計雜湊函式，
   6. 也就說明雜湊函式的設計其實是非常複雜的。

4. 最一般的雜湊函式設計原則

   -100~100
   0~200
   mod 10000
   mod 1000000
   

5. 取模的數字選擇很重要，

   http://planetmath.org/goodhashtableprimes
   

   // 10 % 4 ---> 210 % 7 --->3
   // 20 % 4 ---> 020 % 7 --->6
   // 30 % 4 ---> 230 % 7 --->2
   // 40 % 4 ---> 040 % 7 --->4
   // 50 % 4 ---> 250 % 7 --->1
   複製程式碼

6. 浮點型的雜湊函式設計

   1. 將浮點型的資料轉化為一個整數的索引，

   2. 在計算機中都 32 位或者 64 位的二進位制表示，只不過計算機解析成了浮點數，

   3. 如果鍵是浮點型的話，那麼就可以使用浮點型所儲存的這個空間，

   4. 把它當作是整型來進行處理，

   5. 也就是把這個浮點型所佔用的 32 位空間或 64 位空間使用整數的方式來解析，

   6. 那麼這篇空間同樣可以可以表示一個整數，

   7. 之後就可以將一個大的整數轉成整數相應的方式，也就是取模的方式，

   8. 這樣就解決了浮點型的雜湊函式的設計的問題

      // // 單精度
      //8-bit23-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
      // 31230
      
      // //雙進度
      //11-bit52-bit
      // 0|011111111100|0100000000000000000000000000000000000000000000000000
      // 63520
      複製程式碼

7. 字串的雜湊函式設計

   166 = 1 * 10^2 + 6 * 10^1 + 6 * 10^0
   code = c * 26^3 + o * 26^2 + d * 26^1 + e * 26^0
   code = c * B^3 + o * B^2 + d * B^1 + e * B^0
   hash(code) = (c * B^3 + o * B^2 + d * B^1 + e * B^0) % M
   hash(code) = ((((c * B) + o) * B + d) * B + e) % M
   hash(code) = ((((c % M) * B + o) % M * B + d) % M * B + e) % M
   

   //hash(code) = ((((c % M) * B + o) % M * B + d) % M * B + e) % M
   
   // 上面的公式中 ((((c % M) * B + o) % M * B + d) % M * B + e) % M
   // 對應下面的程式碼，只需要一重for迴圈即可，最終的到的就是整個字串的雜湊值
   let s = 'code';
   let hash = 0;
   for (let i = 0; i < s.length; i++) hash = (hash * B + s.charAt(i)) % M;
   複製程式碼

8. 複合型別的雜湊函式設計

   hash(code) = ((((c % M) * B + o) % M * B + d) % M * B + e) % M
   Date：year，month，day，
   hash(date) = ((((date.year%M) * B + date.month) % M * B + date.day) % M * B + e) % M
   

9. 雜湊函式設計一般來說對任何資料型別都是將它轉換成整型來處理。

   1. 轉換成整型並不是雜湊函式設計的唯一方法，
   2. 只不過這是一個比較普通比較常用比較通用的一種方法，
   3. 在很多特殊的領域有很多相關的論文去講更多的雜湊函式設計的方法。

雜湊函式的設計，通常要遵循三個原則

1. 一致性：如果 a==b，則 hash(a)==hash(b)。
   1. 如果兩個鍵相等，那麼扔進雜湊函式之後得到的值也一定要相等，
   2. 但是對於雜湊函式來說反過來是不一定成立的，
   3. 同樣的一個雜湊值很有可能對應了兩個不同的資料或者不同的鍵，
   4. 這就是所謂的雜湊衝突的情況。
2. 高效性：計算高效簡便。
   1. 使用雜湊表就是為了能夠高效的儲存，
   2. 那麼在使用雜湊函式計算的時候耗費太多的效能那麼就太得不償失了。
3. 均勻性：雜湊值均勻分佈。
   1. 使用雜湊函式之後得到的索引值就應該儘量的均勻，
   2. 對於一般的整型可以通過模一個素數來讓它儘量的均勻，
   3. 這個條件雖然看起來很簡單，但是真正要滿足這個條件，
   4. 探究這個條件背後的數學性質還是很複雜的一個問題。

js 中 自定義 hashCode 方法

1. 在 js 中自定義資料型別

   1. 對於自己定義的複合型別，如學生類、日期型別，
   2. 你可以通過寫 hashCode 方法，
   3. 然後自己實現一下這個方法重新生成 hash 值。

2. 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-jwl
   hashCode() {
   // 選擇進位制
   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-jwl
   equals(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
   );
   }
   
   // 拆分字元生成數字 -
   getCode(s) {
   s = s + '';
   let result = 0;
   // 遍歷字元 計算結果
   for (const c of s) result += c.charCodeAt(0);
   
   // 返回結果
   return result;
   }
   
   //@Override toString 2018-10-19-jwl
   toString() {
   let studentInfo = `Student(name: ${this.name}, score: ${this.score})`;
   return studentInfo;
   }
   }
   複製程式碼

3. Main

   // main 函式
   class Main {
   constructor() {
   // vars = "leetcode";
   // this.show(new Solution().firstUniqChar(s) + " =====> 返回 0.");
   
   // vars = "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());
   }
   
   // 將內容顯示在頁面上
   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() {
   // 執行主函式
   new Main();
   };
   複製程式碼

雜湊衝突的處理-鏈地址法(Seperate Chaining)

1. 雜湊表的本質就是一個數組
   1. 對於一個雜湊表來說，對於一個整數求它的 hash 值的時候會對一個素數取模，
   2. 這個素數就是這個陣列的空間大小，也可以把它稱之為 M，
2. 在 強型別語言 中獲取到的 hash 值可能是一個負數，所以就需要進行處理一下

   (hashCode(k1) & 0x7fffffff) % M
   1111
   111
   0x7fffffff
   

3. 鏈地址法
   1. 根據元素的雜湊值計算出索引後，根據索引來雜湊表中的數組裡儲存資料，
   2. 如果索引相同的話，那麼就以連結串列的方式將新元素掛到陣列對應的位置中，
   3. 這樣就很好的解決了雜湊衝突的問題了，因為每一個位置都對應了一個鏈，
   4. 它的本質就是一個查詢表，查詢表的本質不一定是使用連結串列，
   5. 它的底層其實還可以使用樹結構如平衡樹結構，
   6. 對於雜湊表的陣列中每一個位置存的不是一個連結串列而是一個 Map，
   7. 通過雜湊值計算出索引後，根據索引找到陣列中對應的位置之後，
   8. 就可以把你要儲存的元素插入該位置的 紅黑樹 裡即可，
   9. 那麼這個 Map 本質就是一個 紅黑樹 Map 陣列，這是對映的形式，
   10. 如果你真正要實現的是一個集合，那麼也可以使用 紅黑樹 Set 陣列，
   11. 雜湊表的陣列中每一個位置存的都是一個查詢表，
   12. 只要這個資料結構適合作為查詢表就可以了，它是可以有不同的底層實現,
   13. 雜湊表的陣列中每一個位置也可以對應的是一個連結串列，
   14. 當資料規模比較小的時候，其實連結串列要比紅黑樹要快的，
   15. 資料規模比較小的時候使用紅黑樹可能更加耗費效能，如各種旋轉操作，
   16. 因為它要滿足紅黑樹的效能，所以反而會慢一些。

實現自己的雜湊表

1. 之前實現的樹結構中都需要進行比較
   1. 其中的鍵都需要實現 compare 這個用來比較兩個元素的方法，
   2. 因為需要通過鍵來進行比較，
   3. 對於雜湊表來說沒有這個要求，
   4. 這個 key 不需要實現這個方法。
2. 在雜湊表中儲存的元素都需要實現可以用來獲取 hashCode 的方法。
3. 對於雜湊表來說相應的開多少空間是非常重要的

   http://planetmath.org/goodhashtableprimes
   

程式碼示例

1. MyHashTable

   // 自定義的hash生成類。
   class MyHash {
   constructor() {
   this.store = new Map();
   }
   
   // 生成hash
   hashCode(key) {
   let hash = this.store.get(key);
   if (hash !== undefined) return hash;
   else {
   // 如果 這個hash沒有進行儲存 就生成，並且記錄
   let hash = this.calcHashTwo(key);
   
   // 記錄
   this.store.set(key, hash);
   
   // 返回hash
   return hash;
   }
   }
   
   // 得到的數字比較小 六七位數 以下輔助函式：生成hash -
   calcHashOne(key) {
   // 生成hash 隨機小數 * 當前日期毫秒 * 隨機小數
   let hash = Math.random() * Date.now() * Math.random();
   
   // hash 取小數部分的字串
   hash = hash.toString().replace(/^\d*\.\d*?([1-9]+)$/, '$1');
   
   hash = parseInt(hash); // 取整
   
   return hash;
   }
   
   // 得到的數字很大 十幾位數 左右輔助函式：生成hash -
   calcHashTwo(key) {
   // 生成hash 隨機小數 * 當前日期毫秒 * 隨機小數
   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; // 實際元素個數
   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();
   }
   }
   
   // 根據key生成 雜湊表索引
   hash(key) {
   // 獲取雜湊值
   let hash = this.hashCalc.hashCode(key);
   // 對雜湊值轉換為32位的整數再進行取模運算
   return (hash & 0x7fffffff) % this.M;
   }
   
   // 獲取實際儲存的元素個數
   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 基於使系統的Map 底層是雜湊表+紅黑樹
   // 自定義的雜湊表 HashTable 基於自己的AVL樹
   class MyHashTableByAVLTree {
   constructor(M = 97) {
   this.M = M; // 空間大小
   this.size = 0; // 實際元素個數
   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();
   }
   }
   
   // 根據key生成 雜湊表索引
   hash(key) {
   // 獲取雜湊值
   let hash = this.hashCalc.hashCode(key);
   // 對雜湊值轉換為32位的整數再進行取模運算
   return (hash & 0x7fffffff) % this.M;
   }
   
   // 獲取實際儲存的元素個數
   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);
   }
   }
   複製程式碼

2. Main

   // main 函式
   class Main {
   constructor() {
   this.alterLine('HashTable Comparison Area');
   const n = 2000000;
   
   const random = Math.random;
   let arrNumber = new Array(n);
   
   // 迴圈新增隨機數的值
   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.");
   });
   
   //總毫秒數：
   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.");
   });
   
   //總毫秒數：
   console.log(hashTableInfo1);
   console.log(hashTable1);
   this.show(hashTableInfo1);
   }
   
   // 將內容顯示在頁面上
   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() {
   // 執行主函式
   new Main();
   };
   複製程式碼

雜湊表的動態空間處理與複雜度分析

雜湊表的時間複雜度

1. 對於鏈地址法來說

   O(N/M)
   O(log(N/M))
   O(1)
   O(1)
   

2. 正常情況下不會出現最壞的情況，
   1. 但是在資訊保安領域有一種攻擊方法叫做雜湊碰撞攻擊，
   2. 也就是當你知道這個雜湊計算方式之後，你就會精心設計一套資料，
   3. 當這套資料插入到雜湊表中之後，這套資料全部產生雜湊衝突，
   4. 這就使得系統的雜湊表的時間複雜度變成了最壞的情況，
   5. 這樣就大大的拖慢整個系統的執行速度，
   6. 也會在雜湊表查詢的過程中大大的消耗系統的資源。

雜湊表的動態空間處理

1. 雜湊表的本質就是一個數組

   O(1)
   

2. 雜湊表的中陣列的空間要隨著元素個數的改變進行一定的自適應

   N / M >= upperTolerance
   N / M
   N / M < lowerTolerance
   N / M
   

程式碼示例

1. MyHashTable

   // 自定義的hash生成類。
   class MyHash {
   constructor() {
   this.store = new Map();
   }
   
   // 生成hash
   hashCode(key) {
   let hash = this.store.get(key);
   if (hash !== undefined) return hash;
   else {
   // 如果 這個hash沒有進行儲存 就生成，並且記錄
   let hash = this.calcHashTwo(key);
   
   // 記錄
   this.store.set(key, hash);
   
   // 返回hash
   return hash;
   }
   }
   
   // 得到的數字比較小 六七位數 以下輔助函式：生成hash -
   calcHashOne(key) {
   // 生成hash 隨機小數 * 當前日期毫秒 * 隨機小數
   let hash = Math.random() * Date.now() * Math.random();
   
   // hash 取小數部分的字串
   hash = hash.toString().replace(/^\d*\.\d*?([1-9]+)$/, '$1');
   
   hash = parseInt(hash); // 取整
   
   return hash;
   }
   
   // 得到的數字很大 十幾位數 左右輔助函式：生成hash -
   calcHashTwo(key) {
   // 生成hash 隨機小數 * 當前日期毫秒 * 隨機小數
   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; // 實際元素個數
   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();
   }
   }
   
   // 根據key生成 雜湊表索引
   hash(key) {
   // 獲取雜湊值
   let hash = this.hashCalc.hashCode(key);
   // 對雜湊值轉換為32位的整數再進行取模運算
   return (hash & 0x7fffffff) % this.M;
   }
   
   // 獲取實際儲存的元素個數
   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; // 實際元素個數
   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();
   }
   
   // 設定擴容的上邊界
   this.upperTolerance = 10;
   // 設定縮容的下邊界
   this.lowerTolerance = 2;
   // 初始容量大小為 97
   this.initCapcity = 97;
   }
   
   // 根據key生成 雜湊表索引
   hash(key) {
   // 獲取雜湊值
   let hash = this.hashCalc.hashCode(key);
   // 對雜湊值轉換為32位的整數再進行取模運算
   return (hash & 0x7fffffff) % this.M;
   }
   
   // 獲取實際儲存的元素個數
   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++;
   
   // 平均元素個數 大於等於 當前容量的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--;
   
   // 平均元素個數 小於容量的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
   );
   }
   
   // 重新設定當前hashTable
   this.hashTable = newHashTable;
   }
   }
   複製程式碼

2. Main

   // main 函式
   class Main {
   constructor() {
   this.alterLine('HashTable Comparison Area');
   const n = 2000000;
   
   const random = Math.random;
   let arrNumber = new Array(n);
   
   // 迴圈新增隨機數的值
   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.");
   });
   
   //總毫秒數：
   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.");
   });
   
   //總毫秒數：
   console.log('HashTableBySystem' + ':' + hashTableInfo1);
   console.log(hashTable1);
   this.show('HashTableBySystem' + ':' + hashTableInfo1);
   }
   
   // 將內容顯示在頁面上
   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() {
   // 執行主函式
   new Main();
   };
   複製程式碼

雜湊表更復雜的動態空間處理方法

雜湊表的複雜度分析

1. 已經為雜湊表添加了動態處理空間大小的機制了
   1. 所以就需要對這個新的雜湊表進行一下時間複雜度的分析。
2. 自己實現的動態陣列的均攤複雜度分析
   1. 當陣列中的元素個數等於陣列的當前的容量的時候，
   2. 就需要進行擴容，擴容的大小是當前容量的兩倍，
   3. 整個擴容的過程要消耗O(n) 的複雜度，
   4. 但是這是經過 n 次O(1) 級別的操作之後才有這一次O(n) 級別的操作，
   5. 所以就把這個O(n) 級別的操作平攤到 n 次O(1) 級別的操作中，
   6. 那麼就可以簡單的理解之前每一次操作都是O(2) 級別的操作，
   7. 這個 2 是一個常數，對於複雜度分析來說會忽略一下常數，
   8. 那麼平均時間複雜度就是O(1) 級別的。
3. 自己實現的動態雜湊表的複雜度分析

   O(n)
   9*n
   O(1)
   O(lowerTolerance)~O(upperTolerance)之間
   O(1)
   O(1)
   

更復雜的動態空間處理方法

1. 對於自己實現的雜湊表來說

   M -> 2*M
   http://planetmath.org/goodhashtableprimes
   

2. 雜湊表的擴容的方案就可以不是原先的簡單乘以 2 或者除以 2
   1. 可以根據一張區內對應的素數表來進行擴容和縮容，
   2. 比如初始的大小是 53，擴容的時候就到 97，再擴容就到 193，
   3. 如果要縮容了，就到 97，如果要再縮容的就到 53，就這樣。
   4. 對於雜湊表來說，這些素數有在儘量的維持一個二倍的關係，
   5. 使用這些素數值進行擴容更加的合理。

      // lwrupr% errprime
      // 2^52^610.41666753
      // 2^62^71.04166797
      // 2^72^80.520833193
      // 2^82^91.302083389
      // 2^92^100.130208769
      // 2^102^110.4557291543
      // 2^112^120.2278653079
      // 2^122^130.1139326151
      // 2^132^140.00813812289
      // 2^142^150.06917324593
      // 2^152^160.01017349157
      // 2^162^170.01322498317
      // 2^172^180.002543196613
      // 2^182^190.006358393241
      // 2^192^200.000127786433
      // 2^202^210.0003181572869
      // 2^212^220.0003503145739
      // 2^222^230.0002076291469
      // 2^232^240.00004012582917
      // 2^242^250.00007525165843
      // 2^252^260.00001050331653
      // 2^262^270.000023100663319
      // 2^272^280.000009201326611
      // 2^282^290.000001402653189
      // 2^292^300.000011805306457
      // 2^302^310.0000001610612741
      複製程式碼

3. 對於計算機組成原理

   2.0 * 10^9
   1.6\*10^9
   

4. 擴容和縮容的注意點
   1. 擴容和縮容不要越界，
   2. 擴容和縮容使用那張表格中區間對應的素數。

程式碼示例

1. MyHashTable

   // 自定義的hash生成類。
   class MyHash {
   constructor() {
   this.store = new Map();
   }
   
   // 生成hash
   hashCode(key) {
   let hash = this.store.get(key);
   if (hash !== undefined) return hash;
   else {
   // 如果 這個hash沒有進行儲存 就生成，並且記錄
   let hash = this.calcHashTwo(key);
   
   // 記錄
   this.store.set(key, hash);
   
   // 返回hash
   return hash;
   }
   }
   
   // 得到的數字比較小 六七位數 以下輔助函式：生成hash -
   calcHashOne(key) {
   // 生成hash 隨機小數 * 當前日期毫秒 * 隨機小數
   let hash = Math.random() * Date.now() * Math.random();
   
   // hash 取小數部分的字串
   hash = hash.toString().replace(/^\d*\.\d*?([1-9]+)$/, '$1');
   
   hash = parseInt(hash); // 取整
   
   return hash;
   }
   
   // 得到的數字很大 十幾位數 左右輔助函式：生成hash -
   calcHashTwo(key) {
   // 生成hash 隨機小數 * 當前日期毫秒 * 隨機小數
   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; // 實際元素個數
   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();
   }
   }
   
   // 根據key生成 雜湊表索引
   hash(key) {
   // 獲取雜湊值
   let hash = this.hashCalc.hashCode(key);
   // 對雜湊值轉換為32位的整數再進行取模運算
   return (hash & 0x7fffffff) % this.M;
   }
   
   // 獲取實際儲存的元素個數
   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
   // 基於自己實現的AVL樹
   class MyHashTableByAVLTree {
   constructor() {
   // 設定擴容的上邊界
   this.upperTolerance = 10;
   // 設定縮容的下邊界
   this.lowerTolerance = 2;
   // 雜湊表合理的素數表
   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; // 實際元素個數
   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();
   }
   }
   
   // 根據key生成 雜湊表索引
   hash(key) {
   // 獲取雜湊值
   let hash = this.hashCalc.hashCode(key);
   // 對雜湊值轉換為32位的整數再進行取模運算
   return (hash & 0x7fffffff) % this.M;
   }
   
   // 獲取實際儲存的元素個數
   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++;
   
   // 平均元素個數 大於等於 當前容量的10倍，同時防止索引越界
   // 就以雜湊表合理的素數表 為標準進行 索引的推移
   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--;
   
   // 平均元素個數 小於容量的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
   );
   }
   
   // 重新設定當前hashTable
   this.hashTable = newHashTable;
   }
   }
   複製程式碼

2. Main

   // main 函式
   class Main {
   constructor() {
   this.alterLine('HashTable Comparison Area');
   const n = 2000000;
   
   const random = Math.random;
   let arrNumber = new Array(n);
   
   // 迴圈新增隨機數的值
   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.");
   });
   
   // 總毫秒數：13249
   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.");
   });
   
   // 總毫秒數：5032
   console.log('HashTableBySystem' + ':' + hashTableInfo1);
   console.log(hashTable1);
   this.show('HashTableBySystem' + ':' + hashTableInfo1);
   }
   
   // 將內容顯示在頁面上
   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() {
   // 執行主函式
   new Main();
   };
   複製程式碼

雜湊表的更多話題

1. 雜湊表：均攤複雜度為O(1)
2. 雜湊表也可以作為集合和對映的底層實現
   1. 平衡樹結構可以作為集合和對映的底層實現，
   2. 它的時間複雜度是O(logn) ，而雜湊表的時間複雜度是O(1) ，
   3. 既然如此平衡樹趕不上雜湊表，那麼平衡樹為什麼存在。
3. 平衡樹存在的意義是什麼？
   1. 答：順序性，平衡樹具有順序性，
   2. 因為樹結構本身是基於二分搜尋樹，所以他維護了儲存的資料相應的順序性。
4. 雜湊表犧牲了什麼才達到了如此的效能？
   1. 答：順序性，雜湊表不具有順序性，由於不再維護這些順序資訊，
   2. 所以它的效能才比樹結構的效能更加優越。
5. 對於大多數的演算法或者資料結構來說
   1. 通常都是有得必有失的，如果一個演算法要比另外一個演算法要好的話，
   2. 通常都是少維護了一些性質多消耗了一些空間等等，
   3. 很多時候依照這樣的思路來分析之前的那些演算法與同樣解決類似問題的演算法，
   4. 進行比較之後想明白兩種演算法它們的區別在哪兒，
   5. 一個演算法比一個演算法好，那麼它相應的犧牲了什麼失去了什麼，
   6. 這樣去思考就能夠對各種演算法對各種資料結構有更加深刻的認識。
6. 集合和對映
   1. 集合和對映的底層實現可以是連結串列、樹、雜湊表。
   2. 這兩種資料結構可以再抽象的細分成兩種資料結構，
   3. 一種是有序集合、有序對映，在儲存資料的時候還維持的資料的有序性，
   4. 通常這種資料結構底層的實現都是平衡樹，如 AVL 樹、紅黑樹等等，
   5. 在 系統內建的 Map、Set 這兩個類，底層實現是紅黑樹。
   6. 一種是無序集合、無序對映，
   7. 所以也可以基於雜湊表封裝自己的無序集合類和無序對映類。
   8. 同樣的只要你實現了二分搜尋樹的與有序相關的方法，
   9. 那麼這些介面就可以在有序集合類和有序對映類中進行使用，
   10. 從而使你的集合類和對映類都是有序的。