1. Для написания хэш-функции, которая соответствует аксиоматике, вам нужно выбрать подходящий метод генерации хэша. Один из самых распространенных методов - это использование функций сжатия, таких как CRC32, MD5, SHA-1 или SHA-256. Вы также можете использовать алгоритмы хэширования, такие как MurMurHash или JenkinsHash, которые предназначены специально для хэш-таблиц.
2. При переполнении хэш-таблицы возникают коллизии, когда двум разным ключам соответствует одно и то же значение хэша. Существуют различные подходы к управлению коллизиями. Некоторые из них включают в себя:
- Открытое связывание (open addressing): при коллизии элементы помещаются в другую ячейку таблицы, пока не найдется свободная ячейка.
- Закрытое связывание (closed addressing или chaining): при коллизии элементы помещаются в список или другую структуру данных, хранящую значения с одинаковым хэшем.
- Двойное хэширование (double hashing): при коллизии используется вторая хэш-функция, чтобы определить новую позицию элемента.
После расширения таблицы никаких дополнительных действий для перезаписи элементов не требуется. Элементы остаются на своих местах, за исключением переноса элементов, которые могут быть затронуты расширением. Новая хэш-функция применяется только к новым элементам, добавляемым в расширенную таблицу.