Threadsafe可变集合,快速元素删除和随机获取

Question

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

第一个:同步变量中的Seq.

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为true.主要问题是制作一个快速的getRandom方法(在最坏的情况下不是O(n)).

有没有更好的方法来实现这个？

Answer 1

Scala的Trie是一种无锁数据结构,支持快照(也就是你的currentAvailable)和快速删除