1. hash表的概念
hash表技术是直接查找技术的推广， 其主要目标是提高查找效率。
2. 几种 hash 表
<1>. 链式 hash 表。 这种 hash 表是在实际应用中最常用的 hash 表。如图所示
|------|
| |--> 1 --> 11
|------|
| |--> 2 --> 12
|------|
| |--> 3 --> 13
...
...
链式 hash 表的填入：
· 计算关键字 K 的 hash 码 i = i(k).
· 获得新的结点 P, 并将关键字 K 及有关信息填入结点P中。
· 将结点 P 链入以 H(i) 为头指针的链表的链头。
链式 hash 表的取出
· 计算关键字 K 的 hash 码 i = i(k).
· 在以 H(i) 为头指针的链表中查找关键字为 K 的结点。
<2>. 溢出 hash 表。
溢出 hash 表包括 hash 表与溢出表两部分。
在 hash 表填入过程中，将冲突的元素顺序填入到溢出表中。
而当查找过程中发现冲突时，就在溢出表中进行顺序查找。
<3>. 顺序 hash 表是一种简单的 hash 表，其中存在很多问题，在实际开发中基本上不使用。
<4>. 随机 hash 表。它与顺序 hash 表基本相同，只不过当发生冲突时它使用随即数来解决冲突。
博客 下载
论坛 开源项目
发表评论 
打印本文
推荐本文
加入收藏
返回顶部
关闭窗口
