散列表(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描述》
网友评论