锐客网

  1. 首页 > it技术 > >

算法|JavaScript数据结构与算法 - 哈希表详解

算法javascript数据结构

哈希表通常是基于数组进行实现的,但是相对于数组,它也很多的优势和不足.
优势：

  • 它可以提供非常快速的插入-删除-查找操作
  • 无论多少数据,插入和删除值需要接近常量的时间:即O(1)的时间级.实际上，只需要几个机器指令即可完成
  • 哈希表的速度比树还要快，基本可以瞬间查找到想要的元素
  • 哈希表相对于树来说编码要容易很多.
不足:
  • 哈希表中的数据是没有顺序的,所以不能以一种固定的方式(比如从小到大)来遍历其中的元素
  • 通常情况下。哈希表中的key是不允许重复的,不能放置相同的key.用于保存不同的元素.
1. 哈希表的一些概念 1.1 哈希化 ? 将大数字转化成数组范围内下标的过程,我们就称之为哈希化.
1.2 哈希函数 ? 通常我们会将字符串转成大数字,大数字在进行哈希化的代码实现放在一个i
1.3 哈希表 ? 最终将数据插入到的这个数组,对整个结构的封装,我们就称之为是一个哈希表
2. 解决冲突 元素通过哈希化了获得的数组下标跟其他的已有的元素下标重复，就叫做冲突
常见的解决冲突的方法有两种：
  • 链地址法
  • 开放地址法
3. 链地址法（拉链法） 每个下标处存储一个链表或数组，当获取到下标值后，在遍历链表/数组依次查找元素
算法|JavaScript数据结构与算法 - 哈希表详解
文章图片

  • 图片解析:
    • 从图片中我们可以看出，链地址法解决冲突的办法是每个数组单元中存储的不再是单个数据,而是一个链条
    • 这个链条使用什么数据结构呢?常见的是数组或者链表
    • 比如是继表,也就是每个数组单元中存储着一个链表.一旦发现重复,将重复的元素插入到链表的首端或者未端即可
    • 当查询时,先根据哈希化后的下标值找到对应的位置再取出链表，依次查询找寻找的数据
  • 数组还是链表呢?
    • 数组或者链表在这里其实都可以,效率上也差不多
      因为根据哈希化的index找出这个数组或者链表时,通常就会使用线性查找，这个时候数组和链表的效率是差不多的
    • 当然在某些实现中，会将新插入的数据放在数组或者链表的最前面,因为觉得新插入的数据用于取出的可能性更大
    • 这种情况最好采用链表，因为数组在首位插入数据是需要所有其他项后移的,链表就没有这样的问题
    • 当然,我觉得出于这个也看业务需求,不见得新的数据就访问次数会更多:比如我们微信新添加的好友,可能是刚认识的,联系的频率不见得比我们的老朋友更多，甚至新加的只是聊一两句
    • 所以,这里个人觉得选择数据或者链表都是可以的.
4. 开放地址法 开放地址法主要工作方式是寻找空白的单元格来添加重复的数据
寻找空白位置有三种方法：
  • 线性探测法
  • 二次探测法
  • 再哈希法
4.1 线性探测 线性探测即线性的查找空白的单元格
插入32
  • 经过哈希化得到的index=2，但是在插入的时候发现该位置已经有了82.怎么办呢?
  • 线性探测就是从index位置+1开始一点点查找合适的位置来放置32,什么是合适的位置呢?
  • 空的位置就是合适的位置，在我们上面的例子中就是index=3的位置,这个时候32就会放在该位置.
查询32
  • 首先经过哈希化得到index=2,比如2的位置结果和查询的数值是否相同,相同那么就直接返回
  • 不相同呢?线性查找。从index位置+1开始查找和32一样的.
  • 这里有一个特别需要注意的地方:如果32的位置我们之前没有插入,是否将整个哈希表查询一遍来确定32存不存在吗?
  • 当然不是,查询过程有一个约定,就是查询到空位置,就停止.
  • 因为查询到这里有空位置,32之前不可能跳过空位置去其他的位置.
删除32
  • 删除操作和插入查询比较类似,但是也有一个特别注意点.
  • 注意:删除操作一个数据项时,不可以将这个位置下标的内容设置为null,为什么呢?
  • 因为将它设置为null同能会影响我们之后查询其他操作，所以通常删除一个位置的数据项时,我们可以将它进行特殊处理(比如设置为-1).
  • 当我们之后看到-1位置的数据项时,就知道查询时要继续查询,但是插入时这个位置可以放置数据.
