Scala中的mutable.HashTable类

Question

在线文档并没有给出太多关于它的说明(http://www.scala-lang.org/api/2.12.0/scala/collection/mutable/HashTable.html)，也不可能找到任何使用它的例子。我想知道如何将元素放入mutable.HashTable中。

在我可以使用的研究和删除操作中，是否有相同时间复杂度的数据结构？

Answer 1

mutable.HashTable是一种特质。

trait HashTable[A, Entry >: Null <: HashEntry[A, Entry]] extends HashTable.HashUtils[A]

默认负载因子为75%

private[collection] final def defaultLoadFactor: Int = 750

使用数组来实现，

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

1)您必须使用HashTable**，的实现，这些实现是** mutable.HashMap 或 mutable.LinkedHashMap**.**

例如，

scala> import scala.collection.mutable.HashMap
import scala.collection.mutable.HashMap

scala> new HashMap[String, String]
res9: scala.collection.mutable.HashMap[String,String] = Map()

添加元素

scala> res9+= "order-id-1" -> "delivered"
res10: res9.type = Map(order-id-1 -> delivered)

scala> res9
res11: scala.collection.mutable.HashMap[String,String] = Map(order-id-1 -> delivered)

访问元素

scala> res9("order-id-1")
res12: String = delivered

写复杂度应该与hashmap数据结构中的O(1)相同。找到哈希码并将其添加到条目数组中。

  def += (kv: (A, B)): this.type = {
    val e = findOrAddEntry(kv._1, kv._2)
    if (e ne null) e.value = kv._2
    this
  }

  protected def findOrAddEntry[B](key: A, value: B): Entry = {
    val h = index(elemHashCode(key))
    val e = findEntry0(key, h)
    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
  }

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

2.如果使用LinkedHashMap ，则使用链接条目来保持插入顺序。

  @transient protected var firstEntry: Entry = null
  @transient protected var lastEntry: Entry = null

例如，

scala> import scala.collection.mutable.LinkedHashMap
import scala.collection.mutable.LinkedHashMap

scala> LinkedHashMap[String, String]()
res0: scala.collection.mutable.LinkedHashMap[String,String] = Map()

scala> res0 += "line-item1" -> "Delivered" += "line-item2" -> "Processing"
res2: res0.type = Map(line-item1 -> Delivered, line-item2 -> Processing)

scala> res0
res3: scala.collection.mutable.LinkedHashMap[String,String] = Map(line-item1 -> Delivered, line-item2 -> Processing)