2

因此，由于 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);
    }
4

4 回答 4

7

从字面上看，我不知道任何现有的 Map 或 Set 实现不会在添加和删除键时产生任何垃圾。

事实上，它甚至在技术上是可行的（在 Java 中，使用定义的Map和SetAPI）的唯一方法是，如果您要对条目数量设置严格的上限。实用的 Map 和 Set 实现需要与它们持有的元素数量成比例的额外状态。此状态必须存储在某处，并且当超出当前分配时，需要扩展存储。在 Java 中，这意味着需要分配新节点。

（好吧，你可以设计一个数据结构类来永远保留旧的无用节点，因此永远不会产生任何可收集的垃圾......但它仍然会产生垃圾。）

那么在实践中你能做些什么......以减少产生的垃圾量。我们HashMap举个例子：

  • 删除条目时会创建垃圾。这是不可避免的，除非您将哈希链替换为从不释放代表链条目的节点的实现。（这是个坏主意……除非您可以保证空闲节点池的大小始终很小。请参阅下文了解为什么这是个坏主意。）

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

    • 您可以在 HashMap 构造函数中提供一个“容量”参数，以将初始哈希数组的大小设置为足够大，以至于您永远不需要调整它的大小。HashMap（但这可能会浪费空间……尤其是如果您无法准确预测它会增长到多大。）

    • 您可以为“负载因子”参数提供一个荒谬的值，以使 HashMap 永远不会调整自身大小。（但这会导致 HashMap 的哈希链是无界的，最终会导致O(N)查找、插入、删除等行为。

事实上，创建垃圾并不一定对性能不利。实际上，挂在节点上以使垃圾收集器不收集它们实际上可能会降低性能。

GC 运行的成本（假设是现代复制收集器）主要在三个方面：

  • 寻找不是垃圾的节点。
  • 将那些非垃圾节点复制到“to-space”。
  • 更新其他非垃圾节点中的引用以指向“到空间”中的对象。

（如果您使用的是低暂停收集器，还有其他成本......通常与非垃圾量成正比。）

GC 工作中唯一真正取决于垃圾数量的部分是将垃圾对象曾经占用的内存归零以使其准备好重用。这可以通过bzero对整个“从空间”的一次调用来完成......或使用虚拟内存技巧。

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

如果您使用弱/软引用来允许 GC 从您的数据结构中收回节点，那么这对 GC 来说就更有用了……以及表示这些引用的空间。

注意：我并不是说对象池总是会使性能变差，只是它经常这样做，尤其是在池变得意外大的情况下。

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

最后，有一种简单的方法可以调整 HashMap，以便在删除相同键后立即添加添加不会产生垃圾（保证）。将其包装在一个 Map 类中，该类缓存“添加”的最后一个条目，并且仅在添加下一个条目时才put真正HashMap执行。当然，这不是通用解决方案，但它确实解决了您之前问题的用例。

于 2012-03-22T03:32:40.713 回答
4

我想您需要一个使用开放寻址的 HashMap 版本，并且您需要比线性探测更好的东西。我不知道具体的建议。

于 2012-03-22T16:20:55.957 回答
4

http://sourceforge.net/projects/high-scale-lib/具有 Set 和 Map 的实现，它们不会在添加或删除键时产生垃圾。该实现使用具有交替键和值的单个数组，因此 put(k,v) 不会创建 Entry 对象。

现在，有一些警告：

  • Rehash 创建垃圾 b/c 它替换底层数组
  • 我认为即使整体大小稳定，如果有足够的交错放置和删除操作，这张地图也会重新散列。（收获墓碑值）
  • 如果您要求输入集合（迭代时一次一个），此映射将创建 Entry 对象

该类称为 NonBlockingHashMap。

于 2012-03-23T08:10:20.063 回答
0

一种选择是尝试修复 HashMap 实现以使用条目池。我已经做到了。:) 您还可以在那里进行其他速度优化。我同意你的看法：Javolution FastMap 的问题令人难以置信。:(

于 2012-03-22T03:03:40.043 回答