Java HashMap性能优化/替代方案

Question

我想创建一个大的HashMap,但put()性能不够好.有任何想法吗？

其他数据结构建议是受欢迎的,但我需要Java Map的查找功能:

map.get(key)

在我的情况下,我想创建一个包含2600万条目的地图.使用标准Java HashMap,在2-3百万次插入后,放置速率变得无法忍受.

此外,是否有人知道为密钥使用不同的哈希代码分发是否有帮助？

我的哈希码方法:

byte[] a = new byte[2];
byte[] b = new byte[3];
...

public int hashCode() {
    int hash = 503;
    hash = hash * 5381 + (a[0] + a[1]);
    hash = hash * 5381 + (b[0] + b[1] + b[2]);
    return hash;
}

我使用add的associative属性来确保相等的对象具有相同的哈希码.数组是字节,其值在0到51之间.值只在一个数组中使用一次.如果a数组包含相同的值(按任意顺序),则对象相等,而b数组则相同.所以a = {0,1} b = {45,12,33}和a = {1,0} b = {33,45,12}是相等的.

编辑,一些说明:

• 一些人批评使用哈希映射或其他数据结构来存储2600万个条目.我不明白为什么这看起来很奇怪.它看起来像是一个经典的数据结构和算法问题.我有2600万个项目,我希望能够快速将它们插入并从数据结构中查找它们:给我数据结构和算法.

• 将默认Java HashMap的初始容量设置为2600万会降低性能.

• 有些人建议使用数据库,在某些其他情况下这绝对是明智的选择.但我真的在问一个数据结构和算法的问题,一个完整的数据库会比一个好的数据结构解决方案过度而且速度慢得多(毕竟数据库只是软件,但会有通信和可能的磁盘开销).

Answer 1

正如许多人指出的那样,这种hashCode()方法应该受到指责.它只为2600万个不同的对象生成了大约20,000个代码.这是每个哈希桶平均1,300个对象=非常非常糟糕.但是,如果我将两个数组转换为基数52中的数字,我保证会为每个对象获取一个唯一的哈希码:

public int hashCode() {       
    // assume that both a and b are sorted       
    return a[0] + powerOf52(a[1], 1) + powerOf52(b[0], 2) + powerOf52(b[1], 3) + powerOf52(b[2], 4);
}

public static int powerOf52(byte b, int power) {
    int result = b;
    for (int i = 0; i < power; i++) {
        result *= 52;
    }
    return result;
}

对数组进行排序以确保此方法满足hashCode()相等对象具有相同哈希码的约定.使用旧方法,每秒平均投放次数超过100,000次投注,100,000到2,000,000是:

168350.17
109409.195
81344.91
64319.023
53780.79
45931.258
39680.29
34972.676
31354.514
28343.062
25562.371
23850.695
22299.22
20998.006
19797.799
18702.951
17702.434
16832.182
16084.52
15353.083

使用新方法给出:

337837.84
337268.12
337078.66
336983.97
313873.2
317460.3
317748.5
320000.0
309704.06
310752.03
312944.5
265780.75
275540.5
264350.44
273522.97
270910.94
279008.7
276285.5
283455.16
289603.25

好多了.旧方法很快就停止了,而新方法保持了良好的吞吐量.

Answer 2

有一件事我在您的通知hashCode()方法是,在数组中元素的顺序a[]并b[]没有关系.因此(a[]={1,2,3}, b[]={99,100})将散列到相同的值(a[]={3,1,2}, b[]={100,99}).其实所有的按键k1和k2地方sum(k1.a)==sum(k2.a)以及sum(k1.b)=sum(k2.b)会造成冲突.我建议为数组的每个位置分配一个权重:

hash = hash * 5381 + (c0*a[0] + c1*a[1]);
hash = hash * 5381 + (c0*b[0] + c1*b[1] + c3*b[2]);

其中,c0,c1和c3是不同的常数(你可以使用不同的常量,b如果需要的话).这应该可以使事情变得更加平坦.

Answer 3

详细说明Pascal:你了解HashMap的工作原理吗？您的哈希表中有一些插槽.找到每个密钥的哈希值,然后映射到表中的条目.如果两个哈希值映射到同一条目 - "哈希冲突" - HashMap构建链接列表.

