数据结构7

数据结构 7 伸展树 哈希表

平衡树的缺陷

插入删除代价大，易出错没有利用 90 - 10 规则：百分之90的访问都是针对百分之10的数据

伸展树的概念

基本思想：让10%经常访问的数据靠近根结点基本方法：在每个结点被访问后，通过一些旋转（单）使它向根移动

但是很不幸，基本方法很容易导致树退化成单链表，这是因为单链表并不保证树高度的降低，但双旋转可以。于是我们分下面3种情况访问：

• zig 父结点为根结点：向根做一次单旋转

• zig-zag X在祖父结点内侧：LR or RL

• zig-zig X在祖父结点外侧：LL or RR

哈希表

直接根据所求结点的关键字值 KEY 找到这个结点。

直接地址法

除留余数法

H(key) = key MOD p(p 是数组大小)
p最好为质数，函数值分布更均匀

数字分析法

取数字分布均匀的位作为地址的组成部分

平方取中法

将关键字平方后，取其结果的中间各位作为散列函数值

折叠法

选取一个长度后，将关键字按此长度分组相加

哈希冲突问题

闭散列表

• 线性探测法（哈希后暴力遍历直至空）Simple
  我们还需要一个函数指针，把小数转化为整数还需额外增设一个信息，以判断是否是《曾经有过但现在已经被删除了》一段时间后，所有数组元素都变为active or deleted，所有操作的时间性能都是O(N)的（可以进行一个整理，把该删的删了，另外，最好保证表长是素数）

• 二次探测法当发生冲突时，下一个探测单元是：k+1,k+4,k+9…
  Conclusion:如果表长为素数，且表至少有一半是空的，则新元素一定可以被插入
  负载因子要小于0.5

• 再次散列法地址为 Hi = H0 + i * Hash(x)

开散列表

相当于是Linked Hash Map