巨大地图的不可变地图实施

Question

如果我有一个不可变的地图,我可能期望(在很短的时间内 - 如几秒钟)添加/删除数十万个项目,标准HashMap是一个坏主意？假设我想在<10秒内通过Map传递1Gb数据,这样任何一次瞬间Map的最大大小只有256Mb.

我得到的印象是地图保留了某种"历史",但我将始终访问最后更新的表(即我不传递地图),因为它是一个私有成员变量,Actor只更新/访问从反应中.

基本上我怀疑这个数据结构可能(部分)因为在短时间内读取大量数据时JVM内存不足而出现问题.

我是否会更好地使用不同的地图实现,如果是这样,它是什么？

Answer 1

哎哟.为什么你必须使用不可变的地图？垃圾收集器差!除了(log n)时间之外,不可变映射通常需要(log n)每个操作的新对象,或者它们实际上只是将可变散列映射和层变换集包装在顶部(这会减慢速度并增加对象创建的数量).

不变性很好,但在我看来,这似乎不适合使用它.如果我是你,我会坚持下去scala.collection.mutable.HashMap.如果需要并发访问,请改为包装Java util.concurrent.

您还可能希望增加JVM中年轻代的大小:-Xmn1G或更多(假设您正在运行-Xmx3G).此外,使用吞吐量(并行)垃圾收集器.

在FP中,人们更喜欢基于有序的平衡树的地图,而不是基于散列表的地图 - 正是因为很难获得持久版本.根据我的理解,FP人员很快就会放弃哈希表的O(1)查找平衡树的O(logn),其推理基本上相当于"谁关心*那么多性能,没关系,我比如不变性".好吧,有些人只是喜欢性能:) (5认同)
不可变性的程度取决于应用程序.如果您正在运行一个应用程序,例如,消息线程的树被发送到一堆客户端,不变性是天赐之物 - 您只需发送当前树,您不必担心数据结构本身会更改来自你.(你仍然需要抓住像客户端要求在线程中添加注释的情况,这些线程在响应时被删除.)对于非常快速转换的私有数据结构中的高吞吐量工作,不变性几乎没有什么优势,需要很多开销. (3认同)

Answer 2

那太糟糕了.你说你总是想要访问最后更新的表,这意味着你只需要一个短暂的数据结构,没有必要支付持久数据结构的成本- 就像交易时间和内存来获得完全可论证的"样式点" ".当你没有被要求时,你不是通过使用盲目持久的结构来建立你的业力.

此外,哈希表是一种特别难以持久化的结构.换句话说,"非常非常慢"(基本上,当读取数量大大超过写入数量时,它可用 - 而且您似乎谈论了许多写入).

顺便说一句,ConcurrentHashMap在这个设计中没有意义,因为地图是从一个演员那里访问的(这是我从描述中理解的).