diff options
author | RĂ¼diger Klaehn <rklaehn@gmail.com> | 2014-01-14 23:38:03 +0100 |
---|---|---|
committer | RĂ¼diger Klaehn <rklaehn@gmail.com> | 2014-01-14 23:38:03 +0100 |
commit | b33740f0b46ea8f8f6eb5efa7ecfcf7bcb6b57cd (patch) | |
tree | 6cdea721d933f4b8b591c76ad70ca73d7563aa5b | |
parent | 24a227d23d651caa121bbe50ee3c81dfef17a337 (diff) | |
download | scala-b33740f0b46ea8f8f6eb5efa7ecfcf7bcb6b57cd.tar.gz scala-b33740f0b46ea8f8f6eb5efa7ecfcf7bcb6b57cd.tar.bz2 scala-b33740f0b46ea8f8f6eb5efa7ecfcf7bcb6b57cd.zip |
Improved documentation of HashTrieSet internals
Added some more general documentation about how levels work and how the
bitmap field encodes the position of elems.
-rw-r--r-- | src/library/scala/collection/immutable/HashSet.scala | 36 |
1 files changed, 36 insertions, 0 deletions
diff --git a/src/library/scala/collection/immutable/HashSet.scala b/src/library/scala/collection/immutable/HashSet.scala index 9ebcf72d24..384cb6631f 100644 --- a/src/library/scala/collection/immutable/HashSet.scala +++ b/src/library/scala/collection/immutable/HashSet.scala @@ -237,6 +237,42 @@ object HashSet extends ImmutableSetFactory[HashSet] { } + /** + * A branch node of the HashTrieSet with at least one and up to 32 children. + * + * @param bitmap encodes which element corresponds to which child + * @param elems the up to 32 children of this node. + * the number of children must be identical to the number of 1 bits in bitmap + * @param size0 the total number of elements. This is stored just for performance reasons. + * @tparam A the type of the elements contained in this hash set. + * + * How levels work: + * + * When looking up or adding elements, the part of the hashcode that is used to address the children array depends + * on how deep we are in the tree. This is accomplished by having a level parameter in all internal methods + * that starts at 0 and increases by 5 (32 = 2^5) every time we go deeper into the tree. + * + * hashcode (binary): 00000000000000000000000000000000 + * level=0 (depth=0) ^^^^^ + * level=5 (depth=1) ^^^^^ + * level=10 (depth=2) ^^^^^ + * ... + * + * Be careful: a non-toplevel HashTrieSet is not a self-contained set, so e.g. calling contains on it will not work! + * It relies on its depth in the Trie for which part of a hash to use to address the children, but this information + * (the level) is not stored due to storage efficiency reasons but has to be passed explicitly! + * + * How bitmap and elems correspond: + * + * A naive implementation of a HashTrieSet would always have an array of size 32 for children and leave the unused + * children empty (null). But that would be very wasteful regarding memory. Instead, only non-empty children are + * stored in elems, and the bitmap is used to encode which elem corresponds to which child bucket. The lowest 1 bit + * corresponds to the first element, the second-lowest to the second, etc. + * + * bitmap (binary): 00010000000000000000100000000000 + * elems: [a,b] + * children: ---b----------------a----------- + */ class HashTrieSet[A](private val bitmap: Int, private[collection] val elems: Array[HashSet[A]], private val size0: Int) extends HashSet[A] { assert(Integer.bitCount(bitmap) == elems.length) |