Clojure地图界限和一致性 [英] Clojure map limits and consistency

问题描述

我想知道，考虑到Clojure使用32位散列作为其地图实现，如果Clojure地图因此限制了2 ^ 32-1个键（如果这不是真的，它如何管理碰撞）和如果其哈希执行是一致。
TIA！

解决方案

Clojure maps是一种定制实现，是持久性和不可变的即它不使用Java hashmaps，在不可变数据结构中使用时不会提供足够的性能）。

它使用32位哈希码，因此 2 ^ 32个可能的哈希桶。在碰撞的情况下，键和值存储在每个哈希桶的数组中，因此可能有超过2 ^ 32个键。请参阅 PersistentHashMap来源 - 特别是HashCollisionNode内部类用于根据单个哈希码值存储一个或多个键/值。

由于可能的哈希桶的数量是固定的，因此一致的哈希无关紧要 -

另请参阅：

• http://www.infoq.com/presentations/Value-Identity-State-Rich -Hickey （演示文稿解释了并行的Clojure方法，但也涵盖了持久不变的数据结构）

I would like to know , considering that Clojure uses 32-bit hash for its map implementation, if Clojure map has therefore a limit of 2^32-1 keys (and if this is not true, how it manages collisions) and if its hashing implementation is consistent. TIA!

解决方案

Clojure maps are a custom implementation that is persistent and immutable (i.e. it does not use Java hashmaps, which would not provide sufficient performance when used in an immutable data structure).

It uses 32-bit hash codes, hence 2^32 possible hash buckets. In the case of collisions, keys and values are stored in an array for each hash bucket so it is possible to have more than 2^32 keys. See the PersistentHashMap source - in particular the HashCollisionNode inner class is used to store a bucket of keys / values against a single hashcode value.

Since the number of possible hash buckets is fixed, consistent hashing is irrelevant - the key never need to be remapped.

See also:

• http://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey (presentation explaining Clojure approach to concurrency but also covers the persistent immutable data structures)

这篇关于Clojure地图界限和一致性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！