哈希表

为什么要有哈希表:

是为了根据数据的部分内容(关键字),直接计算出存放完整数据的没存地址,试想一下，如果从链表中根据关键字查找一个元素，那么就需要遍历才能得到这个元素的内存地址，如果链表长度很大，查找就需要更多的时间.而哈希表可以通过某种算法(哈希算法)来根据关键字计算出value存放的完整地址,不需要遍历,所以效率很高,注意一点就是我们的哈希函数有很多种,唯一的目的就是让产生冲突的可能性最低,采用什么样的哈希函数取决于建表的关键字集合的情况,例如关键字的范围和数据类型等等;

哈希冲突

原因就是不同的关键字通过我们的哈希算法时可能产生相同的哈希地址,例如我们的哈希函数是

H(hey)= key mod 11;那么当我们的key为1和23时会产生同一个哈希地址1,那么这种情况我们该如何解决呢?通常有两种方法:

• 开放地址法:比如如果两个关键字通过哈希算法产生的哈希地址一样,那么我们就为产生冲突的地址H(key)求得另一个地址序列,可能再求的地址还有冲突,所以可能需要再求几次甚至更多,直到求得的地址中没有冲突.

• 链地址法:将所有哈希地址相同的记录搜链接在同一个链表中

哈希表的查找

在哈希表上进行查找的过程和建表的过程基本一致。假设给定的值为key，根据建表时设定的哈希函数H，计算出哈希地址H(key),若表中该地址对应的空间未被占用。则查找失败。否则将该地址中的节点与给定值k比较，若相等则查找成功，否则按建表时设定的处理冲突方法找下一个地址，如此反复下去，直到找到某个地址空间未被占用（查找失败）或者关键字比较相等（查找成功）为止。

一个哈希表的实现:

1. 哈希表节点数据结构的定义:根据处理冲突的方式不同数据结构不同,如果采取的是用链表连接起来则需要定义指向链表下一个节点的结构体指针,如果选择的是开放寻址法再生成哈希地址则不需要.

2. 哈希表的初始化和释放:分配内存空间,通常用malloc分配堆内存,最后用free释放内存.

3. 哈希散列函数:将数据的关键字转化为一个哈希地址

4. 哈希表的插入和修改:如果key在哈希表中已经存在，那么就是修改value，否则就是插入一个节点.

5. 哈希表中查找数据:现根据要查找数据的key生成哈希地址,再到哈希表查找该地址对应的value,根据解决冲突的方法不同这个地方查找的方法也有区别,如果冲突是用链表链接起来的可能在哈希表同一个地址下链表的第几个节点的数据是我们要找的数据.