В чем разница между использованием операторов & vs MOD при расчете индексов (реализация хэш-таблицы)?

Question

Для реализации общей хеш-таблицы:

• Вычислить хэш ключа, hash(key)=hashcode

• Сопоставить хеш-код с таблицей /массив.hashcode % array_length = index

• как только мы получим индекс, мы добавим узел (ключ, значение, обновить следующий указатель) в связанный список с этим индексом.

Итак, вопрос в том, в чем разница между:

def _get_index(self, key):

   # compute the hashcode
   hash_code = hash(key)
   array_index = hash_code & 15  # FIXME : why?
   return array_index

и

 array_index = hash_code % 15

Например: для INPUT:

hm =MyHashMap()
hm.put("1", "sachin")
hm.put("2", "sehwag")
hm.put("3", "ganguly")
print(hm.get("1"))
print(hm.get("2"))
print(hm.get("3"))

ВЫХОД:

sachin
sehwag
ganguly

оператор '&' вместо '%', что для меня не имеет смысла?потому что он не всегда работает как оператор% при вычислении индекса, но я видел разработчика, использующего & в некоторых реализациях Hashtable

Любое предложение?

Answer 1

array_index = hash_code & 15

эквивалентно (положительным значениям):

array_index = hash_code % 16

работает только в том случае, когда все значащие биты числа равны единице (то есть, когда число имеет форму 2**n - 1).

И то, и другое удаляет наибольшую часть числовых битов.

Битовая маскировка выполняется намного быстрее, чем деление.Поэтому он используется, когда это возможно, для ускорения вычислений.Каждый раз, когда вы видите:

b = a % modulo

с a > 0 и modulo - это степень 2 (modulo == 2**n), вы можете написать:

b = a & (modulo-1)

.Если модуль не является степенью 2, то это невозможно сделать таким образом (и оптимизаторы скомпилированных языков часто заменяют степень 2 по модулю или делению / умножению на более быструю операцию маскирования / сдвига битов)