scala - 什么是 fp 风格的“naive hashmap”方式

Question

我有一个格式对列表(a: A, x: Int)，并且x不在列表中重复。现在我知道x在一定范围内0 until n，我想做一个大小数组n，其i第 th 元素是类型Option[A]。如果(a, i)原始列表中有一对，则为Some(a)，否则为None。一个简单的例子：

Original List (n = 6):
(a1, 1)
(a2, 2)
(a3, 5)
Desired Output:
(0, None)
(1, Some(a1))
(2, Some(a2))
(3, None)
(4, None)
(5, Some(a3))

当然，我们可以得到一个可变数组，遍历原始列表并填写相应的元素。但是考虑到时间复杂度不应该是超线性的，n那么 fp 风格的做法是什么？也许这是一个简单的问题，但我就是想不通......希望有人能帮忙。谢谢！

Answer 1

如果你有一个大集合和许多/大的间隙，这将浪费内存。我建议您改用 aMap[Int,B]并使用get返回 a 的操作Option[B]。交换可以如下进行：

scala> List("a1"->1, "a2"->2, "a3"->5)
res3: List[(java.lang.String, Int)] = List((a1,1), (a2,2), (a3,5))

// swap the elements and create a Map
scala> res3.map(_.swap).toMap
res4: scala.collection.immutable.Map[Int,java.lang.String] = Map(1 -> a1, 2 -> a2, 5 -> a3)

scala> res3.map(_.swap).toMap.get(3)
res5: Option[java.lang.String] = None

scala> res3.map(_.swap).toMap.get(1)
res6: Option[java.lang.String] = Some(a1)