解决hash冲突之分离链接法

解决hash冲突之分离链接法

分离链接法：其做法就是将散列到同一个值的所有元素保存到一个表中。

这样讲可能比较抽象，下面看一个图就会很清楚，图如下

相应的实现可以用分离链接散列表来实现（其实就是一个linkedList数组）

至于基本的增加、删除和查询的思路都是先根据散列函数来确定遍历哪个链表。然后再到被确定的链表中执行一次查找，然后再进行相应的操作。

接下来就讲几个注意点吧

（一）什么时候需要rehash来扩大散列表的大小

讲这个的时候，先介绍一下什么是装填因子。

装填因子 = 关键字个数 / 表长

当我们使用分离链接法来处理冲突的时候，我们肯定希望装填因子最好为1，因为这个能尽可能将查找代价降到最低，所以当装填因子大于1的时候，我们会需要rehash来扩大散列表的大小。

rehash函数的具体实现如下（这是数据结构与算法书上的伪代码）：

private void rehash() {

        List<AnyType>[] oldLists = theLists;

        theLists = new List[nextPrime(2*theLists.length)];

        for(int j=0; j<theLists.length;j++)

            theLists[j] = new LinkedList<>();

        currentSize = 0;

        for(int i=0; i<oldLists.length;i++)

            for(AnyType item : oldLists[i])

                insert(item);

    }

其实大概的思路就是：将当前表的大小翻倍，但是表的大小必须是大于翻倍后的素数（下面贴出了nextPrime的具体实现）

这里表的大小必须要是素数是为了保证一个好的分布，尽可能减少冲突。

（二）散列函数的大概实现

这里先贴出书上的myhash（）方法的具体实现

private int myhash(AnyType x) {

        int hashVal = x.hashCode();

        hashVal %= theLists.length;

        if(hashVal < 0) {

            hashVal += theLists.length;

        }

        return hashVal;

    }

思路也比较简单，就是先得到插入数据的hashCode，然后对表的大小取余；如果结果是负数的话，就加上表的大小即可。

工具类:

nextPrime

//返回大于某数的下一个素数

static int NextPrime (int N) {

    if (N % 2 == 0)

        ++N;

    int i;

    for (; ; N += 2){

        for (i = 3; i*i <= N; i+=2)

            if (N % i == 0)

                goto ContOuter;

            return N;

        ContOuter:;

    }

}