Бум-бум-бум, делай это часто и пожалеешь, как герой книги Мураками
В главе 1 мы говорили о хеш-таблицах и о том, как они полезны, когда нам нужно провести быстрый обзор и не беспокоиться о порядке. Разговор о многомерных массивах дает нам прекрасную возможность расширить наше знание о хеш-таблицах. Раньше мы принимали на веру, что хеш-функция всегда отмечает позицию элемента, назначая ему уникальное местоположение в хеш-таблице, и именно благодаря этому гарантируется его быстрое нахождение в любое время. В реальности хеш-функция может столкнуться с таким явлением, как коллизия, при которой соответствующее место в хеш-таблице уже занято другим элементом. Это происходит либо потому, что хеш-функция неидеальна, то есть не работает правильно и не обеспечивает единообразного распределения значений хеш-функции, либо у нас больше элементов для хранения, чем может вместить таблица. Степень заполнения хеш-таблицы называется коэффициентом заполнения и равна нулю, когда хеш-таблица пуста, или единице, когда она заполнена.
В таких случаях есть несколько способов разрешения коллизии. Один из них известен под названием метод цепочек. Во время создания цепочки возникает не хеш-таблица элементов, а хеш-таблица группы элементов. Таким образом, когда происходит коллизия, соответствующий пункт перемещается в конец группы и поэтому не происходит непреднамеренной перезаписи данных.
Итак, у нас есть хеш-таблица, которая представляет собой группу групп элементов. Когда наша хеш-функция находит место, в котором имеется множество элементов, нам приходится перебрать их все, пока не найдется искомый. Этот процесс, конечно, полностью прозрачен для пользователя.
