折叠法举例-复高斯分布的数学基础理论

【文件属性】：
文件名称：折叠法举例-复高斯分布的数学基础理论
文件大小：6.48MB
文件格式：PDF
更新时间：2021-06-08 13:20:40
嵌入式 Linux C 图 8.25 折叠法举例 4．除留余数法 除留余数法是取关键字被某个不大于哈希表表长 m 的数 p 除后，所得余数为哈希地址，即： H(key)=key MOD p (p<=m) 5．随机数法 随机数法是选择一个随机函数，取关键字的随机函数值作为它的哈希地址，即 H(key)= random(key)，其中 random 为随机函数，通常关键字长度不等时采用此法。 8.3.3 哈希表的处理冲突方法 就如本节前面提到：如果两个同学分别叫“刘丽”和“刘兰”，当加入刘兰时，地址 24 发生了冲突，我们可以以某种规律使用其他的存储位置，如果选择的一个其他位置仍有冲突， 则再选下一个，直到找到没有冲突的位置，选择其他位置的方法有以下 4 种。 1．开放定址法 Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m?1)，这里的 m 为表长，di 为增量序列。 � 如果 di 值可能为 1,2,3,...,m?1，则称线性探测再散列。 � 如果 di 取值可能为 1, ?1,2, ?2,4, ?4,9, ?9,16, ?16,...k*k, ?k*k(k<=m/2)，则称二次 探测再散列。 � 如果 di 取值可能为伪随机数列，则称伪随机探测再散列。 例如：在长度为 11 的哈希表中已填有关键字分别为 17、60、29 的记录，现有第 4 个记 录，其关键字为 38，由哈希函数得到地址为 5，若用线性探测再散列，如图 8.26 所示： 伪随机数列为 9,5,3,8,1... 2．再哈希法 再哈希法是指当发生冲突时，使用第二个、第三个哈希函数计算地址，直到无冲突为止， 这种方法的缺点是计算时间会显著增加。 3．链地址法 链地址法是将所有发生冲突的关键字链接在同一位置的线性链表中，如图 8.27 所示。