数据结构--哈希表，哈希函数（或者散列表、散列函数）

 目录

哈希表的定义

处理冲突的方法--拉链法 

散列查找

常见的散列函数（构造哈希函数）

除留余数法

直接定址法

 数字分析法

平方取中法

处理冲突的方法--开放定址法

（1）线性探测法： 

（2）平方探测法

（3）伪随机序列发 

处理冲突的方法--再散列法 

总结 

---

 哈希表的定义

处理冲突的方法--拉链法 

散列查找

圈出来部分，分别是除了第一层查找1次，其他每个元素查找次数 

 

装填因子a=表中记录数/散列表长度

 

常见的散列函数（构造哈希函数）

除留余数法

直接定址法

 数字分析法

平方取中法

 

处理冲突的方法--开放定址法

 

（1）线性探测法： 

 把元素1放到数组2位置，然后接着算68，20....

  

 68和20按照哈希函数取余，分别是3，7，而数组下标3，7还没有存放与元素，所以没有冲突，可以直接放进数组对应的下标里面，如图：

接着放84时，按照哈希函数取余时6，6已经有元素放了，所以按照线性推测法 公式算，依次往后找，找到8下标没有元素，所以84放到下标8那里

存放84的结果如下：

 

然后是27： 

 

存放27的结果

 

删除操作 

 

 

（2）平方探测法

 

 

（3）伪随机序列发 

 

 存放结果：

处理冲突的方法--再散列法 

总结 

装填因子，线性探测法很重要