解释：因为按照习惯我们在查询的一般都是遇到了空位置就停止查询了，那么如果我们要查询元素的前一个位置的内容之前被删掉，就会影响这个元素的查找
线性探测的问题
线性探测有一个比较严重的问题,就是聚集.什么是聚集呢?
  • 比如我在没有任何数据的时候。插入的是22-23-24-25-26,那么意味着下标值:2-3-4-5-6的位置都有元素
  • 这种一连串填充单元就叫做聚集.
  • 聚集会影响哈希表的性能，无论是插入/查询/删除都会影响.
  • 比如我们插入一个32.会发现连续的单元都不允许我们放置数据,并且在这个过程中我们需要探索多次
  • 二次探测可以解决一部分这个问题
4.2 二次探测
  • 二次探测在线性探测的基础上进行了优化:
    • 二次探测主要优化的是探测时的步长,什么意思呢?
    • 线性探测，我们可以看成是步长为1的探测,比如从下标值x开始,那么线性测试就是x+1,x+2,x+3依次探测
    • 二次探测,对步长做了优化，比如从下标值x开始,x+12,x+23,x+33.
    • 这样就可以一次性探测比较长的距离，比避免那些聚集带来的影响.
  • 二次探测的问题:
    • 但是二次探测依然存在问题,比如我们连续插入的是32-112-82-2-192,那么它们依次累加的时候步长的相同的.
    • 也就是这种情况下会造成步长不一的一种聚集.还是会影响效率(当然这种可能性相对于连续的数字会小一些)
    • 怎么根本解决这个问题呢?让每个人的步长不一样，一起来看看再哈希法吧.
4.3 再哈希化 为了消除线性探测和二次探测中无论步长+1还是步长+平法中存在的问题，我们可以使用再哈希法
再哈希法:
  • 二次探测的算法产生的探测序列步长是固定的:1,4,9，16,依次类推
  • 现在需要一种方法:产生一种依赖关键字的探测序列,而不是每个关键字都一样
  • 那么不同的关键字即使映射到相同的数组下标,也可以使用不同的探测序列
  • 再哈希法的做法就是:把关键字用另外一个哈希函数,再做一次哈希化,用这次哈希化的结果作为步长
  • 对于指定的关键字，步长在整个探测中是不变的,不过不同的关键字使用不同的步长
第二次哈希化需要具备如下特点:
  • 和第一个哈希函数不同.(不要再使用上一次的哈希函数了,不然结果还是原来的位置)
  • 不能输出为0(否则,将没有步长.每次探测都是原地踏步，算法就进入了死循环)
  • 其我们不用费脑细胞来设计了,计算机专家已经设计出一种工作很好的哈希函数:
    • stepSize = constant - (key - constant)
    • 其中constant是质数,且小于数组的容量
    • 例如: stepSize = 5 -(key % 5)，满足需求,并且结果不可能为0.
5. 哈希化的效率
  • 哈希表中执行插入和搜索操作效率是非常高的
  • 如果没有产生冲突,那么效率就会更高。如果发生冲突，存取时间就依赖后来的探测长度。
  • 平均探测长度以及平均存取时间，取决于填装因子，随着填装因子变大，探测长度也越来越长。
  • 随着填装因子变大，效率下降的情况，在不同开放地址法方案中比链地址法更严重,所以我们来对比一下他们的效率，再决定我们选取的方案.
  • 在分析效率之前,我们先了解一个概念:装填因子.
    • 装填因子表示当前哈希表中已经包含的数据项和整个哈希表长度的比值
    • 装填因子=总数据项/哈希表长度
    • 开放地址法的装填因子最大是1,因为它必须寻找到空白的单元才能将元素放入，总数据项最多等于哈希表长度
    • 链地址法的装填因子可以大于1,因为拉链法可以无限的延伸下去，只要你愿意.(当然后面效率就变低了)