散列冲突可以破坏哈希映射的性能.在极端情况下,如果您的所有密钥都具有相同的哈希码,或者如果它们具有不同的哈希码但它们都映射到同一个槽,那么您的哈希映射将变为链接列表.

因此,如果您看到性能问题,我要检查的第一件事是:我是否获得了随机分布的哈希码？如果没有,您需要更好的哈希函数.那么,在这种情况下"更好"可能意味着"更好地为我的特定数据集".比如,假设您正在使用字符串,并且您将字符串的长度用于哈希值.(不是Java的String.hashCode如何工作,但我只是编写一个简单的例子.)如果你的字符串有很大的变化长度,从1到10,000,并且相当均匀地分布在这个范围内,这可能是一个非常好的哈希函数.但是如果你的字符串都是1或2个字符,那么这将是一个非常糟糕的哈希函数.

编辑:我应该添加:每次添加新条目时,HashMap都会检查这是否重复.当存在哈希冲突时,它必须将传入密钥与映射到该槽的每个密钥进行比较.因此,在最糟糕的情况下,所有内容都散列到一个插槽,第二个键与第一个键进行比较,第三个键与#1和#2进行比较,第四个键与#1,#2和#3进行比较当你获得关键#100万时,你已经完成了超过一万亿的比较.

@Oscar:嗯,我看不出那是"不是真的".这更像是"让我澄清".但是,是的,如果您使用与现有条目相同的密钥创建新条目,则会覆盖第一个条目.当我谈到在最后一段中查找重复时,这就是我的意思:每当一个键哈希到同一个槽时,HashMap必须检查它是否是现有密钥的副本,或者它们是否只是在同一个槽中的巧合哈希函数.我不知道那是HashMap的"重点":我会说"整点"是你可以快速按键检索元素.

但无论如何,这并不影响我试图制作的"整点":当你有两个键 - 是的,不同的键,而不是同一个键再次显示 - 映射到表中的同一个插槽,HashMap构建一个链表.然后,因为它必须检查每个新密钥以查看它是否实际上是现有密钥的副本,所以每次尝试添加映射到同一个槽的新条目都必须追踪链接列表,检查每个现有条目以查看是否是先前看到的密钥的副本,或者它是否是新密钥.

在原帖后很久更新

在发布6年后,我刚刚对这个答案进行了投票,这让我重新阅读了这个问题.

问题中给出的哈希函数对于2600万个条目来说不是一个好的哈希.

它将[0] + a [1]和b [0] + b [1] + b [2]加在一起.他说每个字节的值范围从0到51,因此只给出(51*2 + 1)*(51*3 + 1)= 15,862个可能的哈希值.有2600万个条目,这意味着每个哈希值平均大约有1639个条目.这是很多很多的冲突,需要通过链表进行大量的连续搜索.

OP表示阵列a和阵列b中的不同顺序应该被认为是相等的,即[[1,2],[3,4,5]].等于([[2,1],[5,3,4] ]),为了履行合同,他们必须有相同的哈希码.好的.尽管如此,仍有超过15,000个可能的值.他的第二个提议哈希函数要好得多,给出了更广泛的范围.

虽然正如其他人所评论的那样,哈希函数似乎不适合更改其他数据.在创建对象时"标准化"对象或使对象的副本使用散列函数更有意义.此外,每次通过函数使用循环来计算常量是低效的.由于这里只有四个值,我会写

return a[0]+a[1]*52+b[0]*52*52+b[1]*52*52*52+b[2]*52*52*52*52;

这会导致编译器在编译时执行一次计算; 或者在类中定义4个静态常量.

此外,散列函数的初稿有几个计算,无法添加到输出范围.注意,在考虑类中的值之前,他首先设置hash = 503而不是乘以5381.所以...实际上他为每个值添加了503*5381.这取得了什么成果？为每个哈希值添加一个常量只会烧掉cpu周期而不会完成任何有用的操作.这里的教训:增加哈希函数的复杂性不是目标.目标是获得广泛的不同价值,而不仅仅是为了复杂性而增加复杂性.

Answer 4

