何时使用TrieMap是否合适？

Question

我一直在阅读一些帖子,并想知道是否有人可以提出TrieMap何时比使用HashMap更可取的情况.

基本上什么架构决策应该激励使用TrieMap？

Answer 1

根据文件.它是可变集合,可以安全地用于多线程应用程序.

并发hash-trie或TrieMap是concurrent thread-safe lock-free 哈希数组映射trie的实现.它用于实现并发映射抽象.它有particularly scalable concurrent插入和删除操作,是memory-efficient.它支持O(1),原子,无锁快照,用于实现可线性化的无锁大小,迭代器和清除操作.评估(延迟)快照的成本分布在后续更新中,从而使快照评估可以水平扩展.

有关详细信息,请参阅:http://lampwww.epfl.ch/~prokopec/ctries-snapshot.pdf

它也有非常好的API caching.因此,例如,您必须计算不同数量的阶乘,有时重复使用此结果.

  object o {

    val factorialsCache = new TrieMap[Int, Int]()

    def factorial(num: Int) = ??? // really heavy operations
    def doWorkWithFuctorial(num: Int) = {
      val factRes = factorialsCache.getOrElseUpdate(num, {
        // we do not want to invoke it very often
        factorial(num)
           // this function will be executed only if there are no records in Map for such key
      })
      // start do some work `withfactRes`
      factRes
    }
  }

注意 - 上面的函数使用全局状态(缓存)进行写操作,但在并发线程中使用它是绝对安全的.你不会丢失任何数据.