《哈希表-By 吴航》由会员分享，可在线阅读，更多相关《哈希表-By 吴航（2页珍藏版）》请在金锄头文库上搜索。
1、争辩报告：哈希表-By 吴航一.什么是哈希表？定义：哈希表是依据关键码值而直接进展访问的数据构造。二.算法背景。1953 年，H.P.Luhn 首先提出散列表的思想，G.M.Amdahl 首次提出开放寻址法的思想。1979 年，Carter 和 Wegman 引入全域散列函数列的概念。三.哈希表的构造。1. 思路哈希表是一种数据压缩的手段，最终的目的是把一些有着各种各样个关键字的数据字符，字符串，一些整数压缩到一张表中，使我们可以很便利的通过特定的函 数就是散列函数啦，找到表中的对应的数据而不是一个一个翻过去，空间换时间，因此，问题就成了怎么构建这个函数？2. 怎么构建呢？1） 直接寻址法顾名
2、思义，就是依据关键字直接寻址。H(x)=x2） 数字分析法通过分析题目中的关键字找散列函数。3） 平方取中法取关键字平方后的中间几位为哈希地址。4） 折叠法将关键字分割成位数一样的几局部最终一局部的位数可以不同，然后取这几局部的叠加和舍去进位作为哈希地址，这方法称为折叠法。例：13824769138 247 69H13824769=138+247+69 mod 1000=4545） 除留余数法取关键字被某个不大于哈希表表长m 的数 p 除后所得余数为哈希地址。(H(key)=key MOD p (p=m)，p 最好取大质数。6） 随机数法选择一个随机函数，取关键字的随机函数值为它的哈希地址。2
3、.冲突了？有的时候，会消灭这样的状况两个关键字递归到同一地址。怎么办呢？1开放地址法假设冲突了，明显要是再存在这就掩盖了对吧，因此，我们需要再找一个 建立数组di，假设 Hi冲突，就找 Hi=(Hi+di) mod p(p 为哈希表总长度) 下一个问题随之而来：di怎么构建？方法A:di 1，2，3， 线性探测再散列；方法 B:di 12，12，22，22， 二次探测再散列； 方法 C:di 伪随机序列 伪随机再散列；PS:后面的术语有点四.效率。好不简洁构造完了，现在直接调用就可以了。效率飞速提升！等一下，效率真的提升了吗？构建的时候效率好似有点高效率比照图时间效率一般方法哈希表数据规模上图为一般方法与哈希表用于构建和查找的总时间的比照图该表反响大多数的状况而非特例。屡次试验说明，其他方法在数据太少数据才这么点，你还在构建哈希表它已经完毕了或太多冲突冲突冲突冲突冲突时是不行靠的
