hash table哈希表

原创
2016/11/02 15:46
阅读数 42

stl的map使用红黑树来存储数据,可以在O(log n)时间内找到目标。
hash table也可以在常数时间内找到目标。但是数据结构却完全不一样。
他采用一个数组来存放数据,通过数据的key来直接找到他在数组中的存放位置。
比如长度为10的数组 array[10],我们可以通过 x%10来找到x的存放位置,2就应该存放在array[2]。这个查找元素位置的方法(x%10)就称为散列函数,当然还有很多不同的散列函数
如果我们再放入12,那么得到的位置 也是在array[2]。此时就发生了冲突。解决这类问题有如下方法。
1 开放地址法:
线性探测法:在目标位置H开始,依次往下查找空位。这种方法简单,但是效率比较低
二次探测法:在目标位置H被占用后,并不是往下依次查找,而是在H+1*1、H+2*2、H+3*3...依次查找空位
Rehash法:在目标位置H被占用后,再用第二个函数ReHash()来确定新的位置,可以通过H移动步长来实现
2 开链法
在每个key对应的位置存放一个链表。此时的数组的每个单元可以称作hash桶

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部