保证键唯一时 HashMap 的性能

Question

如果我希望使用的密钥保证是唯一的（或者至少可以假设密钥是唯一的），那么使用“vanilla”ConcurrentHashMap 提供最佳性能，或者是否需要修改哈希函数或 put 方法以避免不必要的哈希？

另外，数字键相对于非数字键（例如具有适当哈希函数的字符串或 POJO）是否具有任何性能优势？

Answer 1

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

如果您想要绝对最佳的性能，请考虑保留您的密钥并使用 IdentityHashMap。这避免了计算对象的哈希（并且，正如注释中提到的，不需要评估 equals），而是假设引用本身就是哈希。

显然，您必须确保同一键的两个实例是同一对象（例如，您必须确保引用相等，而不仅仅是对象相等）。保留所有密钥是实现这一目标的一种方法。

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

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

Answer 2

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 

Answer 3

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

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

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

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

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

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

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

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

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

Answer 4

Java 的 HashMap 最终由 Entry 数组支持，其中 K 的哈希码用于确定存储 Entry 的数组中的槽。

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

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

Answer 5

我有 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);
            }