Li *_*oyi 15 functional-programming scala immutability
我知道正常的可变映射是如何工作的(使用哈希表),我知道不可变列表是如何工作的(递归链表)和它们相对于可变列表的优势(恒定时间附加而不会弄乱原始数据)但是不可变映射(例如Scala)如何工作？
我知道在生成新映射时不会弄乱原始映射的优势,但是底层数据结构如何工作,以及它们具有哪种性能特征,例如与可变哈希表相比？是否有人们用来实现这些的标准数据结构,我可以在CLRS /维基百科中查找？
oxb*_*kes 19
持久哈希映射使用称为哈希特里结构的结构实现.它最初是由Phil Bagwell(他是EPFL的Scala小组成员)提出的,但实际上是由Clojure首先实现的.当2.8在2010年问世时,它击中了scala .
Dan Spiewak 对功能数据结构进行了很好的讨论,其中哈希特里的机制被非常清晰地解释(以及其他诸如银行家的队列)!他还在谈话中非常好地解释了渐近的大O表现.
去年10月,菲尔在伦敦scala Lift Off举行了另一场演讲,这次是关于并行持久数据结构.
持久性排序映射通过红黑树实现