Class mutable.HashTable 在 Scala 中

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) 相同。您找到哈希码并添加到 Entry 的数组中。

  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)

Class mutable.HashTable 在 Scala 中

Class mutable.HashTable in Scala

scala

hashtable

data-structures