文章目录
哈希表
- 哈希表(Hash table )---- 散列表
- 哈希表是一种非常重要的数据结构,几乎所有的编程语言都用到了或者间接用到了哈希表
- 它的结构就是一个
数组
,但是它与数组的不同之处在于对下标值的变换,这种变换称之为哈希函数
,通过哈希函数获得HashCode
- 哈希表通常是基于数组实现的,但是相对于数组,它却有很多的优势
- 它可以非常快速的插入-删除-查找操作
- 无论多少数据,插入和删除值需要接近常量的时间:即O(1)的时间级,实际上,只需要几个机器指令即可完成
- 哈希表的速度比树还要快,基本可以瞬间查找到想要的元素
- 哈希表相对于树的编码要容易很多
- 哈希表相较于数组的一些缺点
- 哈希表中的数据是
没有顺序
的,所以不能使常规的方式来遍历其中的元素 - 通常情况下,
哈希表中的key值是不允许空值
的,且不能放置相同的key
,用于保存不同的元素
- 哈希表中的数据是
结构
当我们向哈希表中存入某个值(数字,字符,bool等)时,哈希函数将这个数据编码为一个大整数,压缩大整数后通过
哈希化
后拿到这个数据在数组结构的下标值
,然后将值直接存入对应的数组位置,之后查询,修改,删除都只用直接将查询的值
哈希化后得到的下标直接去对应下标位置拿到数据即可,无需遍历,效率会高很多。
哈希函数
将单词或其他数据转为大数字
,大数字在进行哈希化的代码实现
放在一个函数中,这个函数称为哈希函数
字符转大整数
-
单词/字符串转下标值,其实就是
字母/文字转数字
- 现在我们需要设计一种方案,可以将单词转成适当的下标
- 其实计算机中有很多的编码方案,就是用数字代替单词的字符
- 如字符编码·
- ASCII编码,也阔以自己设计编码
- 我们可以使用Utf - 8 的编码
- 现在我们需要设计一种方案,可以将单词转成适当的下标
-
如何转?
-
数字相加的方案
-
利用单词在单词表中的位置
-
如 cats = 3 + 1 + 20 + 17 = 41;哈希表查询的时候只需要查询下标41就可以找到单词cats
-
缺点:不够复杂,容易重复
-
-
幂的连乘方案
-
可以基本满足数字的唯一性,不会和其他的单词重复
-
如 7654 = 710³ + 610² + 5*10 + 4;
-
那么单词也可以表示为 cats = 327³ + 127² + 20*27 + 17 = 60337
-
这个时候 60337 就是 cats单词在哈希表中的下标, 哈希表查询的时候只需要查询下标60337就可以找到单词cats
-
缺点
-
创建无意义单词,如yyyyyyyy,浪费空间,并且数组无法表示这么大的下标值
-
当我们拿到大数值时,一般的大小会非常大了,如果创建对应长度的数组将会非常浪费空间,这个时候我们需要进行一定的压缩操作,将数据控制在可接受范围。
哈希化
- 哈希化
- 现在需要一种压缩方法,将连乘得到的巨大整数范围压缩到可接受的范围之内,避免数组无法表示如此之大的下标范围
- 一般情况下需要很大的空间来存储数据,因为不能保证每一个数据能完全映射到数组的每一个位置(有的位置不一定只有一个数据)
-
压缩
- 现在将过大的幂连乘数据压缩到可接受范围内
- 操作:
取余
- 得到一个数被另一个数整除后的余数
- 假设我们要将最大为10000的数值压缩为最大100的数值
- 我们先设定一个哈希表下标值 index = 10000 / 100 = 100;
- 当有一个数据 23459 ,那么他会被存储在 (23459 % index) = 9 这个范围的哈希表内,而120这个值,会被存储在(120 % index = 0)
这个范围的hash表内。 -
这中间也会存在重复的情况
- 概念
- 哈希化: 将大数字转换成数组范围内下标的过程,称为哈希化。
- 哈希函数: 将单词或其他数据转为大数字,大数字在进行哈希化的代码实现放在一个函数中,这个函数称为哈希函数,比如之前的(10000 % 100)
- 哈希表:最终将数据插入到这个数组,对整个结构的封装,称之为哈希表
将数据进行幂的连乘转换为大数字后,不可能直接在数组上开对应大小的空间(浪费空间,有些空间用不上),这时对其进行哈希化后得到的数字可以作为下标,将数值放入对应下标的数组,如有一个长度为8的数组(对应哈希化取余的大小为9),数字23344对应存入下标4位置,数字125对应下标5的位置····
哈希冲突
我们发现存入的值经过哈希化后得到的下标值是有可能重复
的(虽然这种可能性不高),但是一旦出现了哈希冲突,会导致前面的数据被后面的数据覆盖
,这种情况下就需要解决哈希冲突
当在同一个下标位置出现多个数据时,这个时候可能插入数据的话可能会导致之前的数据丢失
常用的解决方法有链地址法和开放地址法
链地址法
-
通过在下标位置使用
链表
或者数组
来存储数据
,这样一个下标位置就可以存储多个数据了,查询的时候就按照链表或者数组的查询方法查询即可 -
当使用链表的时候,一般从头部或者尾部插入数据,如果使用的是数组的时候,一般为了性能优先从尾部插入.
当出现冲突时。后插入的数据会被填入数组或者链表中,避免数据的丢失。
开放地址法
主要是寻找空白位置添加数据,但是查找这个位置的方法有三种
线性探测
-
当前位置已有数据时,那么将从这个位置的下一个位置开始查找位置,当查找到有
空位置
时插入数据 -
当查找该数据时,先查询当前位置数据与查询数据是否相同,相同则返回该值,不同则从下一个位置继续查找查询值,当遇到
空白位置
则终止查询。(因为该值(重复
)只会放在第一个空白位置,如果查找到空值任然没有找到该值,那么后面也不可能会有该值,终止查询避免影响性能)。 -
当删除了某一个数值时,当前位置应该指定
特殊值
(如-1),当查询数据遇到这个数值(-1)时,则继续向后查询,避免因为删除指定位置在的数据后出现的null值(使查询中断)
,影响到后续数据的查询。
二次探测
线性查询存在的问题,
- 当没有任何数据时,我们插入了一段聚集在某一段位置的数据时,会影响到哈希表查询的性能,我们查询一个数据,且它原本的位置被其他元素占据,它的下位置有很多其他连续的数据时,想要查询它就必须一次一次的查询这段区域的数据,直到查询到插入在其他区域的该元素
聚集
- 二次探测解决聚集问题
二次探测主要是解决线性探测的步长问题,普通的线性探测可以看做是步长为1的探测,二次探测可以看做是跨多列探测
,如跨(x是下标值)x+1,x+2²···(如下标值为2,那么步长分别是(3,6,10))这样可以一次性探测较长的距离,避免聚集带来的影响
再哈希法
二次探测存在的问题,当我们插入的是同一个下标的数值(12,102,112,222···);这时候二次探测的步长相同,也会出现性能问题,这是再次对其进行哈希化就可以解决这个问题
哈希化的效率
哈希化的效率
- 如果没有产生冲突,那么效率就会更高
- 如果发生冲突,存取时间就依赖后来的探测长度(即数组每个下标对应的链表或者数组中的数据量)。
- 平均探测长度以及平均存取时间,取决于`装填因子`,随着装填因子的变大,探测的长度也越来越长。
- 装填因子
- 装填因子表示当前hash table中已经包含的数据项和整个哈希表长度的比值。
装填因子 = 总数据项 / 哈希表长度
- 开放地址法的装填因子最大为1,因为它必须寻找到空白的单元才能将元素放入
- 链地址法的装填因子可以大于1,因为拉链法可以无限延伸下去
理论上开放地址法效率要高很多。
一般情况下,当数据项已经占据哈希表长度的一半就该考虑哈希扩容
了。
哈希化中的霍纳法则(秦九韶算法)
应用在哈希函数中- 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
实现哈希表(链地址法解决哈希冲突[使用数组])
封装一个哈希函数
// 封装一个哈希函数
// - 将字符串转换成较大的数字 hashCode
// - 将较大的数字压缩到数组的范围(哈希表长度)之内
// - 返回存储的下标值位置
function hashFunc(str, size): number {
// 定义hashcode变量
let hashCode: number = null;
// 通过秦九韶算法计算hashcode值
// 将str 转换为unicode编码
for (let i = 0; i < str.length; i++) {
hashCode = 37 * hashCode + str.charCodeAt(i);
}
// 取余
let index: number = hashCode % size;
//返回下标位置
return index;
}
其中 str
是存入的数据 — 将被转换为大数字size
是设计的哈希表长度(大数字取余的值,用于压缩大数字)index
返回的在数组中的下标位置
封装哈希表
// 封装哈希表
class MyHashTable {
// 哈希表
private message: unknown[] = [];
// 哈希表中已经存放元素的个数
private count: number = 0;
// 哈希表的长度(压缩后的数组长度)
private limit: number = 10;
// 哈希函数
private runHashFunc(str: unknown, size: number): number {
return hashFunc(str, size);
}
// 哈希表插入和修改方法
alter(key: unknown, value: number): boolean {
let index: number;
// 根据key获取对应的index(下标位置)(已被哈希化)
index = this.runHashFunc(key, this.limit);
// 获取对应下标位置的数组
let bunck: unknown = this.message[index];
// 当对应下标位置没有数组时,创建数组,并将其放在对应的下标位置
if (bunck === undefined) {
bunck = [];
this.message[index] = bunck;
}
// 如果是修改操作
for (let i = 0; i < bunck.length; i++) {
// 找到对应下标的符合条件的数组组的key,修改其中的key
if (bunck[i][0] === key) {
bunck[i][1] = key;
return true;
}
}
//插入操作
bunck.push([key, value]);
this.count += 1;
return true;
}
// 获取方法
getNode(key: unknown): unknown {
// 获取index,需要使用哈希函数
let index: number = this.runHashFunc(key, this.limit);
// 找到对应下标的数组
let bunck: unknown[] = this.message[index];
// 判断在此下标内有无存入的数据
if (bunck === undefined) {
return false;
}
// 遍历对应下标的数组
for (let i: number = 0; i < bunck.length; i++) {
if (bunck[i][0] === key) {
// 有则返回对应value
return bunck[i][1];
}
}
return false;
}
// 删除方法
remove(key: unknown): boolean {
// 获取index,需要使用哈希函数
let index: number;
index = this.runHashFunc(key, this.limit);
// 找到对应下标的数组
let bunck: unknown[] = this.message[index];
// 判断在此下标内有无存入的数据
if (bunck === undefined) {
return false;
}
// 遍历对应下标的数组
for (let i: number = 0; i < bunck.length; i++) {
if (bunck[i][0] === key) {
// 找到则返回下标数组对应位置的元素(数组)
bunck.splice(i, 1);
// 包含数据的哈希表长度-1
this.count -= 1;
return true;
}
}
return false
}
//判断hash表是否为空
isEmpty():boolean{
return this.count === 0;
}
//获取哈希表元素的个数
size():number{
return this.count;
}
}
注意
value
是对应key数据的描述,数据等
测试
let hash = new MyHashTable();
hash.alter('a', 4);
hash.alter('b', 33);
hash.alter('s', 45);
hash.alter('ae', 4);
hash.alter('bg', 333);
hash.alter('rs', 444);
console.log(hash.getNode('s'));
//45
console.log(hash.getNode('a'));
//4
hash.remove('a');
console.log(hash.getNode('a'));
//false
哈希表的扩容
-
理论上,哈希表的下标位置存放的数据可以无限延伸的,但是因为随着数据量的新增,探测长度也会越来越大, 而这里的探测主要用的就是普通的遍历,导致效率越来越低,我们需要在合适得位置进行扩容
-
哈希表的扩容最好最后的容量还是为
质数
,且扩容后所有的数据都要重新插入
(因为哈希化后得到的下标位置改变了) -
扩容的时机一般是hashCode(填充因子) > 0.75的时候
扩容的实现
import {myHash} from "./实现哈希表";
// 扩容的实现
class ResizeHashTable extends myHash {
// 哈希表插入和修改方法
alter(key: unknown, value: number): boolean {
let index: number;
// 根据key获取对应的index(下标)(已被哈希化)
index = this.runHashFunc(key, this.limit);
// 当数据项数量 / 哈希表长度 = 填充因子 > 0.75
if (this.count / this.limit >= 0.75) {
console.warn('哈希表数据容量即将溢满,请及时扩容hash');
// 自动扩容两倍当前hash长度
let newSize: number = this.limit * 2,
// 获取适合长度的质数
newPirme: number = this.getPrime(newSize);
// 扩容
this.resize(newPirme);
}
// 创建长度为对应下标位置的数组
let bunck: unknown = this.message[index];
// 当对应下标位置没有数组时,创建数组,并将其放在对应的下标位置
if (bunck === undefined) {
bunck = [];
this.message[index] = bunck;
}
// 如果是修改操作
for (let i = 0; i < bunck.length; i++) {
// 找到对应下标的符合条件的元组的key,修改其中的key
if (bunck[i][0] === key) {
bunck[i][1] = key;
return true;
}
}
//插入操作
bunck.push([key, value]);
this.count += 1;
return true;
}
-------------------------------------------------------------------
//重写删除方法
remove(key: unknown): boolean {
// 获取index,需要使用哈希函数
let index: number;
index = this.runHashFunc(key, this.limit);
// 找到对应下标的数组
let bunck: unknown[] = this.message[index];
// 判断在此下标内有无存入的数据
if (bunck === undefined) {
return false;
}
// 遍历对应下标的数组
for (let i: number = 0; i < bunck.length; i++) {
if (bunck[i][0] === key) {
// 找到则返回下标数组对应位置的元素(数组)
bunck.splice(i, 1);
// 包含数据的哈希表长度-1
this.count -= 1;
// 当数据项数量 / 哈希表长度 = 填充因子 < 0.25 且最小哈希长度不能小于10
if (this.count / this.limit < 0.25 && this.limit > 10) {
// 自动缩小容量两倍当前hash长度
let newSize: number = Math.floor(this.limit / 2),
// 获取适合长度的质数
newPirme: number = this.getPrime(newSize);
// 缩小容量
this.resize(newPirme);
}
return true;
}
}
return false
}
------------------------------------------------------------
// 新增一个扩容哈希表的方法
// newLimit ---> 新的哈希表长度
resize(newLimit): boolean {
// 创建接收旧的hash表的变量
let oldHash: unknown[];
oldHash = this.message;
// 初始化当前哈希表
this.message = [];
this.count = 0;
// 使当前的哈希表长度改为新哈希表长度
this.limit = newLimit;
// 遍历出每一个下标对应位置的数据数组
for (let i: number = 0; i < oldHash.length; i++) {
// 当数组中有数据时重新插入新的哈希表
if (oldHash[i] !== undefined) {
for (let j: number = 0; j < oldHash[i].length; j++) {
// 将当前遍历出的key和value添加入新哈希表
this.alter(oldHash[i][j][0], oldHash[i][j][1]);
}
} else {
// 当当前数组中无数据则跳过
continue;
}
}
return true;
}
----------------------------------------------------------------------------------
// 获取hash整体结构
get hash(): unknown[] {
return this.message;
}
--------------------------------------------------------------------------------
// 判断质数----用于判断扩容的哈希长度是不是质数以便让数据均匀分布
private ifnum(num: number): boolean {
// 获取平方根
let sqrt: number = Math.floor(Math.sqrt(num));
// 当检查到一半时其实就没必要继续遍历判断指数了 ,就好比 3 * 2 = 2 * 2
for (let i: number = 2; i < sqrt; i++) {
if (num % i === 0) {
return false
}
}
return true;
}
--------------------------------------------------------------------------------------------------
// 获取质数
private getPrime(num: number): number {
// 接收新的长度
// 新的长度不是质数则递增
while (!this.ifnum(num)) {
num++;
}
// 是质数则返回质数
return num;
}
}
let hash = new ResizeHashTable();
hash.alter('a', 4);
hash.alter('b', 33);
hash.alter('s', 45);
hash.alter('ea', 4565);
hash.alter('ae', 4);
hash.alter('bg', 333);
hash.alter('rs', 444);
// 进行扩容
hash.resize(20);
console.log(hash.hash);
//[
// <9 empty items>,
// [ [ 'bg', 333 ] ],
// [ [ 'ae', 4 ] ],
// <2 empty items>,
// [ [ 'rs', 444 ] ],
// [ [ 'ea', 4565 ] ],
// [ [ 's', 45 ] ],
// <1 empty item>,
// [ [ 'a', 4 ] ],
// [ [ 'b', 33 ] ]
// ]