Почему initialCapacity Hashtable равно 11, а DEFAULT_INITIAL_CAPACITY в HashMap - 16 и требует мощности 2

Сравнение исходного кода HashMap и Hashtable в jdk 1.6, я видел ниже коды внутри HashMap

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 16;

    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;

однако, в Hashtable, я видел ниже коды?

table = new Entry[initialCapacity];

public Hashtable() {
    this(11, 0.75f);
}

поэтому мой вопрос: почему hashMap требует мощности 2 в качестве начальной емкости? и в то время как хэш-таблица выбирает 11 как начальную емкость по умолчанию? Я предполагаю, что это не имеет ничего общего с тем, что хеш-таблица является потокобезопасной и не допускает нулевой ключ или значения.

ТНХ.

Ответы

Ответ 1

В следующей статье мы подробно рассмотрим этот вопрос: HashMap требует лучшего hashCode() - JDK 1.4 Part II.

В соответствии с этой статьей основной причиной перехода к силе двух размеров было то, что бит-маскирование быстрее, чем целочисленное деление. Это не лишено негативных последствий, которые объясняются одним из авторов:

Джошуа Блох: Недостатком использования силы-двух является то, что результирующая хеш-таблица очень чувствительный к качеству хэш-функции (hashCode). Крайне важно, чтобы любое изменение входа должно влиять на младшие биты хеш-значения. (В идеале, он должен влиять на все биты хеш-значения с равным вероятностью.) Поскольку мы не имеем уверенности, что это правда, мы добавляем вторичную (или "защитную" ) хеш-функцию, когда мы переключаемся на power-of-two хеш-таблица. Эта хеш-функция применяется к результатам hashCode перед маскировкой бит младшего порядка. Его задача состоит в том, чтобы разбросать информацию по всем битам и, в частности, в биты младшего порядка. Конечно, он должен работать очень быстро, или вы теряете преимущество перехода на таблицу с двумя размерами. Исходная вторичная хеш-функция в 1.4 оказалась недостаточной. Мы знали, что это теоретическая возможность, но мы думали, что это не повлияло на какие-либо практические наборы данных. Мы были неправы. Вторичная вторичная хэш-функция (которую я разработал с помощью компьютера) имеет сильные статистические свойства, которые в значительной степени гарантируют хорошее распределение ковша.

Ответ 2

Hashtable использует размеры таблицы псевдопростых чисел и увеличивает размер таблицы относительно медленнее. HashMap использует мощность 2 в качестве бит и быстрее, чем использование модуля.

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

Ответ 3

Это может помочь:

http://www.concentric.net/~Ttwang/tech/primehash.htm

В основном, если я правильно помню, когда у вас есть хеш-таблица с размером, равным 2, легко получить хеш-функцию на основе менее значимых бит ключа.

Используя простое число (как в 11) в качестве размера таблицы, вероятность столкновения на строках таблицы менее вероятна, поэтому вставка "дешевле".

Ответ 4

Требование о том, чтобы размер таблицы был равен двум, представляет собой деталь реализации, не известную пользователям класса, поэтому c'tor автоматически корректирует значение следующей большей мощности двух вместо пометить ошибку.

В реализации Hashtable предполагается, что хэш не может быть равномерно распределен, поэтому он пытается использовать несколько ящиков, которые являются первичными в надежде избежать пиков в распределении частот хеша.

Комбинация этих двух деталей реализации приводит к плохой производительности.

(например, примитивная хэш-функция будет

int hash(String s, int nBins) {
    return s[0] % nBins;
}

Если nBins равно 32, e и e заканчиваются в одном и том же ящике, поэтому распределение хеш-значений коррелирует с распределением появления букв с четкими пиками - поэтому распределение частот будет иметь пик при 32.)