重温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]

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

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

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

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

根据[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]アルゴリズムとデータ構造編【探索】 第6章 ハッシュ探索①(チェイン法)
[4]アルゴリズムとデータ構造編【探索】 第7章 ハッシュ探索②(オープンアドレス法)
[5]Algorithms with Python ハッシュ法 (hashing)
[6]Math Expression by Powered by MathJax
[7]C言語アルゴリズム-オープンアドレス法
[8]Java HashMap工作原理及实现


Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)