语境

嗨,我正在做一个学校作业,要求我们在Java中实现哈希表。没有要求将冲突保持在最低限度,但是在我完成的所有reading (some more)中,低冲突率和低速度似乎是两个最受欢迎的品质。

问题

我想要一些有关如何将哈希函数的输出映射到较小范围的指导,而不会使我的键的> 20%发生碰撞(像样)。

在我研究过的所有算法中,键都映射到无符号32位整数(或者在许多情况下是64位,甚至是128位)的整个范围。我在这里,Wikipedia或我遇到的任何与哈希相关的文章/讨论中都没有找到太多有关此内容的信息。

就实现的细节而言,我正在使用Java(学校的职责)工作,这是有问题的,因为没有可使用的未签名类型。为了解决这个问题,我一直在使用64位长的整数类型,然后使用位掩码将其映射回32位。我不是简单地截断,而是将高32位与低32位进行XOR运算,然后执行按位与运算以掩盖当我将其向下转换为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和针对输入数据量身定制的自定义变量)。

他们基本上都表现糟糕。我还没有看到
我的讲义推荐以下用于压缩哈希键的方法:

(hashed key) % P


其中P是最大素数
这是一种可接受的压缩哈希值的方法吗?我感觉并非如此,但是由于即使在压缩之前性能仍然很差,所以我也不是罪魁祸首。

最佳答案

我不知道我是否很好地理解了您的具体问题,但我会尽力帮助改进哈希性能和冲突。

基于散列的对象将根据散列值确定将键值对存储在哪个存储桶中。在每个存储桶中都有一个存储该对的结构(在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哈希码:

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中的哈希码已更改,现在当我们运行代码te结果是

100000
tiempo: 47 mls


现在,只需稍作更改,即可获得令人难以置信的更好性能。一种很常见的做法是,使用与equals方法内部相同的哈希码成员返回哈希码乘以质数(在本例中为31),以确定两个对象是否相同(在本例中仅为str)。

我希望这个小例子可以为您的问题指出解决方案。

10-07 19:35
查看更多