程序员

哈希表(simple_hash_table)的实现

2019-03-24  本文已影响0人  DJ_f3ee

散列表(hash table)经常用于文件加密,数据存储中。平时我们看到的字典起始也可以看成(hash table)。

自行脑补

为什么呢,因为每个字对应着一个拼音或者解释...就像数学里的函数 y=f(x) ,x和y是天生的好基友,谁也分不开谁。

如果换一种存储方式,把字典转化一下放入电脑中存储,查找也更快,那么,我们可能要经常用到这个函数hash_func(y = f(x1,x2,x3....))这种函数,因为还是为了让每个字对应不同的拼音。即key1- >hash1                                                                                                                                 key2->hash2...                                                                                                                                        否则就难以查询了,字典也是这样,同字不同音,也容易引起误解的啊。

加密函数or hash算法

当经过hash_func的洗礼后,它们在计算机中的存储没准像上面这样。

137。。

ord(x ) 是将一个字符转换为它的整数值。 137是个质数,由于质数因子少,比如说 用10,那么当       total = 10 ,20 的时候,这个hash_key作用就很小了,那么这个质数是否能取的很大嘛,物极必反,这里就不讨论了。

当然不可避免的产生的hash_key会有冲突的时候,当然这是个小概率事件(0.05%),这时候就得改进这个hash_key算法了,比如说

尝试更大的质数;

让当 hash_key的返回值(a,a)相同时,返回值(a)加一,如果a+1还不满足,则重复a+1;

创建更大的列表,由一维变成二维,二维变成三维。

详细可见开链法和线性探测法,这里提供一种思路。

源码:https://github.com/Jiangjao/python_learn_demo/blob/master/hashmap.py

《learn-python-the-hard-way》中文版

部分图片来源:百度图片

《数据结构与算法 javascript描述》

上一篇下一篇

猜你喜欢

热点阅读