scalaにおけるHashMapの実現原理解析

HashMapは通常最もよく使われるデータ構造の一つであり,検索と削除要素はO(1)の時間的複雑さを有する.本稿では,scala言語におけるHashMap内部の動作原理を簡単な例で説明し,getとputがどのように動作しているかを見る.
使用例

  def main(args: Array[String]): Unit = {
    val m = mutable.HashMap[String,Int]()
    m.put("a",1)
    m.put("b",2)
    println("m:"+m)
    println("a="+m.get("a"))

    for( (k,v)  //    
      print(k,v)
    }
  }

      ：
   m:Map(b -> 2, a -> 1)
   a=Some(1)
   (b,2)(a,1)

HashMap実現原理
1、データ構造
HashMapは配列とチェーンテーブルを結合し、keyのhash値は配列の下付きであり、同じhash値のkeyはチェーンテーブル方式で格納される.
配列はtableで、table配列はEntryクラスのオブジェクトを格納し、EntryのkeyはHashMapのキー、valueはHashMapの値、nextは次のEntry要素である

@transient protected var table: Array[HashEntry[A, Entry]] = new Array(initialCapacity)

trait HashEntry [A, E] {
  val key: A
  var next: E = _
}
final class DefaultEntry[A, B](val key: A, var value: B)
      extends HashEntry[A, DefaultEntry[A, B]] with Serializable
{
  override def toString = chainString

  def chainString = {
    "(kv: " + key + ", " + value + ")" + (if (next != null) " -> " + next.toString else "")
  }
}

2、put方法
putのコード実装を見てみましょう.

  override def put(key: A, value: B): Option[B] = {
    val e = findOrAddEntry(key, value)
    if (e eq null) None
    else { val v = e.value; e.value = value; Some(v) } //  key     value     
  }

  /** Find entry with given key in table, or add new one if not found.
     *  May be somewhat faster then `findEntry`/`addEntry` pair as it
     *  computes entry's hash index only once.
     *  Returns entry found in table or null.
     *  New entries are created by calling `createNewEntry` method.
     */
    protected def findOrAddEntry[B](key: A, value: B): Entry = {
      val h = index(elemHashCode(key))  //  hash          
      val e = findEntry0(key, h)  //        value    
      if (e ne null) e else { addEntry0(createNewEntry(key, value), h); null }
    }

    private[this] def findEntry0(key: A, h: Int): Entry = {
        var e = table(h).asInstanceOf[Entry]
        while (e != null && !elemEquals(e.key, key)) e = e.next
        e
    }

まずhashMapのキーキーキーからtable配列の下付きhを算出し、tableのh番目の要素eを見つけ、eが空ではなくeのキーとHashMapのキーが同時にeのnextをeが最後に返すeが空でなければキーが存在することを示し、Entryオブジェクトを返し、そのvalue値を更新し、eが空であれば追加する必要がある

  protected def createNewEntry[B](key: A, value: B): Entry

  private[this] def addEntry0(e: Entry, h: Int) {
    e.next = table(h).asInstanceOf[Entry] // e        
    table(h) = e
    tableSize = tableSize + 1
    nnSizeMapAdd(h)
    if (tableSize > threshold)
      resize(2 * table.length)
  }

要素を追加するたびにtableSizeが1つ追加され、要素の合計個数、すなわちsizeメソッドが返す結果を表します.override def size: Int = tableSize

   protected def elemHashCode(key: KeyType) = key.##
     ##     
   ##():Int

オブジェクトのhasCodeを返します.hascodeメソッドとは異なり、numericsでは値と等しいハッシュ値を返し、nullではhashcodeを返し、hashCodeではNullPointerExceptionを放出します.
2、table拡張
HashMapの要素が多くなると,配列の長さが固定されるためhash衝突の確率も高くなる.したがって、クエリの効率を向上させるためには、HashMapの配列を拡張するのが一般的ですが、HashMapの配列を拡張した後、最もパフォーマンスを消費する点が現れます.元の配列のデータは、新しい配列の位置を再計算し、resizeである必要があります.
では、HashMapはいつ拡張されますか?HashMapの要素数が配列サイズthresholdを超えると配列拡張が行われ、thresholdのデフォルト値はtableサイズの0.75であり、これは折衷の値である.つまり、デフォルトでは配列サイズが16であるため、HashMapの要素の個数が16*0.75=12を超えると、配列のサイズを2*16=32に拡張して2倍に拡大し、各要素の配列内の位置を再計算するという非常に消耗的な操作である.

  private def resize(newSize: Int) {
    val oldTable = table
    table = new Array(newSize)
    nnSizeMapReset(table.length)
    var i = oldTable.length - 1
    while (i >= 0) {
      var e = oldTable(i)
      while (e != null) {
        val h = index(elemHashCode(e.key))
        val e1 = e.next
        e.next = table(h).asInstanceOf[Entry]
        table(h) = e
        e = e1
        nnSizeMapAdd(h)
      }
      i = i - 1
    }
    threshold = newThreshold(_loadFactor, newSize)
  }

   private[collection] final def defaultLoadFactor: Int = 750 // corresponds to 75%
    private[collection] final def loadFactorDenum = 1000 // should be loadFactorDenom, but changing that isn't binary compatible

  private[collection] final def newThreshold(_loadFactor: Int, size: Int) =
   ((size.toLong * _loadFactor) / loadFactorDenum).toInt  //  threshold         75%

3、getメソッド
put操作を理解するとgetメソッドはずっと簡単で、getはput操作の一歩にすぎません.

  def get(key: A): Option[B] = {
    val e = findEntry(key)
    if (e eq null) None
    else Some(e.value)
  }

  protected def findEntry(key: A): Entry =
     findEntry0(key, index(elemHashCode(key)))

まとめ
HashMapは、キー値対(key-value)マッピングを格納ハッシュリストである.HashMapの実装は同期ではなく、スレッドが安全ではないことを意味します.そのkey、valueはnullです.さらに,HashMapにおけるマッピングは秩序化されていない.HashMapの実装はハッシュテーブルHashTableによって実現される