6. 线性探测效率 下面的等式显示了线性探测时，探测序列§和填装因子(L)的关系
  • 对成功的查找:P=(1+1/(1-L)^2)/2
  • 对不成功的查找:P=(1+1/(1-L))/2
    算法|JavaScript数据结构与算法 - 哈希表详解
    文章图片

    图片解析.:
  • 当填装因子是1/2时，成功的搜索需要1.5次比较，不成功的搜索需要2.5次
  • 当填装因子为2/3时，分别需要2.0次和5.0次比较
  • 如果填装因子更大，比较次数会非常大。
  • 应该使填装因子保持在2/3以下，最好在1/2以下，另一方面，填装因子越低，对于给定数量的数据项，就需要越多的空间。
  • 实际情况中，最好的填装因子取决于存储效率和速度之间的平衡，随着填装因子变小，存储效率下降，而速度上升。
7. 二次探测和再哈希化 二次探测和再哈希法的性能相当。它们的性能比线性探测略好。
  • 对成功的搜索，公式是: -log2(1 - loadFactor) / loadFactor
  • 对于不成功的搜搜,公式是:1/(1-loadFactor)
    算法|JavaScript数据结构与算法 - 哈希表详解
    文章图片

    图片解析:
  • 当填装因子是0.5时，成功和不成的查找平均需要2次比较
  • 当填装因子为2/3时，分别需要2.37和3.0次比较
  • 当填装因子为0.8时，分别需要2.9和5.0次
  • 因此对于较高的填装因子，对比线性探测，二次探测和再哈希法还是可以忍受的。
8. 链地址法 链地址法的效率分析有些不同,一般来说比开放地址法简单，效率也比开放地址法好。我们来分析一下这个公式应该是怎么样的
  • 假如哈希表包含arraySize个数据项,每个数据项有一个链表,在表中一共包含N个数据项
  • 那么,平均起来每个链表有N / arraySize个数据项
  • 上面那个公式就是装填因子.
怎么求出查找成功和不成功的次数：
  • 成功可能只需要查找链表的一半即可: 1 + loadFactor/2
  • 不成功呢?可能需要将整个链表查询完才知道不成功: 1 + loadFactor.
所以在真实开发中，使用链地址法的情况较多
  • 因为它不会因为添加了某元素后性能急剧下降
  • 比如在Java的HashMap中使用的就是链地址法.
9. 哈希函数 9.1 哈希函数的优点
  • 快速的计算
    • 哈希表的优势就在于效率,所以快速获取到对应的hashCode非常重要.
    • 我们需要通过快速的计算来获取到元素对应的hashCode
  • 均匀的分布
    • 哈希表中，无论是链地址法还是开放地址法。当多个元素映射到同一个位置的时候,都会影响效率
    • 所以优秀的哈希函数应该尽可能将元素映射到不同的位置，让元素在哈希表中均匀的分布.
9.2 提高哈希函数计算效率
  • 让哈希函数中尽量减少乘法和除法，因为它们的性能是比较低的。
  • 使用霍纳法则优化多项式，减少乘法和除法
    • - 未优化前： a(n)x^n+a(n-1)x^(n-1)+...a(1)x+a(0); + 乘法次数：n+(n-1)+...+1=n(n+1)/2 + 加法次数：n次 + 时间复杂度：O(n^2) - 优化后 Pn(x)=anx^n+a(n-1)x^(n-1)+...+a1x+a0= ((...(((anx+an-1)x+an-2)x+an-3)...)x+a1)x+a0 + 乘法次数：n次 + 加法次数：n次 + 时间复杂度：O(n)

9.3 均匀分布
  • 在设计哈希表时,我们已经有办法处理映射到相同下标值的情况:链地址法或者开放地址法
  • 但是无论哪种方案,为了提供效率,最好的情况还是让数据在哈希表中均匀分布
  • 因此,我们需要在使用常量的地方,尽量使用质数.
质数的使用: (质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。)
  • 哈希表的长度
  • N次幂的底数(我们之前使用的是27)
**思考：**为什么他们使用质数.会让哈希表分布更加均匀呢?
  • 假设表的容量不是质数,例如:表长为15(下标值0~14)
  • 有一个特定关键字映射到D,步长为5.探测序列是多少呢?
  • 0-5-10-0-5-10,依次类推,循环下去.
  • 算法只尝试着三个单元,如果这三个单元已经有了数据。那么会一直循环下去,直到程序崩溃
  • 如果容量是一个质数。比如13.探测序列是多少呢?
  • 0-5-10-2-7-12-4-9-1-6-11-3,一直这样下去
  • 不仅不会产生循环，而且可以让数据在哈希表中更加均匀的分布.
