数据结构-哈希表
2021-07-23 本文已影响0人
AAA前端
哈希表
哈希表是一种数据结构，它可以提供快速的插入和查找操作。它的优点多得难以置信，无论哈希表中有多少数据，插入和删除只需要接近常量的时间，即O(1)的时间级
-
哈希表不仅速度快，编程实现也相对容易。
-
哈希表也有一些缺点，它是基于数组的，数组创建后难以扩展。某些哈希表被基本填满时，性能下降的非常验证，所以程序员必须要清楚表中要存储多少数据
哈希化
通过映射方法（即哈希函数）把一个巨大的整数范围转化为一个可接受的数组范围中。对哈希表来说是把较大的关键字值范围压缩成较小的数组下标范围
哈希化过程（哈希函数步骤）：
-
具有唯一标识作用的原始数据—s1—>合适的整数关键字—s2—>数组下标
-
s1: 有些原始数据虽然具备唯一标识特征，但可能不是数字（如字符串），也有可能存在冗余数字位（如校验位），需要将其处理为合适的整数关键字。属于预处理过程。（比如把字符串通过 ascii码或者 unicode码 转换为 数字）
-
s2: 一般对整数关键字取余得到数组下标 （假如用一个 length为10的数组存储，把s1得到的大数字比如 42 对10 取余 得到 2）
为什么要哈希化
- 数据存储快速：
- 整数关键字与数组下标存在映射关系，可以通过关键字获取数组下标直接存取数据，而不用像普通数组那样通过遍历来存取数据。
- 节省空间：
- 将大范围整数压缩成小范围，需要的数组长度变小了。
哈希函数的要求
- 能将整数关键字范围转化为数组下标值，即关键字要和数组下标要有关联。
- 简单能快速计算，即各种运算尽量要少。
- 大范围的数字经过哈希映射后应随机地分布在这个小的数字范围。
举例说明
-
比如字符串通过便后得到的整数范围很大，但实际的数据项个数却相对较少。比如说一组整数 0，100，1000，其整数范围为[0, 1000]，但是却只有3项。
-
若创建一个下标从0到1000的整数数组来存放这组整数，数组下标为0的单元存0，数组下标为100的单元存100，数组下标为1000的单元存1000。存取性能很高，可以通过整数直接访问数组，但只用到了3个地址单元，存储效率极低。
-
若创建一个下标从0到2的整数数组来存放这组整数，数组下标为0的单元存0，数组下标为1的单元存100，数组下标为2的单元存1000。存储效率很高，但这些整数与数组下标没有关联，只能遍历来访问数组，存取性能比较低，当数据项个数很多时更差。
-
哈希化在保证这些整数关键字与数组下标直接有关联的前提下，大大减小了整数范围。兼顾了存储效率和存取性能。
冲突
把巨大的数字空间压缩成较小的数字空间，插入时不能保证每个关键字都能通过哈希函数映射到数组的空白单元，删除时不能保证每个关键字通过哈希函数映射到的单元数据项正好为要删除的数据项。
- 减少冲突——哈希表数组容量取质数
- 若哈希表数组容量为非质数，如6，则数据项关键字为2的倍数、3的倍数容易发生冲突，关键字为6倍数一定发生冲突；
- 若哈希表数组容量为质数，如7，则数据项关键字仅在是7的倍数时发生冲突。
- 如2 4 6 8 10 12这6个数是2的倍数，如果对 6 取余 得到 2 4 0 2 4 0 只会得到3种哈希值，冲突会很多。如果对 7 取余 得到 2 4 6 1 3 5 得到6种哈希值，没有冲突。
因此，哈希表数组容量取质数可减少冲突。
- 开放地址法
- 要求：指定目标数组大小两倍于需要存储的数据量，从而保证有大量单元是空的；否则在数组快满时，存取效率会严重降低。
- 思想：当冲突发生时，通过系统的方法找到数组的一个空位并插入。
- 查找开放地址的方法：
- 线性探测：线性地查找空白单元，即数组下标递增（即步长为1）直到找到空位。（比如12对10取余后2，已经存到数组对应2的位置。22对10取余后得到2 ，发现该位置存在了，就往后步长加1找空位置，直到找到空位置，就存到该位置）
- 二次探测：数组下标按步数的平方增加，直到找到空位。(解决比如已经存储11，12，13，14，15，16....， 接下来存储102，这样从2的位置 每次都都加1找空位置，性能很低，要找很多次，改为步长的平方找，第一次 12， 不是空位置第二次 22 ，不是空位置 ，第三次3**2.依次类推，直到找到空格)
- 再哈希法：数组下标按
另一个哈希函数计算得到的步长增加，直到找到空位 （解决二次探测中 加入存储的数组下标刚好是 2，4，9， 16.。。。。这样二次探测也会消耗性能）
- 链地址法
- 不使用对象数组，而是创建一个链表数组，新数据项直接插入哈希函数得到的数组下标的链表中。
哈希算法
function hashFunc(str, max) {
// 1.初始化hashCode的值
var hashCode = 0
// 算法 实际用现成的 unidcode转码就行。这里为了展示原理，自己实现
// 比如 215 ===》 我们用 2*37^2+1*37^1+5 --->抽象成表达式 a(n)X^n+a(n-1)X^n-1...a(1)X+a(0)
// 乘法次数是 n+(n-1)+(n-2)....+1 = n(n-1)/2 次
// 加法次数是 n次
// 时间复杂度 是 O(N^2)
// 霍纳算法---- ((...(anX + an-1)X + an-2)X+ an-3)...)X+a1)X+a0
// 乘法次数是 n次
// 加法次数是 n次
// 时间复杂度 是 O(N)
// 来计算hashCode的数值
for (var i = 0; i < str.length; i++) {
// 37 随便取的一个质数 charCodeAt获取字符串的编码
hashCode = 37 * hashCode + str.charCodeAt(i)
}
// 3.取模运算
hashCode = hashCode % max
return hashCode
}
哈希表
// 创建HashTable构造函数 开放地址法实现
function HashTable() {
// 定义属性
this.storage = []
this.count = 0 // 存储的数组长度
this.limit = 8 // 装填因子 数据项个数/哈希表数组容量
// 定义相关方法
// 判断是否是质数 (质数的两个数，一个小于等于平方根，一个大于等于平方根，所以有下面的算法)
HashTable.prototype.isPrime = function(num) {
// 平方根 后 取整
var temp = parseInt(Math.sqrt(num))
// 2.循环判断
for (var i = 2; i <= temp; i++) {
if (num % i == 0) {
return false
}
}
return true
}
// 获取质数
HashTable.prototype.getPrime = function(num, fn) {
while (!isPrime(num)) {
num++
}
fn(num)
return num
}
// 哈希函数
HashTable.prototype.hashFunc = function(str, max) {
// 1.初始化hashCode的值
var hashCode = 0
// 2.霍纳算法, 来计算hashCode的数值
for (var i = 0; i < str.length; i++) {
hashCode = 37 * hashCode + str.charCodeAt(i)
}
// 3.取模运算
hashCode = hashCode % max
return hashCode
}
// 插入数据方法 即是插入也是修改
HashTable.prototype.put = function(key, value) {
// 1.获取key对应的index
var index = this.hashFunc(key, this.limit)
// 2.取出数组(也可以使用链表)
// 数组中放置数据的方式: [[ [k,v], [k,v], [k,v] ] , [ [k,v], [k,v] ] [ [k,v] ] ]
var bucket = this.storage[index]
// 3.判断这个数组是否存在
if (bucket === undefined) {
// 3.1创建桶
bucket = []
this.storage[index] = bucket
}
// 4.判断是新增还是修改原来的值.
var override = false
for (var i = 0; i < bucket.length; i++) {
var tuple = bucket[i]
if (tuple[0] === key) {
tuple[1] = value
override = true
}
}
// 5.如果是新增, 前一步没有覆盖
if (!override) {
bucket.push([key, value])
this.count++
// 判断 当前存储的 数组长度 是否 大于 2/3 大于需要扩容
if (this.count > this.limit * 0.75) {
this.getPrime(this.limit * 2, this.resize)
}
}
}
// 获取存放的数据
HashTable.prototype.get = function(key) {
// 1.获取key对应的index
var index = this.hashFunc(key, this.limit)
// 2.获取对应的bucket
var bucket = this.storage[index]
// 3.如果bucket为null, 那么说明这个位置没有数据
if (bucket == null) {
return null
}
// 4.有bucket, 判断是否有对应的key
for (var i = 0; i < bucket.length; i++) {
var tuple = bucket[i]
if (tuple[0] === key) {
return tuple[1]
}
}
// 5.没有找到, return null
return null
}
// 删除数据
HashTable.prototype.remove = function(key) {
// 1.获取key对应的index
var index = this.hashFunc(key, this.limit)
// 2.获取对应的bucket
var bucket = this.storage[index]
// 3.判断同是否为null, 为null则说明没有对应的数据
if (bucket == null) {
return null
}
// 4.遍历bucket, 寻找对应的数据
for (var i = 0; i < bucket.length; i++) {
var tuple = bucket[i]
// 找到对应
if (tuple[0] === key) {
bucket.splice(i, 1)
this.count--
// 缩小数组的容量
if (this.limit > 7 && this.count < this.limit * 0.25) {
this.getPrime(Math.floor(this.limit / 2), this.resize)
}
}
return tuple[1]
}
// 5.来到该位置, 说明没有对应的数据, 那么返回null
return null
}
// isEmpty方法
HashTable.prototype.isEmpty = function() {
return this.count == 0
}
// size方法
HashTable.prototype.size = function() {
return this.count
}
// 哈希表扩容
HashTable.prototype.resize = function(newLimit) {
// 1.保存旧的数组内容
var oldStorage = this.storage
// 2.重置属性
this.limit = newLimit
this.count = 0
this.storage = []
// 3.遍历旧数组中的所有数据项, 并且重新插入到哈希表中
oldStorage.forEach(function(bucket) {
// 1.bucket为null, 说明这里面没有数据
if (bucket == null) {
return
}
// 2.bucket中有数据, 那么将里面的数据重新哈希化插入
for (var i = 0; i < bucket.length; i++) {
var tuple = bucket[i]
this.put(tuple[0], tuple[1])
}
}).bind(this)
}
}
参考：https://blog.csdn.net/ChenTianyu666/article/details/106396685
