基础数据结构(四):哈希表,使用typescript封装哈希表 |
您所在的位置:网站首页 › 哈希表有顺序吗 › 基础数据结构(四):哈希表,使用typescript封装哈希表 |
介绍
哈希表是基于数组来实现的,但是相对于数组,它有着更多的优势: 它可以提供非常快速的插入、删除、查找操作 无论多少数据,插入和删除的时间复杂度都可以达到O(1)当然它也有一些不足: 哈希表中的数据是没有顺序的 通常情况下哈希表的key不允许重复哈希表的原理大致可以用下面这张图来表示
虽然我们使用幂的乘积然后压缩的方式来尽量避免重复率过高的问题,但还是避免不了重复,那么我们就要想办法解决冲突。最常用到的有两种方式:链地址法和开放地址法 链地址法链地址法很好理解,就像下图
开放地址法一个位置就只插入一个元素,它的主要工作方式是寻找空白的单元格来添加重复的数据。
哈希表中有一个概念:装填因子,其计算公式是装填因子 = 总数据项 / 哈希表长度,哈希表的查找效率与装填因子的大小是负相关关系即:装填因子越大,查找效率越低,所以当装填因子达到一个值时,我们就要对哈希表进行扩容以保证效率。 哈希表实现链地址法受填装因子的影响较小,大多数语言也采用此方法,所以我们就实现链地址法。 hash算法幂的乘积可以看作是一个多项式:a(n)x^n + a(n-1)x^(n-1) + ... + a(1)x + a(0),这个多项式要进行n(n+1)/2次乘法和n次加法,所以它的时间复杂度是O(n^2),对于追求效率的哈希表来说这个时间复杂度太高,所以应该进行优化,对于多项式的优化可以使用秦九韶算法(霍纳法则),即a(n)x^n + a(n-1)x^(n-1) + ... + a(1)x + a(0) = ((...(((anx + an - 1)x + an - 2)x + an - 3)...)x + a1)x + a0,此时需要进行n次乘法和n次加法,时间复杂度降为O(n)。 除了要优化计算速度,还有注意均匀分布,好的方式是使用质数,比如哈希表的长度、N次幂的底数。使用质数的原因是质数与其他数相乘的结果相对于其他数字更容易产生唯一性的结果,减少哈希冲突(Java中的n次幂的底数选择的是31)。 那么先来实现hash算法,它接受两个参数key和max hashFunction(key: string, max: number) { let hash = 0; for (let i = 0; i < key.length; i++) { // 使用霍纳法则降低时间复杂度 hash = 31 * hash + key.charCodeAt(i); } // 返回hash值(索引值) return hash % max; } 复制代码 哈希表方法因为ts没有提供原生的链表,所以我们采用数组和元组作为bucket(桶,哈希表的基本单元),当然你也可以使用链表。 class HashTable { // 存储数据的数组 private storage: Array[] = [] // 当前插入的元素个数 private count: number = 0 // 最大容量 private limit: number = 7 } 复制代码 插入/修改操作哈希表的插入和修改是使用同一个方法的,put方法接收key和value put(key: string, value: T) { // 获取索引值 const index = this.hashFunction(key, this.limit); // 获取对应的bucket let bucket = this.storage[index]; // 判断bucket是否为undefined if (bucket === undefined) { // 创建桶 bucket = []; this.storage[index] = bucket; } // 判断是否是修改数据 let override = false; for (let i = 0; i < bucket.length; i++) { const tuple = bucket[i]; if (tuple[0] === key) { tuple[1] = value; override = true; } } // 如果不是修改数据 则插入数据 if (!override) { bucket.push([key, value]); this.count++; // 判断是否需要扩容 装填因子超过0.75 if (this.count > this.limit * 0.75) { // 扩容需要对以前容器的数据进行重新散列 // 因为扩容后取余的值发生了变化 对应的索引值也发生了变化 const newSize = this.limit * 2; // 保证newSize是质数 const primeSize = this.getPrime(newSize); this.resize(primeSize); } } } 复制代码这里插入和修改操作还是比较简单实现的,值得注意的是扩容操作,上文我们说了当装填因子超过0.75时会导致效率下降,所以我们要将数组容量提升,一般是提升一倍,由于容器长度为质数时会获取到最佳的均匀分布效果,所以要获取到一个最近的质数。 // 获取最近的质数 private getPrime(num: number) { while (!this.isPrime(num)) { num++; } return num; } // 判断是否为质数 private isPrime(num: number) { const temp = Math.sqrt(num); for (let i = 2; i 7 && this.count < this.limit * 0.25) { const newSize = Math.floor(this.limit / 2); // 保证newSize是质数 const primeSize = this.getPrime(newSize); this.resize(primeSize); } return tuple[1]; } } return undefined; } 复制代码 获取操作 get(key: string) { // 获取索引值 const index = this.hashFunction(key, this.limit); // 获取对应的bucket const bucket = this.storage[index]; // 判断bucket是否为undefined if (bucket === undefined) { return undefined; } // 遍历bucket for (let i = 0; i < bucket.length; i++) { const tuple = bucket[i]; if (tuple[0] === key) { return tuple[1]; } } return undefined; } 复制代码以上就是一个比较完整的哈希表封装,下面是完整代码: class HashTable { // 存储数据的数组 private storage: Array[] = [] // 当前插入的元素个数 private count: number = 0 // 最大容量 private limit: number = 7 // hash函数 private hashFunction(key: string, max: number) { let hash = 0; for (let i = 0; i < key.length; i++) { // 使用霍纳法则降低时间复杂度 hash = 31 * hash + key.charCodeAt(i); } // 返回hash值(索引值) return hash % max; } // 扩容/缩容 private resize(newLimit: number) { // 保存旧的数组内容 const oldStorage = this.storage; // 重置所有属性 this.storage = []; this.count = 0; this.limit = newLimit; // 遍历oldStorage中的所有bucket for (let i = 0; i < oldStorage.length; i++) { const bucket = oldStorage[i]; if (bucket === undefined) { continue; } // 遍历bucket中的所有元素 for (let j = 0; j < bucket.length; j++) { const tuple = bucket[j]; this.put(tuple[0], tuple[1]); } } } // 获取最近的质数 private getPrime(num: number) { while (!this.isPrime(num)) { num++; } return num; } // 判断是否为质数 private isPrime(num: number) { const temp = Math.sqrt(num); for (let i = 2; i this.limit * 0.75) { // 扩容需要对以前容器的数据进行重新散列 // 因为扩容后取余的值发生了变化 对应的索引值也发生了变化 const newSize = this.limit * 2; // 保证newSize是质数 const primeSize = this.getPrime(newSize); this.resize(primeSize); } } } // 获取值 get(key: string) { // 获取索引值 const index = this.hashFunction(key, this.limit); // 获取对应的bucket const bucket = this.storage[index]; // 判断bucket是否为undefined if (bucket === undefined) { return undefined; } // 遍历bucket for (let i = 0; i < bucket.length; i++) { const tuple = bucket[i]; if (tuple[0] === key) { return tuple[1]; } } return undefined; } // 删除 delete(key: string) { // 获取索引值 const index = this.hashFunction(key, this.limit); // 获取对应的bucket const bucket = this.storage[index]; // 判断bucket是否为undefined if (bucket === undefined) { return undefined; } // 遍历bucket for (let i = 0; i < bucket.length; i++) { const tuple = bucket[i]; if (tuple[0] === key) { bucket.splice(i, 1); this.count--; // 判断是否需要缩容 装填因子小于0.25 最小容量为7 if (this.limit > 7 && this.count < this.limit * 0.25) { const newSize = Math.floor(this.limit / 2); // 保证newSize是质数 const primeSize = this.getPrime(newSize); this.resize(primeSize); } return tuple[1]; } } return undefined; } get max() { return this.limit; } } 复制代码 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |