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：哈希忽略初始大小（數十億條目的快速哈希表）

回答

相關問題