跳转至

15. 哈希动态查找

阅读信息

约 324 个字  2 分钟  本页总访问量：加载中... 次

Class Fifteen

哈希动态查找问题

  1. 查找树，只要解决树的平衡的问题
  2. 计算，设计函数（哈希函数）

避免冲突：

  1. 牺牲空间（以空间换时间）

开放地址法,二次探测 Thm. 如果满足:

  1. 求余时用素数
  2. 至少有一半位置空 则可以证明有新的元素,则一定可以找到位置.

Pf:首先证明,如果 i,j 满足\(0<i\neq j\le tablesize/2\), 则

$(h(x)+i^2)\% tablesize \neq (h(x)+j^2)\%tablesize $.

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
position find (int key, hash H) {
  position pos;
  int colliNum;
  pos = hash(key, H.size());
  while (H[pos]非空 && H[pos].Element != key) {
    pos += 2 * ++colliNum - 1;   // 将平方变为乘2，加快计算速度
    if (pos > H.size())
      pos -= H.size();
  }
  return pos;
}

f(i)也可以时哈希函数(double hash 方法) 示例：f(i) = i * hash(key), f(i) = R - i * hash(key)

Rehashing 方法 将原来的哈希表扩大一倍，将原来其中所有元素重新算一遍 什么时候需要 rehash？可能有以下几种情况：

  1. 插入时冲突多，设置几次插入中冲突在几次以上，进行 rehash
  2. 表的装载率超过设定时 rehash
  3. 插入时找不到位置

另外

堆合并

每次取两树顶点的最小值作为合成后顶点，一颗子树直接作为合并后顶点的一个子树，另一个子树和合并前的另一个树合并（递归） 最左堆：不维护完全二叉树的特性，全部偏向左边

需要熟练掌握的程序

出入栈，出入队列，二叉树的左中右层次遍历，非递归遍历，堆的插入删除，查找树的查找插入删除， 图的 bfs dfs，最短路径，拓扑排序， （森林的遍历）