温习Hash冲突问题

日期：2018-10-03T00:00:00Z

重温hash map。
着重重温关于hash冲突的解决方案。
注：本文所有的翻译并非官方翻译，都是个人的私人翻译与命名。

0. 关于hash冲突

hash表一般会根据hash值来计算数据应该放置的位置。在插入2个相同hash值的数据的时候，会重复放置在同一个位置。这种现象叫做hash冲突。

1. hash冲突解决的几种方式

（1）chain法[3]
学校中教过的一个基本方式。就是hash的每个格子都是一个单独的列表。如果有相同的hash值的话新的element会被罗列在同一个列表的下方。
（2）open address法[4]
学校中教过的一个基本方式。就是如果有相同的hash值的话，会进行再hash(rehash)计算。rehash有几种不同的方式。

2. open address法

open address法又被称为closed hashing。[7]

（1）线性查找法[4]

学校中教过的最基本的一个实现，如果hash冲突，那么就放到冲突的hash的下一个格子里面。比如如果想要最快实现就是这个方法了。不过竞技编程一般也不需要去实现它。
整理成式子的话是这样的。[5]

$$h_k(x) = (h(x) + k)\ mod\ M$$

$$h(x)$$是hash函数，M是hash表的大小，k是次数。
也就是说，如果撞到了相同的hash值，那么把k+1然后进行再计算。

（2）双重hash法(double hashing)[5]

简单的说是利用2个hash函数来生成hash值的方法。第一个函数设为$$h(x)$$，第二个函数设为$$g(x)$$的话，那么就是可以写成这个样子。

$$h_k(x) = (h(x) + k * g(x))\ mod\ M$$

按照[5]里面的说法，$$g(x)$$设置的过于复杂会影响效率，一般$$g(x)$$设置成这样子就可以了。

$$g(x) = q - (h(x)\ mod\ q)$$

根据[5]里面的实验结果([s])

数据个数	5000	10000
chain法	0.144	0.301
线性查找法	0.140	11.514
双重hash法	0.144	3.334

3.java中的hashtable的hash冲突解决

放上open jdk8 的代码[2]

//639行
for (int binCount = 0; ; ++binCount) {
    if ((e = p.next) == null) {
        p.next = newNode(hash, key, value, null);
        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab, hash);
        break;
    }
    if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k))))
        break;
    p = e;
}

这里的思路很简单，就是如果没碰撞，那就放进去。（是639行之前的代码）
如果碰撞了，就放到下一位去。就是每一个位置本身是一个list，如果碰撞了，就在这个list里面加一。
我开始还以为我读错了，看了看别人的博客[8]应该没有错。

4.后记

继续调查和阅读hash表满了之后的解决方案。

[1]JavaDoc8 HashMap
[2]Java Openjdk8 Source Code - HashMap
[3]アルゴリズムとデータ構造編【探索】　第６章　ハッシュ探索①（チェイン法）
[4]アルゴリズムとデータ構造編【探索】　第７章　ハッシュ探索②（オープンアドレス法）
[5]Algorithms with Python ハッシュ法 (hashing)
[6]Math Expression by

[7]C言語アルゴリズム-オープンアドレス法
[8]Java HashMap工作原理及实现