9.4 实现哈希函数
// 实现哈希函数 // 1. 将字符串转换为较大的数字：hashCode // 2. 将数字hashCode压缩到数组范围之内 function hashfun(str,size){ var hashCode = 0; // 霍纳法则公式 for (let i = 0; i < str.length; i++) { // string.charCodeAt(index): 返回字符串index位字符的Unicode 编码 // 相当于霍纳法则里的：anx+an-1 // ((...(((anx+an-1)x+an-2)x+an-3)...)x+a1)x+a0 // 37是一个质数，也可以写其他质数，质数比较常用37 hashCode = 37 * hashCode + str.charCodeAt(i); console.log(str.charCodeAt(i)); }// 取余 var index = hashCode % size; return index; }

10. 创建哈希表 10.1 创建 我们这里采用链地址法来实现哈希表:
  • 实现的哈希表(基于storage的数组)每个index对应的是一个数组(bucket).(当然基于链表也可以.)
  • bucket中存放什么呢?我们最好将key和value都放进去,我们继续使用一个数组.(其实其他语言使用元组更好)
  • 最终我们的哈希表的数据格式是这样:[[ [k,v],[k,v],[k,v] ],[[k,v],[k,v] ],[ [k,v]]]
代码解析
【算法|JavaScript数据结构与算法 - 哈希表详解】我们定义了三个属性:
  • storage作为我们的数组,数组中存放相关的元素
  • count表示当前已经存在了多少数据
  • limit用于标记数组中一共可以存放多少个元素.
function Hash(){ var storage = []; var count = 0; var limit = 7; }

实现哈希函数
// 实现哈希函数 // 1. 将字符串转换为较大的数字：hashCode // 2. 将数字hashCode压缩到数组范围之内 function hashfun(str,size){ var hashCode = 0; // 霍纳法则公式 for (let i = 0; i < str.length; i++) { // string.charCodeAt(index): 返回字符串index位字符的Unicode 编码 // 相当于霍纳法则里的：anx+an-1 // ((...(((anx+an-1)x+an-2)x+an-3)...)x+a1)x+a0 // 37是一个质数，也可以写其他质数，质数比较常用37 hashCode = 37 * hashCode + str.charCodeAt(i); console.log(str.charCodeAt(i)); }// 取余 var index = hashCode % size; return index; }

10.2 插入&修改数据 哈希表的插入和修改操作是同一个函数：
  • 因为,当使用者传入一个时
  • 如果原来不存在该key,那么就是插入操作
  • 如果已经存在该key,那么就是修改操作
代码解析
  • 步骤1:根据传入的key获取对应的hashCode,也就是数组的index
  • 步骤2:从哈希表的index位置中取出桶（另外一个数组）
  • 步骤3:查看上一步的bucket是否为null
    • 为nul, 表示之前在该位置没有放置过任何的内容,那么就新建一个数组
  • 步骤4.查看是否之前已经放置过key对应的value
    • 如果放置过,那么就是依次替换操作,而不是插入新的数据
    • 我们使用一个变量override来记录是否是修改操作
  • 步骤5:如果不是修改操作,那么插入新的数据
    • 在bucket中push新的[key value]即可
    • 注意:这里需要将count+1,因为数据增加了一项
// 插入&修改操作 HashTable.prototype.put = function(key, value){ // 1. 根据key获取对应的hashcode，也就是数组的下标 var index = this.hashfun(key, this.limit); // 2. 根据index取出对应的bucket var bucket = this.storage[index]; // 3. 查看`bucket`是否为`null` if (bucket == null) { // 如果为空，就创建一个数组，存放到index位置 bucket = []; this.storage[index] = bucket; }// 4. 判断是否是修改数据 for (let i = 0; i < bucket.length; i++) { // if (bucket[i][0] == key) { //bucket[i][1] = value; // }else if (bucket[i] == null) { //bucket[i][0] = key; //bucket[i][1] = value; //bucket.push([key,value]); // } // return // 定义一个数组存放bucket里的元素 var tuple = bucket[i]; if (tuple[0] == key) { tuple[1] = value; return; } }// 添加 bucket.push([key,value]); this.count += 1; }

