Почему initialCapacity Hashtable 11 в то время как DEFAULT_INITIAL_CAPACITY в HashMap равен 16 и требует степени 2? - PullRequest
Новая
       8

Почему initialCapacity Hashtable 11 в то время как DEFAULT_INITIAL_CAPACITY в HashMap равен 16 и требует степени 2?

29 голосов
/ 23 февраля 2012

Сравнивая исходный код 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 в качестве начальной емкости, в то время как Hashtable выбирает 11 в качестве начальной емкости по умолчанию? Я предполагаю, что это не имеет ничего общего с тем, что Hashtable является поточно-ориентированным и не допускает нулевой ключ или значения.

Ответы [ 4 ]

22 голосов
/ 23 февраля 2012

Следующая статья решает этот вопрос более подробно: HashMap требует лучшего hashCode () - JDK 1.4, часть II .

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

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

6 голосов
/ 23 февраля 2012

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

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

3 голосов
/ 23 февраля 2012

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

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

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

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

0 голосов
/ 23 февраля 2012

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

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

Сочетание этих двух деталей реализации приводит к снижению производительности.

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

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

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

...