解决hash冲突之分离链接法

  • A+
所属分类:qq可爱名字

解决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:;
    }
}