Здравствуйте, Sharowarsheg, Вы писали:

S>Здравствуйте, Serginio1, Вы писали:

S>>>>и доступ через GetHashCode() % 16. У тебя конкуренция в среднем должна уменьшиться в 16 раз, а значит и скорость

S>>>Нужно не забывать, что вместо гигабайта хешмепов у тебя получается шестнадцать гигабайтов хешмепов.
S>> Почему? Данные распределятся по 16 хэшмапам.
S>>Внутри то хэшмапа GetHashCode() % SizeHashMap на связный список коллизий

S>Не совсем. Часть элементов таблицы обычно пустая, если ты хочешь O(1), чтобы списки коллизий не слишком росли. Поэтому на практике, если таблицы достаточно большие, оказывается, что каждая из них не уменьшается в 16 раз, а становится несколько более разреженной. Хотя, может быть, это свойство конкретного дотнетовского Dictionary. Там это заметно даже если не забыть сдвинуть хеши на 4 бита вправо.

Ну общее количество записей будет таким же и среднее наполнение тоже. Обычно это около 75%. При полном заполнении ищется простое число в 2 раза большее чем текущий размер.
Конечно если ты им не задашь начальный размер в миллионы записей. А так будет то же, что и при одной хэш таблице.

В дотнете словарь состоит их 2 таблиц. Вторая представляет собой связный список на массиве, а первая содержит индекс начала связного списка.

Здравствуйте, Sharowarsheg, Вы писали:

S>Здравствуйте, Serginio1, Вы писали:

S>>>>и доступ через GetHashCode() % 16. У тебя конкуренция в среднем должна уменьшиться в 16 раз, а значит и скорость

S>>>Нужно не забывать, что вместо гигабайта хешмепов у тебя получается шестнадцать гигабайтов хешмепов.
S>> Почему? Данные распределятся по 16 хэшмапам.
S>>Внутри то хэшмапа GetHashCode() % SizeHashMap на связный список коллизий

S>Не совсем. Часть элементов таблицы обычно пустая, если ты хочешь O(1), чтобы списки коллизий не слишком росли. Поэтому на практике, если таблицы достаточно большие, оказывается, что каждая из них не уменьшается в 16 раз, а становится несколько более разреженной. Хотя, может быть, это свойство конкретного дотнетовского Dictionary. Там это заметно даже если не забыть сдвинуть хеши на 4 бита вправо.

Ну общее количество записей будет таким же и среднее наполнение тоже. Обычно это около 75%. При полном заполнении ищется простое число в 2 раза большее чем текущий размер.
Конечно если ты им не задашь начальный размер в миллионы записей. А так будет то же, что и при одной хэш таблице.

В дотнете словарь состоит их 2 таблиц. Вторая представляет собой связный список на массиве, а первая содержит индекс начала связного списка.

Вообзе похож на мой http://rsdn.org/forum/alg/437992.1

Автор: Serginio1
Дата: 10.11.03

но сделан на однй таблице