Размер ключа словаря / hash_map

Question

Хеш-значение для ключа рассчитывается и делится на простое число. В общем, есть ли для этого стандартное простое число (скажем, для 32/64 бита)?

Насколько я понимаю, хеш-таблица не имеет изменяемого размера / настраивается, и от этого зависит ее внутренний массив. Если у меня есть хеш-таблица только для 5 элементов, будут ли пустые места в ключевом пространстве?

Редактировать: я должен был сформулировать это лучше. Какой общий подход используется в c ++ hash_map (boost) или C # Dictionary

Answer 1

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

Answer 2

Почему бы не использовать Reflector для просмотра реализаций C # Dictionary или HashTable?Оба ответа Грега и Джима верны в общих чертах и ​​для реализации на C #.

Итак, реализация C # Dictionary использует простое число (которое больше его емкости) в качестве размера внутреннего массива сегментов и использует его для разделения хеш-кода.Всякий раз, когда необходимо изменить размер внутреннего массива, он использует вдвое большую емкость, чем новую емкость.

Answer 3

Часто простое число используется в качестве размера внутреннего массива. То есть, если кто-то запрашивает хэш-таблицу из 100 элементов, вы выбираете следующее простое число, которое> = 100, и это размер. В этом случае у вас будет размер таблицы 101.

Но это не единственный способ сделать это.