10.3 获取操作
// 获取操作 HashTable.prototype.get = function(key){ // 1. 通过传来的key获取hashCode，查找到对应的元素 this.index = this.hashfun(key,this.limit); // 2. 根据index取出对应的bucket var bucket = this.storage[index]; // 3. 判断bucket是否为空 if (bucket == null) return null; // 4. 查找元素 for (let i = 0; i < bucket.length; i++) { var tuple = bucket[i]; if (tuple[0] == key) { return tuple[1]; } return null; } }

10.4 删除操作
// 删除操作 HashTable.prototype.delete = function(key){ // 1. 通过传来的key获取hashCode，查找到对应的元素 this.index = this.hashfun(key,this.limit); // 2. 根据index取出对应的bucket var bucket = this.storage[index]; // 3. 判断bucket是否为空 if (bucket == null) return null; // 4. 查找元素 for (let i = 0; i < bucket.length; i++) { var tuple = bucket[i]; if (tuple[0] == key) { bucket.splice(i,1); this.count--; return tuple[1]; } return null; } }

10.5 测试
var hash = new HashTable(); hash.set('abc', 123); hash.set('cds', 234); hash.get('abc');

11. 哈希表扩容思想
  • 为什么需要扩容?
    • 目前,我们是将所有的数据项放在长度为7的数组中的.
    • 因为我们使用的是链地址法, loadFactor可以大于1,所以这个哈希表可以无限制的插入新数据
      • loadFactor就是前面第五点哈希化的效率中提到过的：装填因子
    • 但是随着数据量的增多,每一个index对应的bucket会越来越长，,也就造成效率的降低
    • 所以在合适的情况对数组进行扩容.比如扩容两倍
  • 如何进行扩容?
    • 扩容可以简单的将容量增大两倍(不是质数吗?质数的问题后面再讨论)
    • 但是这种情况下.所有的数据项一定要同时进行修改(重新调用哈希函数.来获取到不同的位置)
    • 比如hashCode=12的数据项,在length=8的时候,index=4.在长度为16的时候呢? index=12
    • 这是一个耗时的过程,但是如果数组需要扩容,那么这个过程是必要的.
  • 什么情况下扩容呢?
    • 比较常见的情况是loadFactor>0.75的时候进行扩容.
    • 比如Java的哈希表就是在装填因子大于0.75的时候,对哈希表进行扩容.
12. 高效的质数判断
  • 对于每个数n，其实并不需要从2判断到n-1
  • 一个数若可以进行因数分解，那么分解时得到的两个数一定是一个小于等于sqrt(n)，一个大于等于sqrt(n)
  • 比如16可以被分解为2*8,2小于sqrt(16),也就是4, 8大于4。而4*4都是等于sqrt(n)。
    • 就是说在小于sqrt(n)的数里，如果n不是质数，那么总有一个数能被他整除
  • 所以其实我们遍历到等于sqrt(n)即可
function prime(num){ var temp = parseInt(Math.sqrt(num)); for (let i = 0; i <= temp; i++) { if (num % i == 0) { return false; } }// for (let i = 2; i < num; i++) { //if (num % i == 0) { //return false; //} // } return true; } }

13. 实现容量恒为质数
  • 新增方法
    // 判断某个数字是否是质数 HashTable.prototype.isPrime = function (num){ var temp = parseInt(Math.sqrt(num)); for (let i = 0; i <= temp; i++) { if (num % i == 0) { return false; } } return true; }// 获取质数 HashTable.prototype.getPrime = function(num){ while(this.getPrime(num)){ num++; } return num; }

  • 修改set方法
    // 6. 判断是否需要扩容 if (this.count > this.limit * 0.75) { var newSize = this.limit * 2; var newPrime = this.getPrime(newSize); this.resize(newPrime); }

  • 修改delete方法
    // 判断是否需要减小容量 if (this.limit > 7 && this.count < this.limit * 0.25) { var newSize = Math.floor(this.limit / 2); var newPrime = this.getPrime(newSize); this.resize(newPrime); }

14. 完整代码 完整代码

    推荐阅读


    上一篇：数据结构|哈希表详解

    下一篇：查找——图文详解HashTree（哈希树）