首页 > 代码库 > 哈希表查找速度为什么那么快?快在哪里了?

哈希表查找速度为什么那么快?快在哪里了?

先看数组存储数据是怎么样的。

现在有一个数组,它里面每个单元存储的是数据的地址

这叫指针数组吧,假设它有100个单元

我们称他为p[100]

现在我想把一百个数据(地址)放到里面

我们想把某个数据放到p的第几个单元完全是由

我们决定的,可以说想怎么放就怎么放

是一种乱放,既然是乱放,那么查找起来就比较耗时。

 

哈希表是怎么存储数据的呢?

哈希表同样是一个指针数组。

同样需要存储100个数据,需要的就不是100个单元了,因为哈希表要把某个数据存放在某个单元不是随机的一个过程,而是算出来的,这个算法叫哈希函数

比如要存储一个数据对

张三 1882356

李四  23456789

王五  58856456

张三经过哈希函数算出来的值是138,那么哈希表最少需要138个单元,因为张三对应的数据1882356要存储在指针数组的p[138]的位置上。

李四经过哈希函数算出来的值是500,那么2356789这个数据就要存放在p[500]这个位置上。

所以你明白了,"数据的地址放在指针数组的哪个单元格是算出来的,是有迹可寻的,并不是想放在哪里就放在哪里"

那查找的时候就好查找了,你要查找张三对应的数据,

直接把张三用哈希函数算一下,得到138,哦 张三的数据就在p[138]这个位置上,所以一下就找到了。

 

哈希表是一个key- value的数据对,p是一个指针数组,用来存放value的地址,那么key和value的关系是下面这样的。

p[f(key)]=&value

 

可以看出哈希表有时候会浪费很大空间的,比如上面张三 李四 王五那个例子 如果按照哈希表存储要定义一个500个大小的指针数组。怎么解决这个问题呢?我再看看书。

 

哈希表查找速度为什么那么快?快在哪里了?