美文网首页程序员
哈希表(simple_hash_table)的实现

哈希表(simple_hash_table)的实现

作者: DJ_f3ee | 来源:发表于2019-03-24 21:58 被阅读0次

    散列表(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描述》

    相关文章

      网友评论

        本文标题:哈希表(simple_hash_table)的实现

        本文链接:https://www.haomeiwen.com/subject/kxepvqtx.html