我的第一个想法是确保你正确地初始化你的HashMap.从JavaDocs for HashMap:

HashMap的一个实例有两个影响其性能的参数:初始容量和负载因子.容量是哈希表中的桶数,初始容量只是创建哈希表时的容量.加载因子是在自动增加容量之前允许哈希表获取的完整程度的度量.当哈希表中的条目数超过加载因子和当前容量的乘积时,哈希表将被重新哈希(即,重建内部数据结构),以便哈希表具有大约两倍的桶数.

因此,如果您从一个太小的HashMap开始,那么每次需要调整大小时,所有哈希都会被重新计算...这可能是您在达到2-3百万个插入点时所感受到的.

Answer 5

我建议采取三管齐下的方法:

1. 运行具有更多内存的Java:java -Xmx256M例如以256兆字节运行.如果需要,可以使用更多,并且有大量的RAM.

2. 按照另一张海报的建议缓存计算的哈希值,因此每个对象只计算一次哈希值.

3. 使用更好的散列算法.您发布的那个将返回相同的散列,其中a = {0,1},而a = {1,0},其他所有相等.

利用Java为您提供的免费服务.

public int hashCode() {
    return 31 * Arrays.hashCode(a) + Arrays.hashCode(b);
}

我很确定这比现有的hashCode方法碰撞的可能性要小得多,尽管它取决于数据的确切性质.

Answer 6

进入"开/关主题"的灰色区域,但有必要消除有关Oscar Reyes建议更多哈希冲突是一件好事的混淆,因为它减少了HashMap中的元素数量.我可能会误解奥斯卡所说的话,但我似乎并不是唯一一个:kdgregory,delfuego,Nash0,我似乎都有同样的(错误的)理解.

如果我理解Oscar对同一个具有相同哈希码的类的说法,他建议只有一个具有给定哈希码的类的实例将插入到HashMap中.例如,如果我有一个哈希码为1的SomeClass实例和一个哈希码为1的SomeClass的第二个实例,则只插入一个SomeClass实例.

http://pastebin.com/f20af40b9上的Java pastebin示例似乎表明上面正确总结了Oscar提出的建议.

无论有任何理解或误解,如果相同类的不同实例具有相同的哈希码,则不会仅将其插入HashMap中 - 直到确定键是否相等为止.哈希码契约要求相等的对象具有相同的哈希码; 但是,它并不要求不相等的对象具有不同的哈希码(尽管出于其他原因这可能是合乎需要的)[1].

下面是pastebin.com/f20af40b9示例(Oscar至少引用两次),但略微修改以使用JUnit断言而不是printlines.此示例用于支持相同哈希码导致冲突的提议,并且当类相同时,仅创建一个条目(例如,在此特定情况下仅一个字符串):

@Test
public void shouldOverwriteWhenEqualAndHashcodeSame() {
    String s = new String("ese");
    String ese = new String("ese");
    // same hash right?
    assertEquals(s.hashCode(), ese.hashCode());
    // same class
    assertEquals(s.getClass(), ese.getClass());
    // AND equal
    assertTrue(s.equals(ese));

    Map map = new HashMap();
    map.put(s, 1);
    map.put(ese, 2);
    SomeClass some = new SomeClass();
    // still  same hash right?
    assertEquals(s.hashCode(), ese.hashCode());
    assertEquals(s.hashCode(), some.hashCode());

    map.put(some, 3);
    // what would we get?
    assertEquals(2, map.size());

    assertEquals(2, map.get("ese"));
    assertEquals(3, map.get(some));

    assertTrue(s.equals(ese) && s.equals("ese"));
}

class SomeClass {
    public int hashCode() {
        return 100727;
    }
}

但是,哈希码并不是完整的故事.什么引擎收录例子忽略的事实是,这两个s和ese是相等的:它们都是字符串"ESE".因此,在插入或使用得到映射的内容s或ese或"ese"作为键都是等效的,因为s.equals(ese) && s.equals("ese").

