java - 内部字符串的最佳映射

Question

我有大量要存储在 Map 中的实习字符串(具有少量可能值，因此实习它们很有意义)(用作计数器) .

TreeMap 在树的每个级别进行比较，我想这将涉及字符的 O(n) 比较。 HashMap 将使用哈希存储桶。

鉴于我有一小部分 interned Strings，这意味着引用可以用于相等或排序比较(因此既不需要使用哈希码也不需要使用值)，我想知道是否有合适的结构？

(或者更专门的适合计数的)

我的首要任务是速度和紧凑的表示(我正在处理大量数据)。

(为了避免任何“过早优化”的评论，我正在处理大约 2 亿个项目)。

Answer 1

IdentityHashMap

java.util.IdentityHashMap与 HashMap 类的工作方式类似，但使用身份相等性 == 和哈希码 (System.identityHashCode) 来比较键。它的内存占用也小得多，因为它只使用一个数组来存储键和值。尽管 == 已经快到了，System.identityHashCode(Object)方法有一个 native 实现，它会带来一些开销(但它可能是 JVM 内在的)。

哈希表

HashMap 实现虽然需要更多内存(HashEntry)，但在哈希码计算和相等性检查方面应该具有类似的性能。这是因为 String.equals 方法首先检查引用相等性，然后为每个 String 缓存 String.hashCode。在“紧急情况”下，HashMap 方法也将为非缓存字符串生成正确的结果。在可维护性方面，这可能是更好的选择。