第08章 哈希表

第8章哈希表 数据结构 C 语言描述 配套PPT北京大学出版社制作 陈广博客 数据结构 C 语言描述 配套PPT 引入 数据结构 C 语言描述 配套PPT 在C 的万物之母object对象中定义了一个虚方法GetHashCode 这个方法用于获取对象的哈希码 什么是哈希码 它有什么作用 为什么要在如此重要的类中定义这个方法 哈希码跟哈希表有什么内在的联系吗 本章将对这些问题展开论述 8 1概念引入 数据结构 C 语言描述 配套PPT 例8 1Demo8 1 cs 使用学号查找学生地址 例8 2Demo8 2 cs 哈希查找 8 2构造哈希函数的方法 数据结构 C 语言描述 配套PPT 构造哈希函数的目标是使哈希地址尽可能均匀地分布在连续的内存单元地址上 以减少冲突发生的可能性 同时使计算尽可能简单以达到尽可能高的时间效率 根据关键字的结构和分布不同 可构造出与之适应的各不相同的哈希函数 这里主要讨论几种常用的整数类型关键字的哈希函数构造方法 8 2构造哈希函数的方法 数据结构 C 语言描述 配套PPT 直接定址法取关键字或关键字的某个线性函数为哈希地址 即 h key key或h key a key b其中a b为常数 调整a与b的值可以使哈希地址取值范围与存储空间范围一致 这种哈希函数计算简单 并且不会有冲突发生 它适合于关键字的分布基本连续的情况 若关键字分布不连续 将造成存储空间的大量浪费 8 2构造哈希函数的方法 数据结构 C 语言描述 配套PPT 该方法是提取关键字中随机性较好的数字位 然后把这些数位拼接起来作为哈希地址 它适合于所有关键字值都已知的情况 并需要对关键字中每位的取值分布情况进行分析 8 2构造哈希函数的方法 数据结构 C 语言描述 配套PPT 除留余数法采用取模运算 把关键字除以某个不大于哈希表表长的整数得到的余数作为哈希地址 哈希函数的形式为 h key key p除留余数法的关键是选好p 使得记录集合中的每个关键字通过该孩子数转换后映射到哈希表范围内任意地址上的概率相等 从而尽可能减少发生冲突的可能性 8 3哈希冲突解决方法 数据结构 C 语言描述 配套PPT 哈希函数的目标是尽量减少冲突 但实际应用中冲突是无法避免的 所以在冲突发生时 必须有相应的解决方案 而发生冲突的可能性又跟以下两个因素有关 装填因子 所采用的哈希函数 8 3哈希冲突解决方法 数据结构 C 语言描述 配套PPT 冲突解决技术可分为两大类 开散列法 又称为链地址法 和闭散列法 又称为开放地址法 哈希表是用数组实现的一片连续的地址空间 两种冲突解决技术的区别在于发生冲突的元素是存储在这片数组的空间之外还是空间之内 8 3哈希冲突解决方法 数据结构 C 语言描述 配套PPT 闭散列法是把所有的元素存储在哈希表数组中 当发生冲突时 在冲突位置的附近寻找可存放记录的空单元 寻找 下一个 空位的过程称为探测 上述方法可用如下公式表示 hi h key di m其中i 1 2 k k m 1 其中h key 为哈希函数 m为哈希表长 di为增量的序列 根据di取值的不同 可以分成几种探测方法 8 3哈希冲突解决方法 数据结构 C 语言描述 配套PPT 线性探测法的基本思想是 当发生冲突时 从冲突位置的下一个单元顺序寻找 只要找到一个空位 就把元素放入此空位中 顺序查找时 把哈希表看成一个循环表 即如果到最后一个位置也没有找到空位 则回到表头开始继续查找 此时 如果仍然未找到空位 则说明哈希表已满 需要进行溢出处理 8 3哈希冲突解决方法 数据结构 C 语言描述 配套PPT 已知一组关键字为 12 19 23 28 39 51 56 76 84 哈希表长m 13 哈希函数为 h key key 11 key h key 比较次数 插入12h key 12 11 1 插入28h key 28 11 6 插入19h key 19 11 8 插入23h key 23 11 1 插入39h key 39 11 6 插入56h key 56 11 1 插入76h key 76 11 10 插入51h key 51 11 7 插入84h key 84 11 7 8 3哈希冲突解决方法 数据结构 C 语言描述 配套PPT 每个元素经哈希函数计算出来的地址称为基地址 这种不同基地址的元素争夺同一个单元的现象叫做二次聚集 二次聚集实际上是在处理同义词之间的冲突时引发的非同义词的冲突 显然 这种现象对查找不利 线性探测很容易出现二次聚集 小的聚集能汇合成大的聚集 最终导致很长的探测序列 从而降低哈希表的运算效率 8 3哈希冲突解决方法 数据结构 C 语言描述 配套PPT 线性探测法的缺点是容易出现二次聚集 为了减少二次聚集的产生 可以加大探测序列的步长 使发生冲突的元素的位置比较分散 如果在地址i产生冲突 不是探测i 1地址 而是探测i 12 i 12 i 22 i 12 的地址 该方法的优点是可以减少二聚集的产生 缺点是不易探测到整个哈希空间 8 3哈希冲突解决方法 数据结构 C 语言描述 配套PPT 双重散列法又称二度哈希 是闭散列法中较好的一种方法 它是以关键字的另一个散列函数值作为增量 设两个哈希函数为 h1和h2 则得到的探测序列为 h1 key h2 key m h1 key 2h2 key m h1 key 3h2 key m 其中 m为哈希表长 由此可知 双重散列法探测下一个开放地址的公式为 h1 key i h2 key m 1 i m 1 8 3哈希冲突解决方法 数据结构 C 语言描述 配套PPT 定义h2的方法较多 但无采用什么方法都必须使h2 key 的值和m互素才能使发生冲突的同义词地址均匀地分布在整个哈希表中 否则可能造成同义词地址的循环计算 若m为素数 则h2取1至m 1之间的任何数均与m互素 因此可以简单地将h2定义为 h2 key key m 2 1 8 3哈希冲突解决方法 数据结构 C 语言描述 配套PPT 开散列法的常见形式形式是将所有关键字为同义词的结点链接在同一个单链表中 每个单链表中除了表头指针存储在哈希表数组中以外 所有元素都存储在数组以外的空间 哈希表没有 边界 这也是 开散列法 名称的来源 8 3哈希冲突解决方法 数据结构 C 语言描述 配套PPT 关键字为 12 19 23 28 39 51 56 76 84 哈希表长m 13 哈希函数为h key key 11 如果使用开散列法进行存储 元素插入单链表时总是插在表头作为第一个结点 设插入顺序为 12 28 19 23 39 56 76 51 84 其结果将如图所示 56 23 12 39 28 84 51 19 76 8 3哈希冲突解决方法 数据结构 C 语言描述 配套PPT 与开放地址法相比 链地址法有如下优缺点 优点 使用链地址法处理冲突无二次聚集现象 因此平均查找长度较短 由于链地址法中各链表上的结点空间是动态申请的 因此适合于无法确定表长的情况 在用链地址法构造的哈希表中 删除结点的操作易于实现 只要删除链表上相应的结点即可 缺点 指针需要额外空间 故当记录规模较小时 闭散列法较为节省空间 在 NET中 链表的各个元素分散于托管堆各处 这会给自动垃圾回收带来压力 影响程序性能 8 4剖析System Collections Hashtable 数据结构 C 语言描述 配套PPT C 中实现了哈希表数据结构的集合类有 System Collections HashtableSystem Collections Generic Dictionary前者为一般类型的哈希表 后者是泛型版本的哈希表 Dictionary和Hashtable之间并非只是简单的泛型和非泛型的区别 两者使用了完全不同的哈希冲突解决办法 8 4剖析System Collections Hashtable 数据结构 C 语言描述 配套PPT object类中定义了一个GetHashCode 方法 这个方法默认的实现是返回一个唯一的整数值以保证在object的生命期中不被修改 GetHashCode 方法使得C 中的所有类型都能以唯一的数字值来表示 由于GetHashCode 方法是一个虚方法 可以通过重写这个方法来构造自己的哈希函数 8 4剖析System Collections Hashtable 数据结构 C 语言描述 配套PPT Hashtable使用了闭散列法来解决冲突 它通过一个结构体bucket来表示哈希表中的单个元素 这个结构体中有三个成员 key 表示键 即哈希表中的关键字 val 表示值 即跟关键字所对应值 hash coll 它是一个int类型 用于表示键所对应的哈希码 8 4剖析System Collections Hashtable 数据结构 C 语言描述 配套PPT Hashtable解决冲突使用了双重散列法 但又跟前面所讲的双重散列法稍有不同 它探测地址的方式为 h key i h1 key i h2 key 其中哈希函数h1和h2的公式如下 h1 key key GetHashCode h2 key 1 h1 key 5 1 hashsize 1 由于使用了二度哈希 最终的h key i 的值有可能会大于hashsize 所以需要对h key i 进行模运算 最终计算的哈希地址为 哈希地址 h key i hashsize Hashtable动态演示程序网址 8 5剖析Dictionary 数据结构 C 语言描述 配套PPT 8 5 1 Dictionary的实现原理 Dictionary的哈希地址求解较之Hashtable简单许多 哈希地址 key GetHashCode hashsizeDictionary内有两个数组 一个数组名为buckets 用于存放由多个同义词组成的静态链表头指针 另一个数组名为entries 它用于存放哈希表中的实际数据 同时这些数据通过next指针构成多个单链表 8 5剖析Dictionary 数据结构 C 语言描述 配套PPT 8 5 1 Dictionary的实现原理 buckets中所存放的是Entry结构体 它由四个部分组成 key 元素的键value 元素的值hashCode 元素的哈希码next 指向哈希表中下一个同义词的指针 实际为下一个同义词在数组中的索引 当不存在下一个同义词时 next的值为 1 8 5剖析Dictionary 数据结构 C 语言描述 配套PPT 8 5 1 Dictionary的实现原理 为了正确添加和删除元素 Dictionary内部维护了三个成员变量 countfreeCountfreeList 运行虚拟Dictionary 8 6本章小结 数据结构 C 语言描述 配套PPT 本章介绍了哈希表及C 中在现了哈希表的两个集合类Hashtable和Dictionary 两种哈希表的区别如下 Hashtable使用了闭散列法来解决冲突 而Dictionary使用了开散列法解决冲突 Dictionary相对Hashtable来说需要更多的存储空间 但它不会发生二次聚集的情况 并且由于使用泛型实现 Dictonary的速度更快些 Hashtabl