kotlin - 在 Kotlin 中有效地查看(或复制)大型 HashMap 的子集

Question

我正在尝试从一个巨大的哈希图创建一个子哈希图，而无需复制原始哈希图。

目前我使用这个:

val map = hashMapOf<Job, Int>()
val copy = HashMap(map)
listToRemoveFromCopy.forEach { copy.remove(it) }

这花费了我大约 50% 的当前算法。因为java正在计算 job的哈希值真的经常。
我只想要 map减去 listToRemoveFromCopy在不删除 listToRemoveFromCopy 的新变量中原始列表中的元素。

有人知道吗？

感谢帮助

Answer 1

首先，您需要缓存 Job 的哈希码因为如果您没有 Job 的集合或映射，您使用的任何方法都将是低效的。以最高速度运行的物体。

希望使其成为哈希码的部分是不可变的，否则不应将其用作 key 。是改变 key 非常危险在映射或集合中使用时的哈希码/等于。您应该在第一次调用 hashCode() 时缓存它这样您就不会在此之前产生费用，除非您确定您将永远需要它。

然后改listToRemoveFromCopy成为 Set所以它可以在很多方面有效地使用。您需要在此之前执行先前的步骤。

现在您有多种选择。最有效的是:

Guava具有效用函数 Maps.filterKeys 它将 View 返回到 map 中，您可以创建一个适用于 Set 的谓词。要删除的项目。

 val removeKeys = listToRemoveFromCopy.toSet()
 val mapView = Maps.filterKeys(map, Predicates.not(Predicates.in(removeKeys)))

但是一定要注意 View 上的一些方法不是很有效。如果您避免使用这些方法，这将是性能最佳的选项:

Many of the filtered map's methods, such as size(), iterate across every key/value mapping in the underlying map and determine which satisfy the filter. When a live view is not needed, it may be faster to copy the filtered map and use the copy.

如果你需要复制一份，你有几种方法:

使用 filterKeys 在 map 上一次性创建新 map 。如果删除列表可能占总键的更大百分比，这很好。

val removeKeys = listToRemoveFromCopy.toSet()
val newMap = map.filterKeys { it !in removeKeys }

您应该注意的另一个诱人选项是减号 -复制完整 map 然后删除项目的运算符。它可以使用 listToRemoveFromCopy原样没有它是一个集合，但完整的 map 副本可能会抵消好处。所以不要这样做，除非删除列表是键的一小部分。

val newMapButSlower = map - listToRemoveFromCopy

您可以根据 map 大小和删除列表大小之间的比率选择一个模型，找到一个适合您的“巨大”的断点。

可以在 map 中实现您自己的 View 以避免复制 ，但不是微不足道的(我的意思是非常复杂)。您覆盖的每个方法都必须始终做正确的事情(包括 map 自己的 hashCode 和 equals )，并且必须围绕键集和值创建其他 View 。 entrySet做对了会很讨厌。在尝试自己的解决方案( Guava 或其他)之前，我会寻找一个预先编写的解决方案。这种零拷贝模型将是最有效的解决方案，但代码最多，如果“巨大”意味着大量的处理时间，我会在同一情况下做。如果您误解了实现契约(Contract)的任何部分，则这种方法可能会出错。

您可以使用维护 size 的解决方案包装 Guava 解决方案。属性作为项目被操纵，因此在这种情况下是有效的。如果您知道原始 map 是只读的，您还可以编写更有效的解决方案。有关想法，请查看 FilteredKeyMap 的 Guava 实现及其祖先 AbstractFilteredMap .

总之，很可能缓存你的哈希码会给你带来最大的努力。从那里开始。即使对于 Guava 方法，您也需要它来做。