需要一个有效的Map或Set,在添加和删除时不会产生任何垃圾

Question

因为Javolution不起作用(见这里),我非常需要一个高效的Java Map实现,并且在简单的使用下不会产生垃圾.java.util.Map在添加和删除密钥时会产生垃圾.我检查了Trove和Guava,但它看起来没有Set <E>实现.我在哪里可以找到一个简单而有效的替代方案java.util.Map？

编辑EJP:

添加条目时会分配一个条目对象,并在删除它时将其释放到GC.:(

   void addEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

Answer 1

从字面上看,我不知道Map或Set的任何现有实现在添加和删除密钥时从不产生任何垃圾.

事实上,只有这样,它甚至在技术上是可能的(在Java中,使用Map和SetAPI的定义)是,如果你是实行严格的上限的条目数.实际的Map和Set实现需要与它们所持有的元素数量成比例的额外状态.此状态必须存储在某处,并且当超出当前分配时,需要扩展存储.在Java中,这意味着需要分配新节点.

(好吧,你可以设计一个永久保存在旧无用节点上的数据结构类,因此从不生成任何可收集的垃圾......但它仍然会产生垃圾.)

那么在实践中你能做些什么呢？减少产生的垃圾量.我们以HashMap一个例子为例:

• 删除条目时会创建垃圾.这是不可避免的,除非您使用永远不会释放代表链条目的节点的实现替换哈希链.(这是一个坏主意......除非你能保证免费节点池的大小总是很小.请参阅下面的原因,为什么这是一个坏主意.)

• 调整主哈希数组大小时会创建垃圾.这可以通过以下几种方式避免:

  • 您可以在HashMap构造函数中给出一个'capacity'参数,以便将初始哈希数组的大小设置得足够大,以至于您永远不需要调整它的大小.(但这可能会浪费空间......特别是如果你无法准确预测HashMap它将会增长多少.)

  • 你可以为'load factor'参数提供一个荒谬的值,使HashMap永远不会自己调整大小.(但这导致HashMap的哈希链无限制,最终会出现O(N)查找,插入,删除等行为.

事实上,创建垃圾并不一定对性能有害.实际上,挂在节点上以便垃圾收集器不收集它们实际上会对性能造成影响.

GC运行的成本(假设现代复制收集器)主要在三个方面:

• 查找非垃圾的节点.
• 将这些非垃圾节点复制到"to-space".
• 更新其他非垃圾节点中的引用以指向"to-space"中的对象.

(如果您使用的是低暂停收集器,则还有其他成本...通常与非垃圾量成比例.)

GC的工作中唯一实际依赖于垃圾量的部分是将垃圾对象占用的内存归零以使其可以重用.这可以通过一次bzero调用整个"从空间"......或使用虚拟内存技巧来完成.

假设您的应用程序/数据结构挂起到节点上以避免产生垃圾.现在,当GC运行时,它必须做额外的工作来遍历所有这些额外的节点,并将它们复制到"to-space",即使它们不包含有用的信息.此外,这些节点正在使用内存,这意味着如果应用程序的其余部分生成垃圾,则保留它的空间将会减少,并且GC将需要更频繁地运行.

如果您使用弱/软引用来允许GC从数据结构中回收节点,那么GC的更多工作......以及表示这些引用的空间.

注意:我并没有声称对象池总是会让性能变得更糟,只是它经常会这样,特别是如果池意外地变大了.

当然,这就是为什么HashMap和类似的通用数据结构类不进行任何对象池化的原因.如果他们这样做了,他们会在程序员不期望的情况下表现得非常糟糕......而且他们会真的被打破,IMO.

最后,有一种简单的方法可以调整HashMap,这样在紧接着删除相同的键后立即生成不会产生垃圾(保证).将它包装在一个缓存最后一个条目"添加"的Map类中,并且只put在HashMap添加下一个条目时才实现.当然,这不是一个通用的解决方案,但它确实解决了您之前问题的用例.