【数据结构重温】哈希表_已知一组关键字序列为{5,88,12,56,71,28,33,43,93,17},哈希表长为13,哈-程序员宅基地

技术标签： U.数据结构与算法存储数据结构

1. 哈希表

(1) 哈希表(散列表，杂凑表)

根据设定的哈希函数和处理冲突的方法，将一组关键字映像到一个有限的连续的地址集上，并以关键字在地址集中的象作为记录在表中的存储位置，这种表称为哈希表，又叫散列表，杂凑表。

(2) 哈希函数

常用除留余数法。H(key) = key MOD p。

(3) 冲突

什么是冲突？H(key₁)=H(key₂)，且key₁≠key₂，称冲突。

处理冲突的方法：当H(key)处已有记录，出现冲突，如何处理？

1°. 开放定址法

试用H(key)⊕d_i，常见以下三种。

(1) 线形探测再散列：试用H(key)⊕1，H(key)⊕2，...

(2) 二次探测再散列：试用H(key)⊕1²，H(key)⊕-1²，H(key)⊕2²，H(key)⊕-2²，...

(3) 伪随机探测再散列：试用H(key)⊕f(1)，H(key)⊕f(2)，...

2°. 再哈希法

H₁(key)冲突，试用H₂(key)，H₃(key)，...

3°. 链地址法

发生冲突的记录链成单链表。

4°. 建立公共溢出区

所有冲突记录存入溢出区。

(4) 装填因子

n个记录，m个地址空间。

哈希表的平均查找长度与记录个数n不直接相关，而是取决于装填因子和处理冲突的方法。

(5) 举例

例：已知一组关键字{19, 14, 23, 1, 68, 20, 85, 9}，采用哈希函数H(key)=key MOD 11，请分别采用以下处理冲突的方法构造哈希表，并求各自的平均查找长度。

1) 采用线性探测再散列；

2) 采用伪随机探测再散列，伪随机函数为f(n) = - n；

3) 采用链地址法。

思路：开始时表为空，依次插入关键字建立哈希表。

1) 线性探测再散列

key 19 14 23 1 68 20 85 9 ß 关键字

H(key) 8 3 1 1 2 9 8 9 ß H(key)

2 3 9 10 ß 冲突时计算下一地址

4 10 0 ß

查找长度 1 1 1 2 3 1 3 3 ß 每个关键字的查找长度

ASL = (1+1+1+2+3+1+3+3)/8 = 15/8

2) 伪随机探测再散列

key 19 14 23 1 68 20 85 9

H(key) 8 3 1 1 2 9 8 9

0 7 8

查找长度 1 1 1 2 1 1 2 4

ASL = (1+1+1+2+1+1+2+4)/8 = 13/8

3) 链地址法

ASL = (1×5+2×3)/8 = 11/8

注：关键字在链表中的插入位置可以在表头或表尾，也可以在中间以便保持关键字有序。

最后，此哈希表的装填因子是α= 8/11。

本文链接：https://blog.csdn.net/do2jiang/article/details/5531106

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

web前端培训分享JavaScript学习笔记分支结构_if(ture)前端-程序员宅基地

文章浏览阅读169次。web前端培训分享JavaScript学习笔记分支结构，我们的 js 代码都是顺序执行的（从上到下）逻辑分支就是根据我们设定好的条件来决定要不要执行某些代码IF 条件分支结构if 语句· 通过一个 if 语句来决定代码执行与否a· 语法： if (条件) { 要执行的代码 }· 通过 () 里面的条件是否成立来决定 {} 里面的代码是否执行// 条件为 true 的时候执行 {} 里面的代码if (true) {alert(‘因为条件是 true，我会执行’)}// 条件为 false 的_if(ture)前端

Java ExecutorService四种线程池的例子与说明_java executorservice 多线程例子-程序员宅基地

文章浏览阅读160次。一、为什么使用线程池使用new Thread执行多个线程有如下一些问题：每次new Thread新建对象性能差。线程缺乏统一管理，可能无限制新建线程，相互之间竞争，及可能占用过多系统资源导致死机或oom。缺乏更多功能，如定时执行、定期执行、线程中断。相比new Thread，Java提供的四种线程池的好处在于：重用存在的线程，减少对象创建、消亡的..._java executorservice 多线程例子

高级映射(一)：一对一、一对多，多对多查询总结_购物车和商品是一对多还是多对多-程序员宅基地

文章浏览阅读2w次，点赞2次，收藏18次。多表之间的数据交互其实一对一和一对多映射，在前面的配置中已经接触到，我没在日志里直接说明，是因为想要在之后写一篇总结日志（就是本篇），总结这些高级映射的配置。例如一对一查询在关联的嵌套结果集查询中就涉及到，一对多查询则在这个基础上再加上一个或多个嵌套结果集，它们可以是一个实体类，或者是一个集合。多对多查询稍微有点复杂，举个例子来说，一个商城管理系统中，一名顾客在一个购物清单中可以有多件商品，而..._购物车和商品是一对多还是多对多

值得关注的 CI/CD 主要趋势-程序员宅基地

文章浏览阅读909次，点赞10次，收藏9次。CI/CD 是那些想要加速应用程序交付、发布周期、控制成本并降低开发风险的人的首选。适应用户反馈、提高对市场变化和业务优先级的响应能力以及提升竞争力取决于应用程序质量，CI/CD 成为提高开发速度的宝贵推动者。

个推图可视化应用实践_d3js和g6|graphin对比-程序员宅基地

文章浏览阅读5.2k次。个推资深前端开发专家东风图可视化应用是数据可视化的一个重要组成部分。图指的是知识图谱（Knowledge Graph），此概念于2012年由Google正式提出，旨在帮助Google优化搜索引擎返回的结果，提升用户搜索质量及体验。个推作为专业的数据智能服务商，在图可视化应用方面也进行了丰富的实践。本文将从四部分讲述图可视化应用：应用场景、组成部分、个推图可视化组件、个推图可视化展望。（文末附视频版讲解及完整资料下载）01图可视化应用场景..._d3js和g6|graphin对比

LSM-Tree 与 RocksDB_rocksdb 和lsmtree的区别-程序员宅基地

文章浏览阅读1.3k次。冥冥之中，接触到了不同于关系数据库的NoSQL Key-Value存储引擎RocksDB，懵懵懂懂、充满好奇，google一点，满眼皆是LSM-Tree，头晕眼花、若即若离，便有了这篇文章，一起与大家分享这趟探险之旅。LSM-Tree(Log-Structured-Merge-Tree)LSM从命名上看，容易望文生义成一个具体的数据结构，一个tree。但LSM并不是一个具体的数据结构，也不是一..._rocksdb 和lsmtree的区别