Java HashMap性能优化/替代

equi 发布于 2019-11-10 hashmap 最后更新 2019-11-10 12:09 204 浏览

我想创建一个大型的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;
}
我正在使用addition的associative属性来确保相等的对象具有相同的哈希码。这些数组是字节值在0-51范围内的值。数值仅在任一数组中使用一次。如果a数组包含相同的值(以任意顺序)并且b数组也是相同的,则这些对象是相等的。所以a = {0,1} b = {45,12,33}和a = {1,0} b = {33,45,12}是相等的。 编辑,一些笔记:
  • 少数人批评使用哈希映射或其他数据结构来存储2600万个条目。我看不出为什么这看起来很奇怪。它看起来像我经典的数据结构和算法问题。我有2600万项,我希望能够快速插入并从数据结构中查找它们:给我数据结构和算法。
  • 将默认Java HashMap的初始容量设置为2600万降低了性能。
  • 有些人建议使用数据库,在其他一些情况下,这绝对是明智的选择。但是我真的在问一个数据结构和算法的问题,一个完整的数据库会比一个好的数据结构解决方案矫枉过正并且慢得多(毕竟数据库只是软件,但会有通信和可能的磁盘开销)。
已邀请:

hiure

赞同来自:

SQLite允许您在内存中使用它。

dquis

赞同来自:

首先,您应该检查您是否正确使用Map,键的好hashCode()方法,Map的初始容量,正确的Map实现等等许多其他答案描述。 然后我建议使用分析器来查看实际发生的情况以及执行时间的花费。例如,hashCode()方法执行了数十亿次? 如果这没有帮助,那么如何使用EHCachememcached?是的,它们是用于缓存的产品,但您可以对它们进行配置,以便它们具有足够的容量,并且永远不会从缓存存储中逐出任何值。 另一种选择是一些比完整SQL RDBMS更轻的数据库引擎。也许像Berkeley DB这样的东西。 请注意,我个人没有这些产品性能的经验,但它们值得一试。

nodio

赞同来自:

如果键具有任何图案,则可以将地图拆分为较小的地图并具有索引图。 例: 键:1,2,3,.... n 28张地图,每张100万张。 索引图: 1-1,000,000 - > Map1 1,000,000-2,000,000 - > Map2 因此,您将进行两次查找,但密钥集将为1,000,000与28,000,000。您也可以使用刺痛模式轻松完成此操作。 如果密钥是完全随机的,那么这将不起作用

paut

赞同来自:

我在hashCode()方法中注意到的一件事是数组a[]b[]中元素的顺序无关紧要。因此,(a[]={1,2,3}, b[]={99,100})将散列为与(a[]={3,1,2}, b[]={100,99})相同的值。实际上所有键k1k2,其中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]);
其中,c0c1c3是不同的常量(如果需要,您可以为b使用不同的常量)。这应该甚至更多的东西。

cet

赞同来自:

我用一个列表与一个hashmap进行了一次小测试,有趣的是迭代遍历列表,发现对象花费的时间与毫秒相同,就像使用hashmaps获取函数一样...只是一个fyi。哦,使用大小的哈希映射时,内存是一个大问题。

lest

赞同来自:

正如所指出的,您的哈希码实现有太多的冲突,修复它应该会产生不错的性能。此外,缓存hashCodes和有效实现equals将有所帮助。 如果您需要进一步优化: 根据您的描述,只有(52 51/2)(52 51 50/6)= 29304600个不同的密钥(其中26000000,即约90%将存在)。因此,您可以设计没有任何冲突的哈希函数,并使用简单的数组而不是哈希映射来保存数据,从而减少内存消耗并提高查找速度:

T[] array = new T[Key.maxHashCode];
void put(Key k, T value) {
    array[k.hashCode()] = value;
T get(Key k) {
    return array[k.hashCode()];
}
(一般来说,设计一个高效,无碰撞的散列函数是不可能很好地聚类,这就是为什么HashMap会容忍碰撞,这会产生一些开销) 假设ab已排序,您可以使用以下哈希函数:
public int hashCode() {
    assert a[0] < a[1]; 
    int ahash = a[1] * a[1] / 2 
              + a[0];
assert b[0] < b[1] && b[1] < b[2];
int bhash = b[2] * b[2] * b[2] / 6
              + b[1] * b[1] / 2
              + b[0];
    return bhash * 52 * 52 / 2 + ahash;
}
static final int maxHashCode = 52 * 52 / 2 * 52 * 52 * 52 / 6;  
我认为这是无碰撞的。证明这是留给数学倾向的读者的练习。

nfugit

赞同来自:

HashMap具有初始容量,HashMap的性能非常依赖于生成底层对象的hashCode。 尝试调整两者。

lillo

赞同来自:

In my case I want to create a map with 26 million entries. Using the standard Java HashMap the put rate becomes unbearably slow after 2-3 million insertions.
从我的实验(2009年的学生项目):
  • 我为100,000个节点建立了一个红色黑树,从1到100.000。花了785.68秒(13分钟)。而且我没有为100万个节点构建RBTree(就像使用HashMap的结果一样)。
  • 使用“Prime Tree”,我的算法数据结构。我可以在21.29秒内为一千万个节点建立树/地图(RAM:1.97Gb)。搜索键值成本为O(1)。
注意:“Prime Tree”在“连续键”上的效果最好,从1到10百万。要使用像HashMap这样的键,我们需要调整一些未成年人。
那么,什么是#PrimeTree?简而言之,它是一个像二进制树一样的树数据结构,分支数是素数(而不是“2” - 二进制数)。

fearum

赞同来自:

我的第一个想法是确保你正确地初始化你的HashMap。来自JavaDocs for HashMap

An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.
因此,如果您从一个太小的HashMap开始,那么每次需要调整大小时,所有的哈希都会被重新计算......这可能是您在达到2-3百万个插入点时所感受到的。

benim

赞同来自:

您可以尝试将计算的哈希代码缓存到密钥对象。 像这样的东西:

public int hashCode() {
  if(this.hashCode == null) {
     this.hashCode = computeHashCode();
  }
  return this.hashCode;
}
private int computeHashCode() {
   int hash = 503;
   hash = hash * 5381 + (a[0] + a[1]);
   hash = hash * 5381 + (b[0] + b[1] + b[2]);
   return hash;
}
当然,在第一次计算hashCode之后,您必须小心不要更改密钥的内容。 编辑:当您将每个键只添加一次到地图时,似乎缓存的代码值是不值得的。在其他一些情况下,这可能很有用。

uid

赞同来自:

Effective Java: Programming Language Guide (Java Series)中 第3章,你可以找到计算hashCode()时要遵循的好规则。 特别: 如果该字段是数组,则将其视为每个元素都是单独的字段。 也就是说,通过应用计算每个重要元素的哈希码 递归这些规则,并按步骤2.b组合这些值。如果每一个 数组字段中的元素很重要,可以使用其中之一 版本1.5中添加了Arrays.hashCode方法。

nnam

赞同来自:

正如许多人指出的那样,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
好多了。旧方法很快就停止了,而新方法保持了良好的吞吐量。

wrerum

赞同来自:

如果您提到的两个字节数组是您的整个键,则值在0-51范围内,唯一且a和b数组中的顺序无关紧要,我的数学告诉我,只有大约2600万个可能的排列和您可能正在尝试使用所有可能键的值填充地图。 在这种情况下,如果使用数组而不是HashMap并将其从0到25989599索引,那么从数据存储中填充和检索值当然会快得多。

oad

赞同来自:

使用的流行散列方法对于大型集合并不是非常好,并且如上所述,使用的散列特别糟糕。更好的是使用具有高混合和覆盖的散列算法,例如BuzHash(在http://www.java2s.com/Code/Java/Development-Class/AveryefficientjavahashalgorithmbasedontheBuzHashalgoritm.htm处的示例实现)

riure

赞同来自:

在开头分配一张大地图。如果您知道它将有2600万个条目并且您有内存,请执行new HashMap(30000000)。 你确定,你有足够的内存用于2600万个条目,拥有2600万个密钥和值吗?这对我来说听起来像是很多记忆。你确定垃圾收集在200到300万的标记下还能正常吗?我可以想象这是一个瓶颈。

qenim

赞同来自:

您可以尝试两件事:

  • 让您的hashCode方法返回更简单,更有效的内容,例如连续的int
  • 将地图初始化为:
    Map map = new HashMap( 30000000, .95f );
    
这两个动作将大大减少结构重复的数量,并且我认为很容易测试。 如果这不起作用,请考虑使用不同的存储,例如RDBMS。 编辑 奇怪的是,设置初始容量会降低您的性能。 请参阅javadocs
If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.
我做了一个微观标记(这不是任何权威,但至少证明了这一点)
$cat Huge*java
import java.util.*;
public class Huge {
    public static void main( String [] args ) {
        Map map = new HashMap( 30000000 , 0.95f );
        for( int i = 0 ; i < 26000000 ; i ++ ) { 
            map.put( i, i );
        }
    }
}
import java.util.*;
public class Huge2 {
    public static void main( String [] args ) {
        Map map = new HashMap();
        for( int i = 0 ; i < 26000000 ; i ++ ) { 
            map.put( i, i );
        }
    }
}
$time java -Xms2g -Xmx2g Huge
real    0m16.207s
user    0m14.761s
sys 0m1.377s
$time java -Xms2g -Xmx2g Huge2
real    0m21.781s
user    0m20.045s
sys 0m1.656s
$
因此,由于重新使用,初始容量从21s降至16s。这使我们将您的hashCode方法作为“机会区域”;) 编辑

不是HashMap 根据你上一版。 我认为你应该真正剖析你的应用程序,看看内存/ cpu的消耗位置。 我创建了一个实现相同hashCode的类 该哈希代码会产生数百万次冲突,然后HashMap中的条目会大大减少。 我在之前的考试中从21s,16s传到了10s和8s。原因是hashCode引发了大量的冲突,你没有存储你认为的26M对象,但是数量要少得多(我会说约20k)所以: 问题不是HASHMAP是代码中的其他地方。 现在是时候找到一个分析器并找出它的位置。我认为这是在项目的创建或可能你正在写入磁盘或从网络接收数据。 这是我的课程实施。 注意我没有像你那样使用0-51范围,但我的值没有使用-126到127,并且重复承认,那是因为我在更新你的问题之前做了这个测试 唯一的区别是您的班级将有更多的碰撞,因此存储在地图中的项目更少。
import java.util.*;
public class Item {
private static byte w = Byte.MIN_VALUE;
    private static byte x = Byte.MIN_VALUE;
    private static byte y = Byte.MIN_VALUE;
    private static byte z = Byte.MIN_VALUE;
// Just to avoid typing :) 
    private static final byte M = Byte.MAX_VALUE;
    private static final byte m = Byte.MIN_VALUE;
private byte [] a = new byte[2];
    private byte [] b = new byte[3];
public Item () {
        // make a different value for the bytes
        increment();
        a[0] = z;        a[1] = y;    
        b[0] = x;        b[1] = w;   b[2] = z;
    }
private static void increment() {
        z++;
        if( z == M ) {
            z = m;
            y++;
        }
        if( y == M ) {
            y = m;
            x++;
        }
        if( x == M ) {
            x = m;
            w++;
        }
    }
    public String toString() {
        return "" + this.hashCode();
    }
public int hashCode() {
        int hash = 503;
        hash = hash * 5381 + (a[0] + a[1]);
        hash = hash * 5381 + (b[0] + b[1] + b[2]);
        return hash;
    }
    // I don't realy care about this right now. 
    public boolean equals( Object other ) {
        return this.hashCode() == other.hashCode();
    }
// print how many collisions do we have in 26M items.
    public static void main( String [] args ) {
        Set set = new HashSet();
        int collisions = 0;
        for ( int i = 0 ; i < 26000000 ; i++ ) {
            if( ! set.add( new Item() ) ) {
                collisions++;
            }
        }
        System.out.println( collisions );
    }
}
使用此类具有以前程序的Key
 map.put( new Item() , i );
给我:
real     0m11.188s
user     0m10.784s
sys 0m0.261s
real     0m9.348s
user     0m9.071s
sys  0m0.161s

oillo

赞同来自:

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

  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方法碰撞的可能性要小得多,尽管它取决于数据的确切性质。

eipsum

赞同来自:

详细说明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周期而不会完成任何有用的操作。这里的教训:增加哈希函数的复杂性不是目标。目标是获得广泛的不同价值,而不仅仅是为了复杂性而增加复杂性。

hquae

赞同来自:

如果发布的hashCode中的数组是字节,那么最终可能会出现大量重复数据。 a [0] + a [1]将始终在0到512之间。 添加b将始终产生0到768之间的数字。将这些数字相乘并得到400,000个唯一组合的上限,假设您的数据完美地分布在每个字节的每个可能值中。如果您的数据完全正常,那么此方法的唯一输出可能要少得多。

oalias

赞同来自:

内容太长未翻译

znemo

赞同来自:

您可以尝试使用内存数据库,如HSQLDB

yvero

赞同来自:

我来晚了,但有几条关于大地图的评论:

  1. 正如其他帖子中详细讨论的那样,使用好的hashCode(),Map中的26M条目没什么大不了的。
  2. 但是,这里潜在的隐藏问题是巨型地图对GC的影响。
我假设这些地图是长寿的。即你填充它们并在应用程序的持续时间内保持不变。我也假设应用程序本身很长寿 - 就像某种服务器一样。 Java HashMap中的每个条目都需要三个对象:键,值和将它们连接在一起的Entry。因此,地图中的26M条目意味着26M * 3 == 78M对象。这很好,直到你达到一个完整的GC。然后你有一个暂停世界的问题。 GC将查看每个78M对象并确定它们都存活。 78M +对象只是很多要查看的对象。如果您的应用程序可以忍受偶尔的长时间(可能是几秒钟)暂停,那就没有问题。如果您正在尝试实现任何延迟保证,那么您可能会遇到一个重大问题(当然,如果您想要延迟保证,Java不是选择的平台:))如果地图中的值快速流失,您最终可能会频繁完全收集这大大加剧了这个问题。 我不知道这个问题有很好的解决方案。思路:
  • 有时可以调整GC和堆大小以“大部分”阻止完整的GC。
  • 如果您的地图内容流失很多,您可以尝试Javolution's FastMap - 它可以汇集Entry对象,这可能会降低完全收集的频率
  • 您可以创建自己的地图impl并在byte []上进行显式内存管理(即通过将数百万个对象序列化为单个字节来交换cpu以获得更可预测的延迟[] - 呃!)
  • 不要在这部分使用Java - 通过套接字与某种可预测的内存数据库对话
  • 希望新的G1收藏家能够提供帮助(主要适用于高流失案例)
