Почему HashMaps реализованы с использованием полномочий двух?

Question

У меня вопрос, почему размер корзины в hashmap равен степени 2, и я прошел через множество ответов по stackoverflow, но я все еще не убежден.Причины:

1. Я читал, что наличие емкости как степени 2 делает & работу более эффективной для вычисления индекса, поэтому мой вопрос, как именно это полезно здесь.У меня может быть размер, который может быть степенью 3, я все еще могу выполнять & операции как это (хэш) & (length-1), так почему именно это должно быть степенью 2?

2. Также, если емкость не является степенью 2, зачем мне делать оставшуюся операцию?

Answer 1

Я могу думать о двух причинах:

1. Полномочия двух упрощают анализ сложности времени, потому что когда речь идет о вычислениях, log обычно принимается за основу 2. (Обратите внимание, чтов действительности можно показать, что все log временные сложности эквивалентны независимо от базы, но это упрощает рассуждения о сложности, если вы используете степени 2, потому что все ваши термины умножаются и делятся на 2)

2. Сила двух прекрасно сочетается с оборудованием.Удвоение числа в памяти требует меньше операций, чем умножение его на три.Точно так же все части памяти имеют размеры в степени двух, поэтому если вы всегда удваиваете, вы всегда можете занимать 2 ^ n full байт.

Answer 2

Когда вы вычитаете 1 из числа, которое является степенью 2, вы получаете число, двоичное представление которого равно 1. Например, 16 является степенью 2. Если вы вычтите 1 из этого числа, вы получите 15, чьедвоичное представление равно 1111. Теперь, если вы сделаете побитовое И для любого числа с 1111, вы получите последние 4 бита числа, которые, другими словами, эквивалентны модулю числа на 16 (делениеоперация обычно является дорогостоящей операцией, поэтому побитовая операция обычно предпочтительнее деления).Эти последние 4 бита будут соответствовать любому числу от 0 до 15, которое является индексами вашего базового массива.

Вместо этого вы можете сделать размер 17.В этом случае, вычтя из него 1, вы получите 16, что составляет 10000 в двоичном виде.Теперь вы сделаете немного И с числом с 16, вы потеряете все биты числа, кроме 5-го бита с конца.Таким образом, независимо от того, какое число вы берете, индекс массива будет 16 или 0. Это означает, что у вас будет много коллизий, что, в свою очередь, означает низкую производительность.Вместо O (1) для извлечения вам понадобится O (log n), потому что когда происходит столкновение, все узлы в данном сегменте будут храниться в красном черном дереве.Не только это.Если вы используете ConcurrentHashMap в многопоточном окружении, у вас будет много синхронизаций, потому что все новые добавления будут заканчиваться очень небольшим количеством блоков (только два - 0 и 16 в приведенном выше случае) иКогда вы добавляете новые узлы в корзину, в которой уже есть другие узлы, корзина блокируется, чтобы избежать несоответствия данных из-за изменений, внесенных несколькими потоками.Поэтому другим потокам, пытающимся добавить новые узлы, нужно дождаться, пока текущий поток снимет блокировку.

Наконец, я должен также упомянуть, что реализация Java HashMap также сдвигает 16 бит хеш-кода ключа вправильно и делает побитовое XOR с исходным хеш-кодом перед выполнением побитового И с (length - 1), чтобы гарантировать, что эффект битов более высокого порядка также будет захвачен.

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

Answer 3

Независимо от того, что вам нужно сделать операцию остатка, чтобы получить хеш-код (который может быть любым int) для сопоставления с записью в хеш-таблице.

В случае, когда m является степенью двойки - и только , в этом случае - a % m равно a & (m - 1).Нет другого случая, в котором остатки могут быть вычислены с &.