4

如果保证我希望使用的键是唯一的（或者至少可以假设键是唯一的），使用“香草” ConcurrentHashMap是否提供最佳性能，或者是否需要散列函数或 put 方法进行修改以避免不必要的散列？

此外，数字键是否比非数字键（例如具有适当散列函数的字符串或 POJO）具有任何性能优势？

4

5 回答 5

8

正如评论中已经提到的，如果您不需要线程安全方面，请不要使用ConcurrentHashMap.

如果您想要绝对最佳的性能，请考虑实习您的密钥并使用IdentityHashMap。这避免了计算对象的哈希（并且，如评论中所述，否定了equals评估的需要），而是假设引用本身就是哈希。

请注意，您必须确保相同键的两个实例是相同的对象（例如，您必须确保引用相等，而不仅仅是对象相等）。实习你所有的钥匙是实现这一目标的一种方法。

实施说明：这是一个简单的线性探针哈希表，如 Sedgewick 和 Knuth 的文本中所述。该数组交替保存键和值。（与使用单独的数组相比，这对于大型表具有更好的局部性。）对于许多 JRE 实现和操作混合，此类将产生比 HashMap（使用链接而不是线性探测）更好的性能。

如果您知道所有密钥，也许您还可以考虑完美散列？或者映射到一个简单的数组结构？

于 2011-07-12T12:45:35.510 回答
1

ConcurrentHashMap 是最昂贵的 HashMap 实现，这是因为它是线程安全的。

所有地图都必须有唯一的键，所以这是给定的。

如果您使用支持 TLongHashMap 等基元的集合，则使用数字具有性能优势，但是使用自定义哈希映射可能会更快。

来自http://vanillajava.blogspot.com/2011/07/low-gc-in-java-using-primitives.html

Test                                    Performance Memory used
Use Integer wrappers and HashMap        71 - 134 (ns)   53 MB/sec
Use int primitives and HashMap          45 - 76 (ns)    36 MB/sec
Use int primitives and FastMap          58 - 93 (ns)    28 MB/sec
Use int primitives and TIntIntHashMap   18 - 28 (ns)    nonimal
Use int primitives and simple hash map   6 - 9 (ns)     nonimal
于 2011-07-12T12:46:05.947 回答
1

如果保证我希望使用的键是唯一的（或者至少可以假设键是唯一的），那么使用“香草”ConcurrentHashMap 是否提供最佳性能，

ConcurrentHashMap如果Map是潜在的并发瓶颈，您通常会使用。如果您的应用程序是单线程的或没有争用，ConcurrentHashMap则比HashMap.

或者是否需要修改散列函数或 put 方法以避免不必要的散列？

哈希函数在哈希表的每个“探针”中被评估一次；例如，每次get或put操作一次。您可以通过缓存结果来降低散列函数的成本，但这会为每个键对象额外花费 4 字节的存储空间。缓存是否值得优化取决于：

  • 与应用程序的其余部分相比，散列的相对成本是多少，以及
  • 调用的比例hashCode()实际上将使用缓存的值。

这两个因素都是高度应用特定的。

（顺便说一下，使用身份哈希码作为哈希值的长期成本也是额外的 4 个字节的存储空间。）

此外，数字键是否比非数字键（例如具有适当散列函数的字符串或 POJO）具有任何性能优势？

在数字情况下，散列函数可能更便宜，但是否值得取决于使用数字键是否存在特定于应用程序的缺点。而且，如上所述，相对成本是应用程序的具体情况。例如，成本与String.hashCode()被散列的字符串的长度成正比。

于 2011-07-12T13:06:56.967 回答
0

Java 的 HashMap 最终由一个数组支持，Entry<K,V>其中 K 的哈希码用于确定存储条目的数组中的槽。

使用的数组的大小（通常从 16 开始）远小于可能的哈希码数量（2^32 ~= 40 亿），因此即使哈希码是唯一的，该数组也必然会发生冲突。

只要您的 hashcode() 方法速度快，用作 Key 的类型之间就没有区别。请记住，hashcode() 方法可能会被调用很多次，所以如果它很慢，您可以在对象内部缓存它。

于 2011-07-12T12:49:03.313 回答
0

我有 ConcurrentHashMap 实例映射，它通过多线程访问。见下面的代码片段。这些怎么样？

Iterator<String> it = new TreeSet<String>(map.keySet()).iterator();
            while(it.hasNext())
            {
                id = it.next();
                synchronized(map)
                {
                    msg = map.get(id);
                    if(msg != null)
                        map.remove(id);
                }
                if(msg != null)
                listener.procMessage(msg);
            }
于 2011-07-15T11:05:32.717 回答