scala – 不可变地图使用什么样的数据结构？
发布时间：2020-12-16 09:22:56 所属栏目：安全 来源：网络整理
导读：我知道正常的可变地图是如何工作的(使用散列表),我知道不可变的列表是如何工作的(递归链表)和它们在可变列表上的优势(不间断地添加而不会弄乱原始的列表),但是不可变的地图(例如Scala)如何工作？ 我知道在生成新地图时不会弄乱原始地图的优点,但底层数据结构
|
我知道正常的可变地图是如何工作的(使用散列表),我知道不可变的列表是如何工作的(递归链表)和它们在可变列表上的优势(不间断地添加而不会弄乱原始的列表),但是不可变的地图(例如Scala)如何工作？
我知道在生成新地图时不会弄乱原始地图的优点,但底层数据结构如何工作,以及它们具有什么样的性能特征,例如与可变哈希表相比？有没有人使用的标准数据结构来实现这些,我可以去查看CLRS /维基百科？ 解决方法
持久的散列图使用一个名为
Hash trie的结构实现.它是
originally proposed by Phil Bagwell(谁是EPFL的Scala组成员),但实际上是由Clojure实现的.当它在2010年出现时,它会打到Scala.
Dan Spiewak有一个great talk on functional data structures,其中哈希特技的机制非常清楚地解释(与其他事情,如银行家的队列)！他也在谈话中解释了渐近的大O表现. 去年10月,菲尔在London scala Lift Off发表了另一个演讲,这次是并行持久的数据结构. 持续排序的地图通过Red-Black tree实现 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |