清华大学：《实用数据结构》课程教学资源（PPT课件）第八章 Hash表技术第8章

清华大学出版社 TSINGHUA UNIVERSITY PRESS 第8章Hash表技术 8.1Hash表的基本概念 8.2几种常用的Hash表

第8章 Hash表技术 8.1 Hash表的基本概念 8.2 几种常用的Hash表

清华大学出版社 TSINGHUA UNIVERSITY PRESS 8.1Hash表的基本概念 8.1.1直接查找技术 8.1.2Hash表 8.1.3Hash码的构造

8.1 Hash表的基本概念 8.1.1 直接查找技术 8.1.2 Hash表 8.1.3 Hash码的构造

清华大学出版社 TSINGHUA UNIVERSITY PRESS 8.1Hash表的基本概念 8.1.1直接查找技术 设表的长度为n。如果存在一个函数i=i(k),对于表中 的任意一个元素的关键字k,满足以下条件: (1)1≤i≤n; (2)对于任意的元素关键字k1≠k2,恒存在i(k1)≠i(k2) 则称此表为直接查找表。其中函数i=i(k)称为关键字k 的映象函数

8.1 Hash表的基本概念 8.1.1 直接查找技术 设表的长度为n。如果存在一个函数i＝i(k)，对于表中 的任意一个元素的关键字k，满足以下条件： (1)1≤i≤n； (2)对于任意的元素关键字k1≠k2，恒存在i(k1)≠i(k2)。 则称此表为直接查找表。其中函数i＝i(k)称为关键字k 的映象函数

清华大学出版社 TSINGHUA UNIVERSITY PRESS 8.1Hash表的基本概念 1.直接查找表的填入 要将关键字为k的元素填入到直接查找表,只需做以下两 步: (1)计算关键字k的映象函数i=i(k); (2)将关键字k及有关元素信息填入到表的第i项

8.1 Hash表的基本概念 1.直接查找表的填入 要将关键字为k的元素填入到直接查找表，只需做以下两 步： (1)计算关键字k的映象函数i＝i(k)； (2)将关键字k及有关元素信息填入到表的第i项

清华大学出版社 TSINGHUA UNIVERSITY PRESS 8.1Hash表的基本概念 2.直接查找表的取出 要在直接査找表中取出关键字k的元素,也只需做以下两 步: (1)计算关键字k的映象函数i=i(k); (2)检查表中第i项: 若第i项为空,则说明表中没有关键字为k的元素; 否则取出第i项中的元素即可

8.1 Hash表的基本概念 2.直接查找表的取出 要在直接查找表中取出关键字k的元素，也只需做以下两 步： (1)计算关键字k的映象函数i＝i(k)； (2)检查表中第i项： 若第i项为空，则说明表中没有关键字为k的元素； 否则取出第i项中的元素即可

清华大学出版社 TSINGHUA UNIVERSITY PRESS 8.1Hash表的基本概念 8.1.2Hash表

8.1 Hash表的基本概念 8.1.2 Hash表

清华大学出版社 TSINGHUA UNIVERSITY PRESS 8.1Hash表的基本概念 例 将关键字序列(09,31,26,19,01,13,02,11,27 ,16,05,21)依次填入长度为n=12的表中。设映象函 数为i=INT(k/3)+1 表项序号 12345678910112 按i=Ix3)+10105 0913161921262731 填入的关键字k02

8.1 Hash表的基本概念 例 将关键字序列(09，31，26，19，01，13，02，11，27 ，16，05，21)依次填入长度为n＝12的表中。设映象函 数为i＝INT(k/3)＋1

清华大学出版社 TSINGHUA UNIVERSITY PRESS 8.1Hash表的基本概念 设表的长度为n。如果存在一个函数i=i(k),对于表中 的任意一个元素的关键字k,满足1≤i≤n,则称此表 为Hash表。其中函数i=i(k)称为关键字k的Hash码 (1)构造合适的Hash码,以便尽量减少表中元素冲突的次 数。即Hash码的均匀性要比较好 (2)当表中元素发生冲突时,要进行适当的处理

8.1 Hash表的基本概念 设表的长度为n。如果存在一个函数i＝i(k)，对于表中 的任意一个元素的关键字k，满足1≤i≤n，则称此表 为Hash表。其中函数i＝i(k)称为关键字k的Hash码。 (1)构造合适的Hash码，以便尽量减少表中元素冲突的次 数。即Hash码的均匀性要比较好。 (2)当表中元素发生冲突时，要进行适当的处理

清华大学出版社 TSINGHUA UNIVERSITY PRESS 8.1Hash表的基本概念 8.1.3Hash码的构造 (1)使各关键字尽可能均匀地分布在Hash表中,即Hash码 的均勺性要好,以便减少冲突发生的机会 (2)Hash码的计算要尽量简单

8.1 Hash表的基本概念 8.1.3 Hash码的构造 (1)使各关键字尽可能均匀地分布在Hash表中，即Hash码 的均匀性要好，以便减少冲突发生的机会。 (2)Hash码的计算要尽量简单

清华大学出版社 TSINGHUA UNIVERSITY PRESS 8.1Hash表的基本概念 1.截段法 2.分段叠加法 3.除法 i=mod(k, n) 4乘法 i=mod(k*φ,n) φ一般取0.61803988747,或0.6125423371, 或0.6161616161

8.1 Hash表的基本概念 1.截段法 2.分段叠加法 3.除法 i＝mod(k，n) 4.乘法 i＝mod(k*φ，n) φ一般取0.618033988747，或0.6125423371， 或0.6161616161