清华大学出版社 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