只是花了很多时间在Java中使用巨型地图的人的一些想法。

afuga

赞同来自:

另一张海报已经指出,由于您将值一起添加,您的哈希码实现将导致大量冲突。我愿意这样做,如果你在调试器中查看HashMap对象,你会发现你有200个不同的哈希值,具有极长的存储桶链。 如果总是具有0..51范围内的值,则每个值将需要6位来表示。如果您总是有5个值,则可以使用左移和添加创建一个30位哈希码:

    int code = a[0];
    code = (code << 6) + a[1];
    code = (code << 6) + b[0];
    code = (code << 6) + b[1];
    code = (code << 6) + b[2];
    return code;
左移很快,但会留下不均匀分布的哈希码(因为6位意味着范围为0..63)。另一种方法是将散列乘以51并添加每个值。这仍然不会完美分布(例如,{2,0}和{1,52}将发生碰撞),并且将比移位慢。
    int code = a[0];
    code *= 51 + a[1];
    code *= 51 + b[0];
    code *= 51 + b[1];
    code *= 51 + b[2];
    return code;

rut

赞同来自:

您是否考虑过使用嵌入式数据库来执行此操作。看看Berkeley DB。它是开源的,现在由Oracle拥有。 它将所有内容存储为Key-> Value对,它不是RDBMS。它的目标是快速。