学习视频

传送门

哈希表，是既能具备数组的快速查询的优点，又能融合链表方便快捷的增加删除元素的优势。

所谓的hash,简单的说就是散列，即将输入的数据通过hash函数得到一个key值，输入的数据存储到数组中下标的key值的数组单元中去。

处理冲突的方式：（着重讲两个）

一、开发定址法：

方法：

令Hi=（H（key）+di）%m,i=1,2,3......,m-1。其中H(key)为哈希函数，m为哈希表长，di为增量序列。

• 若取di=1，2，3....,m-1 ,则称为线性探测再散列 ；
• 若取di=1²,-1²,2²,-2².....,±k² ，则称为二次探测再散列 ；

---

假设一组关键字{19，01，23，14，55，68，11，82，36}，哈希函数为H(key)=key%11（表长11）,用线性探测再散列法处理冲突。

根据哈希函数，来计算关键字的地址。

1. 若采用线性探测再散列处理冲突 di=1，2，3.....,m-1
2. 19%11=8
3. 01%11=1
4. 23%11=1 （1+1）%11=2
5. 14%11=3
6. 55%11=0 
7. 68%11=2 （2+1）%11=3 （2+2）%11=4 
8. 11%11=0 （0+1）%11=1 （0+2）%11=2 （0+3）%11=3 （0+4）%11=4 （0+5）%11=5
9. 82%11=5 （5+1）%11=6
10. 36%11=3 （3+1）%11=4 （3+2）%11=5 （3+3）%11=6 （3+4）%11=7

• 若采用二次探测再散列处理冲突 di =1²,-1²,2²,-2².....,±k²

1. 19%11=8
2. 01%11=1
3. 23%11=1 （1+1）%11=2
4. 14%11=3
5. 55%11=0
6. 68%11=2 （2+1）%11=3 （2-1）%11=1 （2+4）%11=6
7. 11%11=0 （0+1）%11=1  （0-1）%11=10
8. 82%11=5 
9. 36%11=3 （3+1）%11=4

通过以上两种方法的比较，可以发现用二次探测再散列处理冲突的效率就会高一些。

 

二、链地址法：

设有一组关键字{67，84，18，26，34，28}，哈希函数为H(key)=key%7，用链地址法处理冲突 ，

根据哈希函数，来计算关键字的地址。

---

题目来源

7-17 电话聊天狂人（25 分）

给定大量手机用户通话记录，找出其中通话次数最多的聊天狂人。

输入格式:
输入首先给出正整数N（≤10​5​​），为通话记录条数。随后N行，每行给出一条通话记录。简单起见，这里只列出拨出方和接收方的11位数字构成的手机号码，其中以空格分隔。

输出格式:
在一行中给出聊天狂人的手机号码及其通话次数，其间以空格分隔。如果这样的人不唯一，则输出狂人中最小的号码及其通话次数，并且附加给出并列狂人的人数。

输入样例:
4
13005711862 13588625832
13505711862 13088625832
13588625832 18087925832
15005713862 13588625832
输出样例:
13588625832 3
 

 

 

 

 

 

 

 

 

 

 

 

 

•