【从蛋壳到满天飞】JS 数据结构解析和算法实现-哈希表

前言

【从蛋壳到满天飞】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. 哈希表是一个相对比较简单的数据结构，
2. 对于哈希表来说也有许多相对比较复杂的研究，
3. 不过对于这些研究大多数都是比较偏数学的，
4. 对于普通的软件工程软件开发来讲，
5. 使用哈希表了解哈希表的底层实现，并不需要知道那么多的复杂深奥的内容，
通过 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);}
}
复制代码
```
哈希表是对于你所关注的内容将它转化成索引
1. 如上面的题目中，
2. 你关注的是字符它所对应的频率，
3. 那么对于每一个字符来说必须先把它转化成一个索引，
4. 更一般的在一个哈希表中是可以存储各种数据类型的，
5. 对于每种数据类型都需要一个方法把它转化成一个索引，
6. 那么相应的关心的这个类型转换成索引的这个函数就称之为是哈希函数，
7. 在上面的题目中，哈希函数可以写成fn(char1) = char1 -'a'，
8. 这 fn 就是函数，char1 就是给定的字符，
9. 通过这个函数 fn 就把 char1 转化成一个索引，
10. 这个转化的方法体就是char1 -'a'，
11. 有了哈希函数将字符转化为索引之后，之后就只需要在哈希表中操作即可，
12. 在上面的题目中只是简单的将键转化为索引，所以非常的容易，
13. 还有如一个班里有 30 名学生，从 1-30 给这个学生直接编号即可，
14. 然后在数组中去存取这个学生的信息时直接用编号-1
15. 作为数组的索引这么简单，通过-1 就将键转化为了索引，太容易了。
16. 在大多数情况下处理的数据是非常复杂的，
17. 如一个城市的居民的信息，那么就会使用居民的身份证号来与之对应，
18. 但是居民的身份证号有 18 位数，那么就不能直接用它作为数组的索引，
19. 复杂的还有字符串，如何将一个字符串转换为哈希表中的一个索引，
20. 还有浮点数，或者是一个复合类型比如日期年月日时分秒，
21. 那么这些类型就需要先将它们转化为一个索引才可以使用，
22. 相应的就需要合理的设计一个哈希函数，
23. 那么多的数据类型，所以很难做到每一个键通过哈希函数
24. 都能转化成不同的索引从而实现一一对应，
25. 而且这个索引的值它要非常适合作为数组所对应的索引。
这种情况下很多时候就不得不处理一个在哈希表中非常关键的问题
1. 两个不同的键通过哈希函数它能对应同样一个索引，
2. 这就是哈希冲突，
3. 所以在哈希表上的操作也就是在解决这种哈希冲突，
4. 如果设计的哈希函数非常好都是一一对应的，
5. 那么对哈希表的操作也会非常的简单，
6. 不过对于更一般的情况，在哈希表上的操作主要考虑怎么解决哈希冲突问题。
哈希表充分的体现了算法设计领域的经典思想
1. 使用空间来换取时间。
2. 很多算法问题很多经典算法在本质上就是使用空间来换取时间，
3. 很多时候多存储一些东西或者预处理一些东西缓存一些东西，
4. 那么在实际执行算法任务的时候完成这个任务得到这个结果就会快很多，
5. 对于哈希表就非常完美的体现了这一点，
6. 例如键对应了身份证号，假如可以开辟无限大的空间，
7. 这个空间大小有 18 个 9 那么大，并且它还是一个数组，
8. 那么完全就可以使用O(1)的时间完成各项操作，
9. 但是很难开辟一个这么大的空间，就算空间中每一个位置只存储 32 位的整型，
10. 一个字节八个位，就是 4 个字节，4byte 乘以 18 个九，
11. 也就是接近 37 万 TB 的空间，太大了。
12. 相反，如果空间的大小只有 1 这么大，
13. 那么就代表了存储的所有内容都会产生哈希冲突，
14. 把所有的内容都堆在唯一的数组空间中，
15. 假设以链表的方式来组织整体的数据，
16. 那么相应的各项操作完成的时间复杂度就会是O(n)级别。
17. 以上就是设计哈希表的极端情况，
18. 如果有无限的空间，各项操作都能在O(1)的时间完成，
19. 如果只有 1 的空间，各项操作只能在O(n)的时间完成。
20. 哈希表整体就是在这二者之间产生一个平衡，
21. 哈希表是时间和空间之间的平衡。
对哈希表整体来说这个数组能开多大空间是非常重要的
1. 虽然如此，哈希表整体，哈希函数的设计依然是非常重要的，
2. 很多数据类型本身并不能非常自然的和一个整型索引相对应，
3. 所以必须想办法让诸如字符串、浮点数、复合类型日期
4. 能够跟一个整型把它当作索引来对应。
5. 就算你能开无限的空间，但是把身份证号作为索引，
6. 但是 18 位以下及 18 位以上的空间全部都是浪费掉的，
7. 所以对于哈希表来说，还希望，
8. 对于每一个键通过哈希函数得到索引后，
9. 这个索引的分布越均匀越好。

哈希函数的设计

哈希表这种数据结构
1. 其实就是把所关心的键通过哈希函数转化成一个索引，
2. 然后直接把内容存到一个数组中就好了。
对于哈希表来说，关心的主要有两部分内容
1. 第一部分就是哈希函数的设计，
2. 第二部分就是解决哈希函数生成的索引相同的冲突，
3. 也就是解决哈希冲突如何处理的问题。
哈希函数的设计
1. 键通过哈希函数得到的索引分布越均匀越好。
2. 虽然很好理解，但是想要达到这样的条件是非常难的，
3. 对于数据的存储的数据类型是五花八门，
4. 所以对于一些特殊领域，有特殊领域的哈希函数设计方式，
5. 甚至有专门的论文来讨论如何设计哈希函数，
6. 也就说明哈希函数的设计其实是非常复杂的。
最一般的哈希函数设计原则
1. 将所有类型的数据相应的哈希函数的设计都转化成是
2. 对于整型进行一个哈希函数的过程。
3. 小范围的正整数直接使用它来作为索引，
4. 如 26 个字母的 ascll 码或者一个班级的学生编号。
5. 小范围的负整数进行偏移，对于数组来说索引都是自然数，
6. 也就是大于等于 0 的数字，做一个简单的偏移即可，
7. 将它们都变完成自然数，如-100~100，让它们都加 100，
8. 变成0~200就可以了，非常容易。
9. 大整数如身份证号转化为索引，通常做法是取模运算，
10. 比如取这个大整数的后四位，等同于mod 10000，
11. 但是这样就存在陷阱，这个哈希表的数组最大只有一万空间，
12. 对于哈希表来说空间越大，就越难发生哈希冲突，
13. 那么你可以取这个大整数的后六位，等同于mod 1000000，
14. 但是对于身份证后四位来说，
15. 这四位前面的八位其实是一个人的生日，
16. 如 110108198512166666，取模后六位就是 166666，
17. 这个 16 其实是日期，数值只在 1-31 之间，永远不可能取 99，
18. 并且只取模后六位，并没有利用身份证上所有的信息，
19. 所以就会造成分布不均匀的情况。
取模的数字选择很重要，
1. 所以才会对哈希函数的设计，不同的领域有不同的做法，
2. 就算对身份证号的哈希函数设计的时候都要具体问题具体分析，
3. 哈希函数设计在很多时候很难找到通用的一般设计原则，
4. 具体问题具体分析在特殊的领域是非常重要的，
5. 像身份证号，有一个简单的解决方案可以解决分布不均匀的问题，
6. 模一个素数，通常情况模一个素数都能更好的解决分布均匀的问题，
7. 所以就可以更有效的利用这个大整数中的信息，
8. 之所以模一个素数可以更有效的解决这个问题，
9. 这是由于它背后有一定的数学理论做支撑，它本身属于数论领域，
10. 如下图所示，模 4 就导致了分布不均匀、哈希冲突，
11. 但是模 7 就不一样了，分布更加均匀减少了哈希冲突，
12. 所以需要看你存储的数据是否有规律，
13. 通常情况下模一个素数得到的结果会更好，
14. http://planetmath.org/goodhashtableprimes，
15. 可以从这个网站中看到，根据你的数据规模，你取模多大一个素数是合适的，
16. 例如你存储的数据在 2^5 至 2^6 时，你可以取模 53，哈希冲突的概率是 10.41667，
17. 例如你存储的数据在 2^23 至 2^24 你可以取模 12582917，冲突概率是 0.000040，
18. 这些都有人研究的，所以你可以从这个网站中去看。
19. 不用去深究，只要了解这个大的基本原则即可。
```
// 10 % 4 ---> 2          10 % 7 --->3
// 20 % 4 ---> 0          20 % 7 --->6
// 30 % 4 ---> 2          30 % 7 --->2
// 40 % 4 ---> 0          40 % 7 --->4
// 50 % 4 ---> 2          50 % 7 --->1
复制代码
```
浮点型的哈希函数设计
1. 将浮点型的数据转化为一个整数的索引，
2. 在计算机中都 32 位或者 64 位的二进制表示，只不过计算机解析成了浮点数，
3. 如果键是浮点型的话，那么就可以使用浮点型所存储的这个空间，
4. 把它当作是整型来进行处理，
5. 也就是把这个浮点型所占用的 32 位空间或 64 位空间使用整数的方式来解析，
6. 那么这篇空间同样可以可以表示一个整数，
7. 之后就可以将一个大的整数转成整数相应的方式，也就是取模的方式，
8. 这样就解决了浮点型的哈希函数的设计的问题
```
// // 单精度
//          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
复制代码
```
字符串的哈希函数设计
1. 字符串相对浮点型来说更加特殊一些，
2. 浮点型依然是占 32 位或 64 位这样的空间，
3. 而字符串可以有若干个字符来组合，它所占的空间数量是不固定的，
4. 尽管如此，对于字符串的哈希函数设计，依然可以将它转成大整型处理，
5. 例如一个整数可以转换成每一位数字的十进制表示法，
6. 如166 = 1 * 10^2 + 6 * 10^1 + 6 * 10^0，
7. 这样就相当于把一个整数看作是一个字符串，每一个字符就是一个数字，
8. 按照这种方式，就可以把字符串中每一个字符拆分出来，
9. 如果是英文就可以把它作为 26 进制的整数表示法，
10. 如code = c * 26^3 + o * 26^2 + d * 26^1 + e * 26^0，
11. c 在 26 进制中对应的是 3，其它的类似，
12. 这样一来就可以把一个字符串看作是 26 进制的整型，
13. 之所以用 26，这是因为一共有 26 个小写字母，这个进制是可以选的，
14. 例如字符串中大小写字母都有，那么就是 52 进制，如果还有各种标点符号，
15. 那么就可以使 256 进制等等，由于这个进制可以选，那么就可以使用一个标记来代替，
16. 如大 B，也就是 basics(基本)的意思，
17. 那么表达式是code = c * B^3 + o * B^2 + d * B^1 + e * B^0，
18. 最后的哈希函数就是
19. hash(code) = (c * B^3 + o * B^2 + d * B^1 + e * B^0) % M，
20. 这个 M 对应的取模的方式中那个素数，
21. 这个 M 也表示了哈希表的那个数组中一共有多少个空间，
22. 对于这种表示的样子，这个 code 一共有四个字符，所以最高位的 c 字符乘以 B 的三次方，
23. 如果这个字符串有一百个字符，那么最高位的 c 字符就要乘以 B 的 99 次方，
24. 很多时候计算 B 的 k 次方，这个 k 比较大的话，这个计算过程也是比较慢的，
25. 所以对于这个式子一个常见的转化形式就是
26. hash(code) = ((((c * B) + o) * B + d) * B + e) % M，
27. 将字符串转换成大整型的一个括号转换成了四个，
28. 在每一个括号里面做的事情都是拿到一个字符乘以 B 得到的结果再加上下一个字符，
29. 再乘以 B 得到的结果在加上下一个字符，
30. 再乘以 B 得到的结果直到加到最后一个字符为止，
31. 这样套四个括号之后，这个式子和那个套一个括号的式子其实是等价的，
32. 就是一种简单的变形，这样就不需要先算 B^99 然后再算 B^98 等等这么复杂了，
33. 每一次都需要乘以一个 B 再加上下一个字符再乘以 B 依此类推就好，
34. 那么使用程序实现的时候计算这个哈希函数相应的速度就会快一些，
35. 这是一个很通用的数学技巧，是数学中的多项式就是这样的，
36. 但是这么加可能会导致整型的溢出，
37. 那么就可以将这个取模的过程分别放入每个括号里面，
38. 这样就可以转化成这种形式
39. hash(code) = ((((c % M) * B + o) % M * B + d) % M * B + e) % M，
40. 这样一来，每一次都计算出了比 M 更小的数，所以根本就不用担心整型溢出的问题，
41. 这就是数论中的模运算的一个很重要的性质。
```
//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;
复制代码
```
复合类型的哈希函数设计
1. 比如一个学生类，里面包括了他的年级、班级、姓名等等信息，
2. 或者一个日期类，里面包含了年、月、日、时、分、秒、毫秒等等信息，
3. 依然是转换成整型来处理，处理方式和字符串是一样的，
4. 也是hash(code) = ((((c % M) * B + o) % M * B + d) % M * B + e) % M，
5. 完全套用这个公式，只不过是这样套用的，
6. 日期格式是这样的，Date：year，month，day，
7. hash(date) = ((((date.year%M) * B + date.month) % M * B + date.day) % M * B + e) % M，
8. 根据你复合类的不同，
9. 可能需要对 B 的值也就是进制进行一下设计从而选取一个更合理的数值，
10. 整个思路是一致的。
哈希函数设计一般来说对任何数据类型都是将它转换成整型来处理。
1. 转换成整型并不是哈希函数设计的唯一方法，
2. 只不过这是一个比较普通比较常用比较通用的一种方法，
3. 在很多特殊的领域有很多相关的论文去讲更多的哈希函数设计的方法。

哈希函数的设计，通常要遵循三个原则

一致性：如果 a==b，则 hash(a)==hash(b)。
1. 如果两个键相等，那么扔进哈希函数之后得到的值也一定要相等，
2. 但是对于哈希函数来说反过来是不一定成立的，
3. 同样的一个哈希值很有可能对应了两个不同的数据或者不同的键，
4. 这就是所谓的哈希冲突的情况。
高效性：计算高效简便。
1. 使用哈希表就是为了能够高效的存储，
2. 那么在使用哈希函数计算的时候耗费太多的性能那么就太得不偿失了。
均匀性：哈希值均匀分布。
1. 使用哈希函数之后得到的索引值就应该尽量的均匀，
2. 对于一般的整型可以通过模一个素数来让它尽量的均匀，
3. 这个条件虽然看起来很简单，但是真正要满足这个条件，
4. 探究这个条件背后的数学性质还是很复杂的一个问题。

js 中自定义 hashCode 方法

在 js 中自定义数据类型
1. 对于自己定义的复合类型，如学生类、日期类型，
2. 你可以通过写 hashCode 方法，
3. 然后自己实现一下这个方法重新生成 hash 值。

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);}// 拆分字符生成数字 -getCode(s) {s = s + '';let result = 0;// 遍历字符 计算结果for (const c of s) result += c.charCodeAt(0);// 返回结果return result;}//@Override toString 2018-10-19-jwltoString() {let studentInfo = `Student(name: ${this.name}, score: ${this.score})`;return studentInfo;}
}
复制代码

Main

// main 函数
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());}// 将内容显示在页面上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. 对于一个哈希表来说，对于一个整数求它的 hash 值的时候会对一个素数取模，
2. 这个素数就是这个数组的空间大小，也可以把它称之为 M，
在强类型语言中获取到的 hash 值可能是一个负数，所以就需要进行处理一下
1. 最简单的，直接获取这个 hash 值的绝对值就可以了，
2. 但是很多源码中，是这样的一个表示 (hashCode(k1) & 0x7fffffff) % M，
3. 也就是让 hash 值和一个十六进制的数字进行一个按位与，
4. 按位与之后再对 M 进行一个取模操作，这和直接获取这个 hash 值的正负号去掉是一样的，
5. 在十六进制中，每一位表示的是四个 bit，那么 f 表示的就是二进制中的1111，
6. 七个 f 表示的是二进制中的 28 个 1，7 表示的是二进制中的111，
7. 那么0x7fffffff表示的二进制就是 31 个 1，hash 值对 31 个 1 进行一下按位与，
8. 在计算机中整型的表示是用的 32 位，其中最高位就是符号位，如果和 31 个 1 做按位与，
9. 那么相应的最高为其实是 0，这样操作的结果其实就是最高位的结果，肯定是 0，
10. 而这个 hash 值对应的二进制表示的那 31 位
11. 再和 31 个 1 进行按位与之后任然保持原来的样子，
12. 也就是这个操作做的事情实际上就是把 hash 值整型对应的二进制表示的最高位的 1 给抹去，
13. 给抹成了 0，如果它原来是 0 的，那么任然是 0，
14. 这是因为在计算机中对整型的表示最高位是符号位，如果最高位是 1 表示它是一个负数，
15. 如果最高位是 0 表示它是一个正数，那么抹去 1 就相当于把负号去掉了。
16. 在 js 中这样做效果不好，所以需要自己根据实际情况来写一起算法，如通过时间戳来进行这种操作。
链地址法
1. 根据元素的哈希值计算出索引后，根据索引来哈希表中的数组里存储数据，
2. 如果索引相同的话，那么就以链表的方式将新元素挂到数组对应的位置中，
3. 这样就很好的解决了哈希冲突的问题了，因为每一个位置都对应了一个链，
4. 它的本质就是一个查找表，查找表的本质不一定是使用链表，
5. 它的底层其实还可以使用树结构如平衡树结构，
6. 对于哈希表的数组中每一个位置存的不是一个链表而是一个 Map，
7. 通过哈希值计算出索引后，根据索引找到数组中对应的位置之后，
8. 就可以把你要存储的元素插入该位置的红黑树里即可，
9. 那么这个 Map 本质就是一个红黑树 Map 数组，这是映射的形式，
10. 如果你真正要实现的是一个集合，那么也可以使用红黑树 Set 数组，
11. 哈希表的数组中每一个位置存的都是一个查找表，
12. 只要这个数据结构适合作为查找表就可以了，它是可以有不同的底层实现,
13. 哈希表的数组中每一个位置也可以对应的是一个链表，
14. 当数据规模比较小的时候，其实链表要比红黑树要快的，
15. 数据规模比较小的时候使用红黑树可能更加耗费性能，如各种旋转操作，
16. 因为它要满足红黑树的性能，所以反而会慢一些。

实现自己的哈希表

之前实现的树结构中都需要进行比较
1. 其中的键都需要实现 compare 这个用来比较两个元素的方法，
2. 因为需要通过键来进行比较，
3. 对于哈希表来说没有这个要求，
4. 这个 key 不需要实现这个方法。
在哈希表中存储的元素都需要实现可以用来获取 hashCode 的方法。
对于哈希表来说相应的开多少空间是非常重要的
1. 开的空间越合适，那么相应的哈希冲突就越少，
2. 空间大小可以参考http://planetmath.org/goodhashtableprimes，
3. 根据存储数据的多少来开辟合适的空间，但是很多时候并不知道要开多少的空间，
4. 此时使用哈希表并不能合理的估计一个 M 值，所以需要进行优化。

代码示例

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;}}// 得到的数字比较小 六七位数 以下  辅助函数：生成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);}
}
复制代码

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. 总共有 M 个地址，如果放入 N 个元素，那么每一个地址就有 N/M 个元素，
2. 也就是说有 N/M 个元素的哈希值是冲突的，
3. 如果每个地址里面是一个链表，那么平均的时间复杂度就是O(N/M)级别，
4. 如果每一个地址里面是一个平衡树，那么平均的时间复杂度是O(log(N/M))级别，
5. 这两个时间复杂度都是平均来看的，并不是最坏的情况，
6. 哈希表的优势在于，能够让时间复杂度变成O(1)级别的，
7. 只要让这个 M 不是固定的，是动态的，那么就能够让时间复杂度变成O(1)级别。
正常情况下不会出现最坏的情况，
1. 但是在信息安全领域有一种攻击方法叫做哈希碰撞攻击，
2. 也就是当你知道这个哈希计算方式之后，你就会精心设计一套数据，
3. 当这套数据插入到哈希表中之后，这套数据全部产生哈希冲突，
4. 这就使得系统的哈希表的时间复杂度变成了最坏的情况，
5. 这样就大大的拖慢整个系统的运行速度，
6. 也会在哈希表查找的过程中大大的消耗系统的资源。

哈希表的动态空间处理

哈希表的本质就是一个数组
1. 如果这个数组是静态的话，那么哈希冲突的机会会很多，
2. 如果这个数组是动态的话，那么哈希冲突的机会会很少，
3. 因为你存储的元素接近无穷大的话，
4. 静态的数组肯定是无法让相应的时间复杂度接近O(1)级别。
哈希表的中数组的空间要随着元素个数的改变进行一定的自适应
1. 由于静态数组固定的地址空间是不合理的，
2. 所以和自己实现的动态数组一样，需要进行 resize，
3. 和自己实现的动态数组不一样的是，哈希表中的数组不存在所有位置都填满，
4. 因为它的存储方式和动态数组的按照顺序一个一个的塞进数组的方式不一样。
5. 相应的解决方案是，
6. 当平均每个地址的承载的元素多过一定程度，就去扩容，
7. 也就是N / M >= upperTolerance的时候，也就是设置一个上界，
8. 如果也就是说平均每个地址存储的元素超过了多少个，如 upperTolerance 为 10，
9. 那么N / M大于等于 10，那么就进行扩容操作。
10. 反之也有缩容，
11. 当平均每个地址承载的元素少过一定程度，就去缩容，
12. 也就是N / M < lowerTolerance的时候，也就是设置一个下限，
13. 也就是哈希冲突并不严重，那么就不需要开那么大的空间了，
14. 如 lowerTolerance 为 2，那么N / M小于 2，那么就进行缩容操作。
15. 大概的原理和动态数组扩容和缩容的原理是一致的，但是有些细节方面会不一样，
16. 如新的哈希表的根据 key 获取哈希值后对 M 取模，这个 M 你需要设置为新的 newM，
17. 并且你遍历的空间也是原来那个旧的 M 个空间地址，并不是新的 newM 个空间地址，
18. 所以你需要先将旧的 M 值存一下，然后再将 newM 赋值给 M，这样逻辑才完全正确。

代码示例

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;}}// 得到的数字比较小 六七位数 以下  辅助函数：生成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;// 初始容量大小为 97this.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);}// 重新设置当前hashTablethis.hashTable = newHashTable;}
}
复制代码

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. 就需要进行扩容，扩容的大小是当前容量的两倍，
3. 整个扩容的过程要消耗O(n)的复杂度，
4. 但是这是经过 n 次O(1)级别的操作之后才有这一次O(n)级别的操作，
5. 所以就把这个O(n)级别的操作平摊到 n 次O(1)级别的操作中，
6. 那么就可以简单的理解之前每一次操作都是O(2)级别的操作，
7. 这个 2 是一个常数，对于复杂度分析来说会忽略一下常数，
8. 那么平均时间复杂度就是O(1)级别的。
自己实现的动态哈希表的复杂度分析
1. 其实分析的方式和动态数组的分析方式是一样的道理，
2. 也就是说，哈希表中元素个数从 N 增加到了 upperTolerance*N 的时候，
3. 整个哈希表的地址空间才会进行一个翻倍这样的扩容，
4. 也就是说增加 9 倍原来的空间大小之后才会进行空间地址的翻倍，
5. 那么相对与动态数组来说，是添加了更多的元素才进行的翻倍，
6. 这个操作也是O(n)级别的操作，
7. 这一次操作也需要平摊到 9*n次操作中去，
8. 那么每一次操作平摊到的时间复杂度就会更少，
9. 正因为如此就算进行了 resize 操作之后，
10. 哈希表的平均时间复杂度还是O(1)级别的，
11. 其实每个操作是在O(lowerTolerance)~O(upperTolerance)之间，
12. 这两个数都是自定义的常数，所以这样的一个复杂度还是O(1)级别的，
13. 无论缩容还是扩容都是如此，所以这就是哈希表这种数据结构的一个巨大优势，
14. 这个O(1)级别的时间复杂度是均摊得到的，是平均的时间复杂度。

更复杂的动态空间处理方法

对于自己实现的哈希表来说
1. 扩容操作是从 M -> 2*M，就算初始的 M 是一个素数，
2. 那么乘以 2 之后一定是一个偶数，再继续扩容的过程中，
3. 就会是 2^k 乘以 M，所以它显然不再是一个素数，
4. 这样的一个容量，会随着扩容而导致哈希表索引分布不再均匀，
5. 所以希望这个空间是一个素数，解决的方法非常的简单。
6. 在哈希表中不同的空间范围里合理的素数已经有人总结出来了，
7. 也就是说对于哈希表的大小已经有很多与数学相关的研究人员给出了一些建议，
8. 可以通过这个网址看到一张表格，表格中就是对应的大小区间、对应的素数以及冲突概率，
9. http://planetmath.org/goodhashtableprimes，

哈希表的扩容的方案就可以不是原先的简单乘以 2 或者除以 2

可以根据一张区内对应的素数表来进行扩容和缩容，
比如初始的大小是 53，扩容的时候就到 97，再扩容就到 193，
如果要缩容了，就到 97，如果要再缩容的就到 53，就这样。
对于哈希表来说，这些素数有在尽量的维持一个二倍的关系，

使用这些素数值进行扩容更加的合理。

// lwr   upr    % err     prime
// 2^5   2^6   10.416667  53
// 2^6   2^7   1.041667   97
// 2^7   2^8   0.520833   193
// 2^8   2^9   1.302083   389
// 2^9   2^10  0.130208   769
// 2^10  2^11  0.455729   1543
// 2^11  2^12  0.227865   3079
// 2^12  2^13  0.113932   6151
// 2^13  2^14  0.008138   12289
// 2^14  2^15  0.069173   24593
// 2^15  2^16  0.010173   49157
// 2^16  2^17  0.013224   98317
// 2^17  2^18  0.002543   196613
// 2^18  2^19  0.006358   393241
// 2^19  2^20  0.000127   786433
// 2^20  2^21  0.000318   1572869
// 2^21  2^22  0.000350   3145739
// 2^22  2^23  0.000207   6291469
// 2^23  2^24  0.000040   12582917
// 2^24  2^25  0.000075   25165843
// 2^25  2^26  0.000010   50331653
// 2^26  2^27  0.000023   100663319
// 2^27  2^28  0.000009   201326611
// 2^28  2^29  0.000001   402653189
// 2^29  2^30  0.000011   805306457
// 2^30  2^31  0.000000   1610612741
复制代码

对于计算机组成原理
1. 32 位的整型最大可以承载的 int 是2.0 * 10^9左右，
2. 1610612741 是 1.6*10^9，
3. 它是比较接近 int 型可以承载的极限的一个素数了。
扩容和缩容的注意点
1. 扩容和缩容不要越界，
2. 扩容和缩容使用那张表格中区间对应的素数。

代码示例

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;}}// 得到的数字比较小 六七位数 以下  辅助函数：生成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);}// 重新设置当前hashTablethis.hashTable = newHashTable;}
}
复制代码

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.");});// 总毫秒数：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.");});// 总毫秒数：5032console.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();
};
复制代码

哈希表的更多话题

哈希表：均摊复杂度为O(1)
哈希表也可以作为集合和映射的底层实现
1. 平衡树结构可以作为集合和映射的底层实现，
2. 它的时间复杂度是O(logn)，而哈希表的时间复杂度是O(1)，
3. 既然如此平衡树赶不上哈希表，那么平衡树为什么存在。
平衡树存在的意义是什么？
1. 答：顺序性，平衡树具有顺序性，
2. 因为树结构本身是基于二分搜索树，所以他维护了存储的数据相应的顺序性。
哈希表牺牲了什么才达到了如此的性能？
1. 答：顺序性，哈希表不具有顺序性，由于不再维护这些顺序信息，
2. 所以它的性能才比树结构的性能更加优越。
对于大多数的算法或者数据结构来说
1. 通常都是有得必有失的，如果一个算法要比另外一个算法要好的话，
2. 通常都是少维护了一些性质多消耗了一些空间等等，
3. 很多时候依照这样的思路来分析之前的那些算法与同样解决类似问题的算法，
4. 进行比较之后想明白两种算法它们的区别在哪儿，
5. 一个算法比一个算法好，那么它相应的牺牲了什么失去了什么，
6. 这样去思考就能够对各种算法对各种数据结构有更加深刻的认识。
集合和映射
1. 集合和映射的底层实现可以是链表、树、哈希表。
2. 这两种数据结构可以再抽象的细分成两种数据结构，
3. 一种是有序集合、有序映射，在存储数据的时候还维持的数据的有序性，
4. 通常这种数据结构底层的实现都是平衡树，如 AVL 树、红黑树等等，
5. 在系统内置的 Map、Set 这两个类，底层实现是红黑树。
6. 一种是无序集合、无序映射，
7. 所以也可以基于哈希表封装自己的无序集合类和无序映射类。
8. 同样的只要你实现了二分搜索树的与有序相关的方法，
9. 那么这些接口就可以在有序集合类和有序映射类中进行使用，
10. 从而使你的集合类和映射类都是有序的。

【从蛋壳到满天飞】JS 数据结构解析和算法实现-哈希表

前言

哈希表

哈希函数的设计

哈希函数的设计，通常要遵循三个原则

js 中自定义 hashCode 方法

哈希冲突的处理-链地址法(Seperate Chaining)

实现自己的哈希表

代码示例

哈希表的动态空间处理与复杂度分析

哈希表的时间复杂度

哈希表的动态空间处理

代码示例

哈希表更复杂的动态空间处理方法

哈希表的复杂度分析

更复杂的动态空间处理方法

代码示例

哈希表的更多话题

更多哈希冲突的处理方法

Published by

风君子

前言

哈希表

哈希函数的设计

哈希函数的设计，通常要遵循三个原则

js 中 自定义 hashCode 方法

哈希冲突的处理-链地址法(Seperate Chaining)

实现自己的哈希表

代码示例

哈希表的动态空间处理与复杂度分析

哈希表的时间复杂度

哈希表的动态空间处理

代码示例

哈希表更复杂的动态空间处理方法

哈希表的复杂度分析

更复杂的动态空间处理方法

代码示例

哈希表的更多话题

更多哈希冲突的处理方法

Published by

风君子

js 中自定义 hashCode 方法