JS实现哈希函数、哈希表
一些知识准备
哈希化：将大数字进行压缩，转化成数组范围内下标的过程
哈希函数：实现哈希化的函数
哈希表: 最终将数据插入到的这个数组, 我们就称之为是一个哈希表
冲突：计算出的下标相同的情况
解决冲突：①链地址法 ②开放地址法
-
链地址法解决冲突的办法是每个数组单元中存储的不再是单个数据, 而是一个链条。
-
开放地址法的主要工作方式是寻找空白的单元格来添加重复的数据。
对于如何寻找空白单元格又分成三种方法：线性探测、二次探测、再哈希法
线性探测：
- 线性探测就是从index位置+1开始一点点查找合适的位置
二次探测：
- 线性探测, 我们可以看成是步长为1的探测, 比如从下标值x开始, 那么线性测试就是x+1, x+2, x+3依次探测
- 二次探测, 对步长做了优化, 比如从下标值x开始, x+1², x+2², x+3²
再哈希法：
-
把关键字用另外一个哈希函数, 再做一次哈希化, 用这次哈希化的结果作为步长
-
计算机专家已经设计出一种工作很好的哈希函数:
stepSize = constant - (key - constant)
其中constant是质数, 且小于数组的容量
例如: stepSize = 5 - (key % 5), 满足需求, 并且结果不可能为0
链地址法相对来说效率是好于开放地址法的.
所以在真实开发中, 使用链地址法的情况较多, 因为它不会因为添加了某元素后性能急剧下降.
比如在Java的HashMap中使用的就是链地址法
设计哈希函数：
①把字符串计算成哈希值，这里用霍纳法则（一种多项式的优化算法），可以降低时间复杂度
②实现均匀分布：虽然有办法解决冲突，但最好还是让数据在数组里均匀分布，因此, 我们需要在使用常量的地方, 尽量使用质数(所以要封装一个判断质数的函数)
这里扩展：Java的hashMap采用的是链地址法，一般从Key映射到index的算法用的是取模运算，但hasMap采用了位运算
哈希函数的实现
//1.将字符串转成比较大的数字：hashcode
//2.将hashcode压缩到数组范围之内
function hashFunc(str, size) {
//1.定义hashCode变量
let hashCode = 0;
let index = 0;
//2.霍纳算法，计算hashCode的值
for (let i = 0; i < str.length; i++) {
hashCode = hashCode * 37 + str.charCodeAt(i);
}
//3.取余操作
index = hashCode % size;
return index;
}
//测试
console.log(hashFunc('fan', 7)); //5
判断质数
//质数：只能被1和他本身整除(也就是不能被2到他自己-1的数整除)
//一个数n可以进行因式分解，分解得到的两个数一定一个<=sqrt(n),一个>=sqrt(n)
//例如16,得到2和8，2<sqrt(16),8>sqrt(16)
//所以不用遍历2到n-1，遍历到sqrt(n)即可、
function isPrime(num) {
let temp = parseInt(Math.sqrt(num));
for (let i = 0; i <= temp; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
哈希表的实现
//封装哈希表
function HashTable() {
//存放数据的数组
this.storage = [];
//当前哈希表已经存放元素的个数
this.count = 0;
//哈希表数组当前总长度
this.limit = 7;
//哈希函数
HashTable.prototype.hashFunc = function(str, size) {
//1.定义hashCode变量
let hashCode = 0;
let index = 0;
//2.霍纳算法，计算hashCode的值
for (let i = 0; i < str.length; i++) {
hashCode = hashCode * 37 + str.charCodeAt(i);
}
//3.取余操作
index = hashCode % size;
return index;
}
//插入或修改
HashTable.prototype.put = function(key, value) {
//1.根据key获取索引
let index = this.hashFunc(key, this.limit);
//2.根据索引取出对应位置的桶bucket(也是一个数组)
let bucket = this.storage[index];
//2.1判断桶存不存在,不存在就创建，并放回索引位置
if (bucket == null) {
bucket = [];
this.storage[index] = bucket;
}
//3.判断传入的key是新增的还是要修改的
//3.1遍历桶，看看key是否存在
for (let i = 0; i < bucket.length; i++) {
let tuple = bucket[i];
if (tuple[0] == key) {
tuple[1] = value;
return;
}
}
//3.2不存在就添加进桶
bucket.push([key, value]);
//3.3存放个数加一
this.count += 1;
//4.判断是否需要扩容
if (this.count > this.limit * 0.75) {
//4.1获得新的容量，判断这个新容量是不是质数，不是的话获取一个质数作为新容量
let newLimit = this.limit * 2;
let newSize = this.getPrime(newLimit);
this.resize(newSize);
}
}
//获取
HashTable.prototype.get = function(key) {
//1.根据key获取索引
let index = this.hashFunc(key, this.limit);
//2.根据索引获取对应位置的bucket
let bucket = this.storage[index];
//3.判断桶是否存在
//3.1不存在返回null
if (bucket == null) {
return null;
}
//3.2存在就遍历桶，查找key
for (let i = 0; i < bucket.length; i++) {
let tuple = bucket[i];
//3.3找到key就返回对应value
if (tuple[0] == key) {
return tuple[1];
}
}
//3.4没找到返回null
return null;
}
//删除
HashTable.prototype.remove = function(key) {
//1.根据key获取索引
let index = this.hashFunc(key, this.limit);
//2.根据索引获取对应位置的bucket
let bucket = this.storage[index];
//3.判断桶是否存在
//3.1不存在返回null
if (bucket == null) {
return null;
}
//3.2存在就遍历桶，查找key
for (let i = 0; i < bucket.length; i++) {
let tuple = bucket[i];
//3.3找到key就删除,存放个数-1
if (tuple[0] == key) {
bucket.splice(i, 1);
this.count--;
//4.判断是否要缩小容量
if (this.limit > 7 && this.count < this.count.limit * 0.25) {
//4.1获取为质数的新容量
let newLimit = Math.floor(this.limit / 2);
let newSize = this.getPrime(newLimit);
this.resize(newSize);
}
return tuple[1];
}
}
//3.4没找到返回null
return null;
}
//扩容\缩容
HashTable.prototype.resize = function(newLimit) {
//1.保存旧的表
var oldstorage = this.storage;
//2.重置数据
this.storage = [];
this.count = 0;
this.limit = newLimit;
//3.遍历旧的表
for (let i = 0; i < oldstorage.length; i++) {
let bucket = oldstorage[i];
//3.1判断bucket是否为空
if (bucket == null) {
continue;
}
//3.2将bucket的元素取出放入新的表
for (let j = 0; j < bucket.length; j++) {
let tuple = bucket[j];
this.put(tuple[0], tuple[1]);
}
}
}
//判断质数
HashTable.prototype.isPrime = function(num) {
let 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
while (!isPrime(num)) {
num++;
}
return num;
}
}
