Как устроены реальные хеши?

Question

[Никита Гусаков]

Я тут хеши изучал, сделал небольшую реализацию. Но мне вот стало интересно - как делается по нормальному, в stl например.
У меня фактически хеш - std::list<T> *_hash, то есть массив коллизий.
Получается либо мы должны заранее знать максимальное число, которое может вернуть хеш-функция и создать массив такой длины. Но это не эффективно по памяти и я сомневаюсь что такое используется.
Вот у меня вопрос - с помощью чего это правильно сделать?
Ни бинарные деревья, ни списки не подходят - смысл хеша, как я понимаю - чтение, поиск, удаление в среднем случае за O(n)

Comments

[Лолшто]

Вы про реализацию хеш-таблицы говорите?

[Никита Гусаков]

@Lol4t0 да, set, map

[bak]

Пара замечаний:
1) для хранения динамического массива в stl есть std::vector. Соотвественно структура будет выглядеть как std::vector > hash
2) Разберитесь с O нотацией и (или) с эффективностью хеша и остальных базовых структур данных. Чтение, поиск и удаление из хеша в среднем случае занимают постоянное время, т. е. O(1)

[jcmvbkbc]

> смысл хеша, как я понимаю - чтение, поиск, удаление в среднем случае за O(n)
за O(1) вообще-то.

[bak]

std::vector<std::list<T> > hash - в предыдущем коменте автоформат съел часть кода

[bak]

@hell0w0rd set и map - это не хеш таблицы а красно-черные деревья. unordered_set & unordered_map - хеш таблицы.

[Никита Гусаков]

@bak @jcmvbkbc насчет O(n) - описался... с O нотацией разбираюсь, просто перепутал

Answer 1

[bak]

Точно так же как и вектор. Изначально максимальный размер считается небольшим, а каждый раз при заполнении увеличивается в N раз. Для получения позиции в массиве берётся не сама хеш функция, а остаток от деления её на максимальный размер. При увеличении размера массива все элементы распределяются заново.

Answer 2

[tsarevfs]

Чуть более развенуто: http://neerc.ifmo.ru/wiki