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

我想了解Scala的哈希函数对于大哈希表的规模有多好（数十亿条目，例如用于存储特定位数的DNA出现）。有趣的是，HashMap和OpenHashMap都忽略了指定初始大小（2.9.2。和2.10.0，最新版本）的参数。Scala：哈希忽略初始大小（数十亿条目的快速哈希表）

我认为这是因为在第一个800.000左右之后添加新元素变得非常慢。

我已经尝试增加要插入的字符串中的熵（仅在下面的代码中使用字符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 
    } 
}

来源

2012-10-31 Alexander

你不打算用完内存吗？ –

32或64位jvm？关于忽略初始大小：它没有，你可以检查HashMap的源代码 – Arjan

感谢您的答案。为了澄清，这将被部署在具有256G + RAM的机器上。 @Noah：但每次翻倍后都要复制桶内容，对吧？但即使这是真的，它也没有向我解释为什么在重复800.000次左右之后出现这种性能下降的情况 - 我认为重新排列后会急剧下降，然后再恢复到全速。 – Alexander

首先，你不能覆盖INITIALSIZE，我觉得斯卡拉咱们你，因为它包在哈希表私人：

private[collection] final def initialSize: Int = 16

第二，如果你要设置的初始大小，你必须给它一个哈希表你想要的初始尺寸。因此，如果没有从16开始制作这张地图，真的没有什么好的方法，但它的确增长了2倍，所以每次调整大小都会变得更好。

三，scala集合比较慢，我会推荐java/guava/etc集合。

最后，对于大多数硬件来说，数十亿的条目有点多，你可能会用完内存。你最有可能需要使用内存映射文件，这里有一个很好的例子（没有散列虽然）：

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

更新1 下面是更换一个不错滴的Java集合：

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

更新2 我跑你的代码，它确实约800,000项放缓，但后来我带动了Java堆SI泽和它运行良好。尝试使用像这样的JVM：

-Xmx2G

或者，如果你想用你的记忆中每一点：

-Xmx256G

来源

2012-11-01 02:09:24 Noah

我不认为高规模的lib会帮助这里。无论如何，不涉及地图大小的问题。高规模的lib提供的数据结构即使在许多CPU同时使用的情况下也能很好地运行。我不认为有关处理大量藏品的任何具体内容。 – overthink

你认为他将如何构建十亿条散列表？要多线程处理一堆cpus，否则会花费很长时间。 – Noah

这些是错误的数据结构。你会很快达到内存限制（除非你有100 + GB，即使这样你仍然会非常快地达到限制）。

我不知道scala是否存在合适的数据结构，尽管有人可能会用Java做一些事情。

来源

2012-10-31 22:25:31

我不会用Java数据结构来管理地图上百亿条目。原因：

最大水桶在Java HashMap的是2^30（〜1B），所以
- ，默认加载因子时，地图会尝试后750个项调整，你会失败
- 您需要使用大于1的负载因子（例如理论上5个项目会获得50亿个项目）
- 高负载因素会导致很多散列冲突，并且读写性能都是将开始严重劣化
- 一旦你真的超过了Integer.MAX_INTEGER值I不知道什么陷阱存在 - .size（）在地图上将无法返回真正的计数，例如
我会非常担心在Java中运行256 GB的堆 - if你曾经打了一个完整的GC它会锁定世界很长一段时间来检查对象的数十亿美元的老根

如果是我，我会看的离堆解决方案：数据库某种。如果你只是存储（hashcode，count），那么许多关键值存储中的一个可能工作。最大的障碍是找到一个可以支持数十亿记录的记录（有些记录在2^32）。

如果你可以接受一些错误，概率方法可能值得一看。我不是这里的专家，但列出的东西here听起来有关。

来源

2012-11-01 15:46:33 overthink

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

回答

相关问题