Improved documentation of HashTrieSet internals

Added some more general documentation about how levels work and how the
bitmap field encodes the position of elems.

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)