java - 将散列值映射到一个范围，冲突最小

Question

上下文

你好，我正在为学校做作业，要求我们用 Java 实现哈希表。没有要求将碰撞保持在最低限度，但低碰撞率和速度似乎是所有 reading 中最受欢迎的两个品质。 (some more)我已经完成了。

问题

我想要一些关于如何将散列函数的输出映射到更小范围的指导，而不会让我的 20% 以上的键发生冲突(哎呀)。

在我探索过的所有算法中， key 都映射到无符号 32 位整数的整个范围(或者在许多情况下，64 位，甚至 128 位)。我在这里、维基百科或我遇到的任何与哈希相关的文章/讨论中都没有找到太多相关信息。

就我的实现细节而言，我正在使用 Java(我学校的要求)，这是有问题的，因为没有可使用的无符号类型。为了解决这个问题，我一直在使用 64 位长整数类型，然后使用位掩码映射回 32 位。我不是简单地截断，而是将顶部 32 位与底部 32 位进行异或运算，然后执行按位 AND 以屏蔽掉任何高位，当我将其转换为 32 位整数时可能会产生负值。毕竟，一个单独的函数会压缩生成的哈希值以适应哈希表内部数组的边界。

它最终看起来像:

int hash( String key ) {

    long h;

    for( int i = 0; i < key.length(); i++ )
        //do some stuff with each character in the key

        h = h ^ ( h << 32 );

    return h & 2147483647;
}

内部循环取决于散列函数(我已经实现了一些:多项式散列、FNV1、SuperFastHash 和针对输入数据定制的自定义函数)。

他们基本上都表现得很糟糕。我还没有看到 <20% 的按键发生碰撞。甚至在我将哈希值压缩到数组索引之前，我的哈希函数都不会让我少感谢 10k 碰撞。我的输入是两个文本文件，每个约 220,000 行。一种是英文单词，另一种是长度不一的随机字符串。

我的讲义推荐以下内容，用于压缩散列键:

(hashed key) % P

其中 P 是最大素数 < 内部数组的大小。

这是压缩哈希值的公认方法吗？我感觉它不是，但由于即使在压缩之前性能也很差，我感觉它也不是罪魁祸首。

Answer 1

我不知道我是否理解你的具体问题，但我会尽力在哈希性能和冲突方面提供帮助。

基于散列的对象将根据散列值确定将键值对存储在哪个桶中。在每个桶中都有一个结构(在 HashMap 的情况下是一个 LinkedList)，其中存储了对。

如果哈希值通常相同，则桶通常也相同，因此性能会下降很多，让我们看一个例子:

考虑这个类

package hashTest;

import java.util.Hashtable;

public class HashTest {

    public static void main (String[] args) {

        Hashtable<MyKey, String> hm = new Hashtable<>();

        long ini = System.currentTimeMillis();

        for (int i=0; i<100000; i++) {
            MyKey a = new HashTest().new MyKey(String.valueOf(i));

            hm.put(a, String.valueOf(i));
        }

        System.out.println(hm.size());

        long fin = System.currentTimeMillis();
        System.out.println("tiempo: " + (fin-ini) + " mls");
    }

    private class MyKey {

        private String str;

        public MyKey(String i) {
            str = i;
        }

        public String getStr() {
            return str;
        }

        @Override
        public int hashCode() {
            return 0;
        }

        @Override
        public boolean equals(Object o) {
            if (o instanceof MyKey) {
                MyKey aux = (MyKey) o;
                if (this.str.equals(aux.getStr())) {
                    return true;
                }
            }
            return false;
        }
    }
}

请注意，MyKey 类中的 hashCode 始终返回“0”作为哈希值。哈希码定义( http://docs.oracle.com/javase/7/docs/api/java/lang/Object.html#hashCode() )没问题。如果我们运行那个程序，这就是结果

100000 
tiempo: 62866 mls

是一个很差的性能，现在我们要改变MyKey hashcode代码:

package hashTest;

import java.util.Hashtable;

public class HashTest {

    public static void main (String[] args) {

        Hashtable<MyKey, String> hm = new Hashtable<>();

        long ini = System.currentTimeMillis();

        for (int i=0; i<100000; i++) {
            MyKey a = new HashTest().new MyKey(String.valueOf(i));

            hm.put(a, String.valueOf(i));
        }

        System.out.println(hm.size());

        long fin = System.currentTimeMillis();
        System.out.println("tiempo: " + (fin-ini) + " mls");
    }

    private class MyKey {

        private String str;

        public MyKey(String i) {
            str = i;
        }

        public String getStr() {
            return str;
        }

        @Override
        public int hashCode() {
            return str.hashCode() * 31;
        }

        @Override
        public boolean equals(Object o) {
            if (o instanceof MyKey) {
                MyKey aux = (MyKey) o;
                if (this.str.equals(aux.getStr())) {
                    return true;
                }
            }
            return false;
        }
    }
}

注意只有MyKey中的hashcode变了，现在我们运行代码的结果是

100000
tiempo: 47 mls

现在有了一个微小的变化，性能有了令人难以置信的改善。一种非常常见的做法是返回哈希码乘以质数(在本例中为 31)，使用您在 equals 方法中使用的相同哈希码成员以确定两个对象是否相同(在本例中仅为 str)。

我希望这个小例子能为您指出解决问题的方法。