第二个测试表明,错误地得出结论:在同一个类上使用相同的哈希码是键 - >值s -> 1被在test 1中调用ese -> 2时覆盖的原因map.put(ese, 2).在试验二,s并且ese仍然有相同的哈希码(通过验证assertEquals(s.hashCode(), ese.hashCode());),他们是同一类.但是,s并且ese是MyString此测试中的实例,而不是Java String实例 - 与此测试相关的唯一差异是等于:String s equals String ese在上面的测试1中,而MyStrings s does not equal MyString ese在测试2中:

@Test
public void shouldInsertWhenNotEqualAndHashcodeSame() {
    MyString s = new MyString("ese");
    MyString ese = new MyString("ese");
    // same hash right?
    assertEquals(s.hashCode(), ese.hashCode());
    // same class
    assertEquals(s.getClass(), ese.getClass());
    // BUT not equal
    assertFalse(s.equals(ese));

    Map map = new HashMap();
    map.put(s, 1);
    map.put(ese, 2);
    SomeClass some = new SomeClass();
    // still  same hash right?
    assertEquals(s.hashCode(), ese.hashCode());
    assertEquals(s.hashCode(), some.hashCode());

    map.put(some, 3);
    // what would we get?
    assertEquals(3, map.size());

    assertEquals(1, map.get(s));
    assertEquals(2, map.get(ese));
    assertEquals(3, map.get(some));
}

/**
 * NOTE: equals is not overridden so the default implementation is used
 * which means objects are only equal if they're the same instance, whereas
 * the actual Java String class compares the value of its contents.
 */
class MyString {
    String i;

    MyString(String i) {
        this.i = i;
    }

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

根据后来的评论,奥斯卡似乎扭转了他早先所说的话,并承认平等的重要性.然而,似乎仍然认为平等是重要的,而不是"同一类",不清楚(强调我的):

"不是真的.只有当哈希值相同但密钥不同时才创建列表.例如,如果String给出哈希码2345并且Integer给出相同的哈希码2345,则整数被插入到列表中,因为String. equals(Integer)为false.但是如果你有相同的类(或者至少.equals返回true)则使用相同的条目.例如new String("one")和`new String("one")用作密钥,将使用相同的条目.实际上这是HashMap的第一个要点!亲眼看看:pastebin.com/f20af40b9 - Oscar Reyes"

与之前的注释明确地解决了相同类和相同哈希码的重要性,没有提到equals:

"@delfuego:自己看看:pastebin.com/f20af40b9所以,在这个问题中,正在使用相同的类(等一下,正在使用同一个类吗？)这意味着当使用相同的哈希相同的条目时使用,并没有条目的"列表". - 奥斯卡雷耶斯"

要么

"实际上,这会增加性能.更多的冲突eq更少的哈希表eq中的条目.更少的工作要做.不是哈希(看起来很好),也不是哈希表(它工作得很好)我敢打赌它是在对象上表演性能下降的创作. - Oscar Reyes"

要么

"@kdgregory:是的,但是只有当碰撞发生在不同的类中时,对于同一个类(在这种情况下)才会使用相同的条目. - Oscar Reyes"

我可能会误解奥斯卡实际上想说的话.然而,他最初的评论引起了足够的混淆,通过一些明确的测试清除所有内容似乎是谨慎的,因此没有挥之不去的疑虑.

[1] - 来自Effective Java,第二版由Joshua Bloch撰写:

• 每当在执行应用程序期间多次在同一对象上调用它时,hashCode方法必须始终返回相同的整数,前提是不修改在对象的相等比较中使用的信息.从应用程序的一次执行到同一应用程序的另一次执行,该整数不需要保持一致.

• 如果两个对象根据等于s(Obj ect)方法相等,则在两个对象中的每一个上调用hashCode方法必须产生相同的整数结果.

• 如果两个对象根据相等的s(Object)方法不相等,则不需要在两个对象中的每一个上调用hashCode方法必须产生不同的整数结果.但是,程序员应该知道为不等对象生成不同的整数结果可能会提高哈希表的性能.

Answer 7

如果发布的hashCode中的数组是字节,那么最终可能会出现大量重复数据.

a [0] + a [1]将始终介于0和512之间.添加b将始终生成介于0和768之间的数字.将这些数字相乘并获得400,000个唯一组合的上限,假设您的数据是完美分布的在每个字节的每个可能值之间.如果您的数据完全正常,则此方法的唯一输出可能要少得多.