哈希表的理解和实现

哈希表，也叫散列表，是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数，存放记录的数组叫做哈希表。

在此我不谈各种权威对哈希表的定义，仅谈自己的理解，因此难免有错误和不足之处。用个具体的例子来阐述我对哈希表的理解。例子虽然有些陈旧，但是不影响理解。现有一个班，班上30名同学，假设都是同一年出生的，那么某些同学有同样生日的可能性是多少呢？生日可以是365天中的任意一天（暂不考虑闰年），大多数班级中的学生没有相同生日的，但是学生越多，具有相同生日的可能性就越大。把学生根据生日映射到日期类似于使用生日作为哈希函数，把记录分配到表的槽中（大小是365），那么，这就相当于一个哈希表。

而事实上，一个槽只应该放一个数据，但是当哈希函数算得的值h(key1)==h(key2)时，两个不同的关键字对应的哈希地址相同，于是就产生了冲突，好的哈希函数只能避免冲突，不能完全消除冲突。好的散列函数特点是：（近似的）满足简单一致散列，即对于关键字集合U中的任何一个关键字，经散列函数映射到地址集合中任何一个地址的概率是相等的，此时可以称为均匀散列函数，也就是说使关键字经过散列函数得到一个“随机的地址”，以便使一组关键字的散列地址均匀分布在整个地址区间，减少冲突。

冲突是必然的，那么，该如何处理冲突，有以下几种常见的方法：开放寻址法，再散列法，链地址法，建立一个公共溢出区等。在自己实现哈希表的时候，我用的处理冲突的方法是链地址法，所以在此着重介绍此法。

链地址法，简单地说，就是把散列到同一个槽中的所有元素都放在一个链表中。相对于开放地址法，可能会增加存储空间。但是便于查找。实现检索的时候，先用哈希函数算得哈希地址，如果没有冲突，直接使用该处的值，如果有冲突，此处会是一个链表，在遍历链表来找到想要的值。采用这种方法时，数组的初始大小，加载因子（已装的数据与数组初始大小的比例）及哈希函数的好坏就尤为重要了。因为此种情况下会产生两个极端，一个极端就是数据很少，加载因子小，哈希表显得很“空旷”，于是哈希表就成了一个数组；另一种情况是加载因子较大，数据很多，冲突也很多，导致挂下长串的链表，这时哈希表就成了链表。这样的设计都是不合理的。当然，随着数据的增多，冲突肯定会变多，哈希表就会显得“拥挤”，这就涉及到了另一个概念，Rehash。

Rehash，简单地说就是重新创建哈希表，将原来的数据重新装入新的哈希表。一般情况下，新建的哈希表的大小会比原来的大一些，但是不会大太多，同时哈希函数也换新的，那么原来数据在表中的位置就发生了变换。Java中系统自带的哈希表是当加载因子大于0.75时就会进行Rehash。当然在自己实现的时候这个值是可以改变的。

我目前实现的哈希表的功能，可以往表中放数据(Key value)，根据Key值和哈希函数得出哈希地址。当发生冲突时，采用挂链表的方法解决，检索的时候根据Key值算出的地址得到所有在该地址中的数据。Rehash的实现还在进一步努力中。鉴于我的代码及实现的哈希函数等都是较“低端的”，在此就不贴代码献丑了。