multithreading - 具有快速元素删除和随机获取的线程安全可变集合

Question

我需要一个具有三个操作的线程安全数据结构:remove、getRandom、reset。 我现在只有两个想法。

首先:seq in syncronized var.

val all: Array[String] =  ... //all possible.
var current: Array[String] = Array.empty[String]

def getRandom(): = {
  val currentAvailable = current
  currentAvailable(Random.nextInt(currentAvailable.length))
}

def remove(s: String) = {
  this.syncronized {
     current = current diff Seq(s)
  }
}

def reset(s: String) = {
  this.syncronized {
     current = all
  }
}

第二个: 维护一些 Map[String,Boolean]，当元素当前存在时，bool 为真。主要问题是制作一个快速的 getRandom 方法(在最坏的情况下不是像 O(n) 这样的方法)。

有没有更好的方法来实现它？

Answer 1

Scala's Trie是一个无锁数据结构，支持快照(又名你的currentAvailable)和快速移除