ree*_*eem 18 algorithm haskell hashtable binary-search-tree data-structures
从我对Haskell的有限知识来看,似乎Maps(来自Data.Map)应该像其他语言中的字典或散列表一样使用,但它们被实现为自平衡二进制搜索树.
为什么是这样？使用二叉树将查找时间减少到O(log(n))而不是O(1),并且要求元素在Ord中.当然有一个很好的理由,那么使用二叉树有什么好处呢？
也:
在什么应用程序中,二叉树比哈希表更差？反过来呢？在许多情况下,一个人会比另一个人更受欢迎吗？Haskell中是否有传统的哈希表？
Joh*_*n L 28
如果没有可变状态,则无法有效地实现散列表,因为它们基于数组查找.密钥是哈希的,哈希将索引确定为桶数组.在没有可变状态的情况下,将元素插入哈希表变为O(n),因为必须复制整个数组(替代的非复制实现,如DiffArray,会引入显着的性能损失).二叉树实现可以共享其大部分结构,因此只需要在插入上复制几个指针.
Haskell肯定可以支持传统的哈希表,只要更新是在合适的monad中.该哈希表包可能是最广泛使用的实现.
二叉树和其他非变异结构的一个优点是它们是持久的:可以保留较旧的数据副本而不需要额外的簿记.例如,这在某种事务算法中可能很有用.它们也是自动线程安全的(尽管更新在其他线程中不可见).
J. *_*son 11
传统的哈希表在其实现中依赖于内存变异.可变内存和引用透明性在最后,因此将哈希表实现降级为IO或STmonad.通过将旧叶留在内存中并返回指向更新树的新根节点,可以持久且高效地实现树.这让我们拥有纯净Map的.
典型的参考是Chris Okasaki的Purely Functional Data Structures.
为什么是这样？使用二叉树将查找时间减少到O(log(n))而不是O(1)
查找只是其中一项操作; 在许多情况下,插入/修改可能更重要; 还有内存考虑因素.选择树表示的主要原因可能是它更适合纯函数语言.正如"真实世界Haskell" 所说:
Maps为我们提供了与其他语言中的哈希表相同的功能.在内部,地图实现为平衡二叉树.与哈希表相比,这是具有不可变数据的语言中更有效的表示.这是纯粹的函数式编程如何影响我们编写代码的最明显的例子:我们选择能够干净利落地表达并有效执行的数据结构和算法,但我们对特定任务的选择往往与命令式语言中的对应物不同.
这个:
并要求元素在Ord中.
似乎不是一个很大的劣势.毕竟,使用哈希映射需要密钥Hashable,这似乎更具限制性.
在什么应用程序中,二叉树比哈希表更差？反过来呢？在许多情况下,一个人会比另一个人更受欢迎吗？Haskell中是否有传统的哈希表？
遗憾的是,我无法提供广泛的比较分析,但是有一个哈希映射包,您可以在此博客文章中查看其实现细节和性能数据,并自行决定.