Search code examples
javascalahashmapimmutabilitytrie

Why is variable index ANDed twice with 0x1f?

I was reading about the underlying data structures for immutable collections in Scala (HashMap and Vector, more precisely) and while reading the code, I came across the get0 function in HashTrieMap.

Why is the variable index AND-ed with 0x1f again in line 312? It seems to me that the result is the same (i.e. the second AND is not necessary). What am I missing?

Here is the aforementioned function:

override def get0(key: A, hash: Int, level: Int): Option[B] = {
  val index = (hash >>> level) & 0x1f // index is AND-ed with 0x1f
  val mask = (1 << index)
  if (bitmap == - 1) {
    elems(index & 0x1f).get0(key, hash, level + 5) // once again, AND-ed with 0x1f
  } else if ((bitmap & mask) != 0) {
    val offset = Integer.bitCount(bitmap & (mask-1))
    elems(offset).get0(key, hash, level + 5)
  } else
    None
}
Solution

  • You are not missing anything. Indeed the second AND is not necessary.