Hash Table
散列表,实际上也可以叫做Hash Table. 他其实是一种数据结构, 类似字典也是key/value pair. 或者应该说,是字典 base on Hash Table. 因为散列表才是真正的key/value pair. 而本质上,hash table 的结构, 是在key与value之间加上一层映射函数的.
首先, 我们的值都是存在RAM中的, 并且都有表示的唯一id.(前文介绍过,python中有id()方法,可以找到value的RAM地址). 如上图所示. 里面的buckets 实际上是一个列表的数据类型, 并且,每一个位置都有唯一的一个索引进行标识. 我们的key, 通过hash function 最终找到那个index, 然后从buckets中取回value. 就是这样的一个过程.
所以,散列表的特点是, 删除,插入,取出数据很快(O(1)), 但是如果涉及到值查找,则效率就相当低了.
Hash Table 映射
经过上面的介绍, 了解散列表实际上 最重要的部分是hash function. 他的原理过程是这样的:
# hash functionhash = hashfunc(key)index = hash % array_sizearray_size 就是存储内容的总长度. hashfunc通过key映射出来一个值, 经过取余操作,得到一个index 这就是值的地址. 但是, 有没有可能出现,两个key经过处理,映射出同一个key值?
从概率上来说,是很有可能的. 在Hash Table 中叫做 collision. 所以, 一个完备的Hash Table 必须有个planB 去解决这样的现象.
另外,Hash Table 的长度是预先设定好的(最好是prime number--质数->137), 但长度是可变的。 其中, 初始化一个Hash Table的长度真的是一个数学问题, 关系到构建一个hash function的难度.
Building a Hash Table
一个基本的Hash Table 应该具有 存储内容的 associated array,映射关系的 hash function 两个基本tip.
所以, 我们可以创建一个Hash Table 类
class HashTable{ constructor(){ this.table = new Array(137); this.hash_function = xxx }}一个hash映射函数, 有一个比较简单的, 取余法~ 即, 当你的键值为整数的时候, 通过对其进行数组长度的取余:(上面说到过)
index = hash % array_size得到你的index值。 聪明的童鞋,可能会联想到上面要求键长为质数 就是这个道理. 如果你的size是一个合数, 那么, 当hash值大于size时, 出现碰撞的可能性, 将会上升一个level. 即, 质数是一个唯一性的选择. 上面,你也可以不用137, 你可以替代为自己想要的长度, 但记住,大一点好.
当,我们的键值为Number类型的话, 那么上面的hash_function就可以写为:
class HashTable{ constructor(){ this.size = 137; this.table = new Array(this.size); } hash_function(key){ return key%this.size; } add(key,value){ let index = this.hash_function(key); this.table[index] = value; }}如果键值是使用Number类型的话, 估计这种数据结构基本上就蹲墙角了. 一般情况下, key 是String类型的. 所以, 这就给hash_function 增加难度了. 将String转换为数字的办法在每种编程语言里面都有, 这里以js为例, 在js中,提供了charCodeAt()来找出, 对应字符在Unicode(0xnnnnnn)里面的序号. 英文字符还好,都是在ASCII编码占据前排的位置, 但是Chinese不一样, 是国人后面硬加进去的. 如果你用一些生僻字作为键名的话, 我送你两个字 呵呵 .因为, 如果这些生僻字在字符表中的位置大于65536,charCodeAt()是找不出来的, 你只能使用,还未普遍支持的codePointAt.
两个方法的基本格式为:
str.charCodeAt(index): index 就是字母出现的顺序. 返回Number. 兼容性很好
str.codePointAt(index): 同上. 只是兼容性差一点, 但对字符的检测更全.
这里我们先使用charCodeAt来实现String 转 Number的效果.
hash_function(key){ let num=0; for(var i=0;i这里有一个公式,常常 可以帮助我们选择使用哪种碰撞解决办法:如果数组的大小是待存储数据个数的 1.5 倍, 那么使用开链法;如果数组的大小是待存储数据的两倍及两倍以上时,那么使用线性探 测法。接下来,我们用代码来模拟一下.class HashTable{
constructor(){
this.size = 137;
this.keys = new Array(this.size);
this.values = new Array(this.size);
}
hash_function(key){
let num=0;
for(var i=0;i
关键字：数据结构, table, hash, index
版权声明
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！
