如何解决散列表的散列值的冲突问题

来源：不详责任编辑：栏目编辑发表时间:2013-07-01 22:15　点击:次

1、散列表要解决的一个问题就是散列值的冲突问题，通常是两种方法：链表法和开放地址法。链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位；开放地址法是通过一个探测算法，当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。java.util.HashMap采用的链表法的方式，链表是单向链表，因此在删除过程中要自己维持prev节点，我想不采用双向链表是从节省空间考虑。一个典型的查找过程：

for　(Entry<K,V>　e　=　table[indexFor(hash,　table.length)];
　　　　　　　　　　　　　e　!=　null;
　　　　　　　　　　　　　e　=　e.next)　{
　　　　　　　　　　　　Object　k;
　　　　　　　　　　　　if　(e.hash　==　hash　&&
　　　　　　　　　　　　　　　　((k　=　e.key)　==　key　||　(key　!=　null　&&　key.equals(k))))
　　　　　　　　　　　　　　　　return　e;
　}

HashMap采用链表法而不是开放地址法，猜想可能的原因是从实用角度出发，对空间和时间效率做出的折中选择。采用开放地址法，无论是线性探测或者二次探测都可能造成群集现象，而双重散列会要求散列表的装填程度比较低的情况下会有比较好的查找效率，容易造成空间的浪费。

2、什么是负载因子？负载因子a定义为

a=散列表的实际元素数目（n）/ 散列表的容量（m）

负载因子衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均次数是（1+a）次，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。

回到HashMap的实现，HashMap中的loadFactor其实定义的就是该map对象允许的最大的负载因子，如果超过这个系数将重新resize.这个是通过threshold字段来判断，看threshold的计算：

threshold　=　(int)(capacity　*　loadFactor);

结合上面的负载因子的定义公式可知，threshold就是在此loadFactor和capacity对应下允许的最大元素数目，超过这个数目就重新resize，以降低实际的负载因子。默认的的负载因子0.75是对空间和时间效率的一个平衡选择。注意到的一点是resize的规模是现有 capacity的两倍：

if　(size++　>=　threshold)
　　　　　　　　　　　　resize(2　*　table.length);

3、可能你也注意到了，java.util.HashMap对key的hash值多做了一步处理，而不是直接使用hashCode：

static　int　hash(int　h)　{
　　　　　　　　h　^=　(h　>>>　20)　^　(h　>>>　12);
　　　　　　　　return　h　^　(h　>>>　7)　^　(h　>>>　4);
　　}

这个处理的原因在于HashMap的容量总是采用2的p次幂，而取index（槽位）的方法是

static　int　indexFor(int　h,　int　length)　{
　　　　　　　　return　h　&　(length-1);
　}

这一运算等价于对length取模，也就是

h % 2^p

返回的将是h的p个最低位组成的数字，我们假设hash输入是符合简单一致散列，然而这一假设并不能推论出hash的p个最低位也会符合简单一致散列，也许h的这p个最低位相同的几率很大，那么冲突的几率就非常大了。优秀的散列函数应该需要考虑所有的位。

因此为了防止这些“坏”的散列函数造成效率的降低，HashMap预先对hash值做了处理以考虑到所有的位，根据注释也可以知道。这个处理我看不懂，留待高人解释，也许来自于某本算法书也不一定。

4、我们知道java.util.HashMap不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略（速错），这一策略在源码中的实现是通过 modCount域，modCount顾名思义就是修改次数，对HashMap内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount，

　HashIterator()　{
　　　　　　　　　　　　expectedModCount　=　modCount;
　　　　　　　　　　　　if　(size　>　0)　{　//　advance　to　first　entry
　　　　　　　　　　　　　　　　Entry[]　t　=　table;
　　　　　　　　　　　　　　　　while　(index　<　t.length　&&　(next　=　t[index++])　==　null)
　　　　　　　　　　　　　　　　　　　　;
　　　　　　　　　　　　}
　　　　　　　　}

在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了map