Scala：哈希表忽略初始大小（用于数十亿条目的快速哈希表）

Question

我正在尝试找出Scala的哈希函数在大型哈希表（例如存储特定DNA位的出现次数）中的扩展性。

然而，有趣的是，无论是HashMap还是OpenHashMap都似乎忽略了指定初始大小的参数（最新版本为2.9.2和2.10.0）。

我认为这是因为在添加首个80万元素后，添加新元素变得更加缓慢。

我尝试过增加要插入的字符串中的熵（代码下面仅使用ACGT字符），但没有效果。

关于这个特定问题有什么建议吗？我也很想听听您是否认为在具有数十亿条记录的哈希表中使用Scala内置类型是一个好主意。

import scala.collection.mutable.{ HashMap, OpenHashMap }    
import scala.util.Random

object HelloWorld {
    def main(args: Array[String]) {


        val h = new collection.mutable.HashMap[String, Int] {
            override def initialSize = 8388608
        }

        // val h = new scala.collection.mutable.OpenHashMap[Int,Int](8388608); 



        for (i <- 0 until 10000000) {
            val kMer = genkMer()

            if(! h.contains(kMer))
            {
                h(kMer) = 0;
            }
            h(kMer) = h(kMer) + 1;

            if(i % 100000 == 0)
            {
                println(h.size);
            }
        }

        println("Exit. Hashmap size:\n");
        println(h.size);

    }

    def genkMer() : String =
    {
        val nucs = "A" :: "C" :: "G" :: "T" :: Nil

        var s:String = "";
        val r = new scala.util.Random
        val nums = for(i <- 1 to 55 toList) yield r.nextInt(4) 
        for (i <- 0 until 55) {
            s = s + nucs(nums(i))
        }
        s
    }
}

- Alexander

---

你不会用尽内存吗？ - Joshua Martell

32位还是64位JVM？关于忽略初始大小：它并没有，你可以查看HashMap的源代码。 - Arjan

感谢您的回答。为了澄清，这将部署在具有256G+ RAM的机器上。@Noah：但是每次加倍后都必须复制桶内容，对吗？但即使如此，我也不明白为什么在800,000左右的迭代之后会出现性能下降--我期望在进行重新排列时会出现急剧下降，然后恢复到全速运行。 - Alexander

@Arjan：64位。除了我描述的性能下降之外，我的程序的内存占用不管我设置什么初始大小都不会改变。 - Alexander

请看我的更新，你需要增加最大堆大小。 - Noah

Answer 1

我不会使用Java数据结构来管理数十亿条记录的映射。原因如下：

• Java HashMap 中最大的桶容量是2^30（约10亿），所以
  • 默认情况下，当地图尝试在750 M条目后进行调整大小时，您将失败
  • 您需要使用负载系数> 1（例如5理论上可以获得50亿个条目）
  • 负载系数过高会导致大量哈希冲突，读写性能都会急剧下降
  • 一旦实际超过Integer.MAX_INTEGER值，我不知道存在哪些问题 - 例如，.size()无法返回真正的计数
• 如果在Java中运行256 GB堆栈，我会非常担心 - 如果您遇到完全GC，它会锁定世界很长时间以检查旧代中的数十亿个对象

如果是我，我会寻找一个离线解决方案：某种类型的数据库。如果只存储（哈希码，计数），那么其中的许多键值存储之一可能起作用。最大的障碍是找到一个可以支持数十亿条记录的数据库（有些最多只支持2^32）。

如果您可以接受一些错误，则值得研究概率方法。我在这方面不是专家，但是此处列出的内容似乎与此相关。

- overthink

Answer 2

首先，您无法覆盖initialSize，我认为Scala可以让您这样做，因为它在HashTable中是包私有的。

private[collection] final def initialSize: Int = 16

第二点，如果您想设置初始大小，您必须给它一个哈希表，以便设置您想要的初始大小。因此，在不从16开始构建此映射的情况下，没有很好的方法，但它会按2的幂增长，因此每次调整大小应该会更好。

第三点，Scala集合相对较慢，我建议使用Java / Guava等集合。

最后，数十亿条目对于大多数硬件来说有点太多了，您可能会耗尽内存。您很可能需要使用内存映射文件，这是一个很好的例子（没有哈希）：

https://github.com/peter-lawrey/Java-Chronicle

更新 1： 这是一个很好的 Java 集合替代品：

https://github.com/boundary/high-scale-lib

更新2： 我运行了你的代码，在大约80万条记录时速度变慢了，但是我增加了Java堆大小，然后它就运行得很好。尝试使用类似于以下的jvm设置：

-Xmx2G

或者，如果你想要使用你的所有记忆空间：

-Xmx256G

- Noah

---

我认为高规模库在这里不会有所帮助。特别是与地图大小相关的问题。高规模库提供了数据结构，即使许多CPU同时使用它们也能表现出色。但我认为它没有处理巨大集合的特定功能。 - overthink

你认为他会如何构建一个十亿条目的哈希表？必须使用多线程和一堆CPU，否则这将需要很长时间。 - Noah

Answer 3

这些数据结构是错误的。你很快就会遇到内存限制问题（除非你有100+GB，即使有那么多也会很快达到限制）。

我不知道是否存在适用于Scala的数据结构，尽管可能有人已经在Java上做了一些工作。

- Ivan Meredith