Книга: Хакни рутину. Как алгоритмы помогают справляться с беспорядком, не тупить в супермаркете и жить проще

Бум-бум-бум, делай это часто и пожалеешь, как герой книги Мураками

закрыть рекламу

Бум-бум-бум, делай это часто и пожалеешь, как герой книги Мураками

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

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

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


Оглавление книги

Реклама
· Аллергии · Холестерин · Глаза, Зрение · Депрессия · Мужское Здоровье
· Артрит · Диета, Похудение · Головная боль · Печень · Женское Здоровье
· Диабет · Простуда и Грипп · Сердце · Язва · Менопауза

Генерация: 1.023. Запросов К БД/Cache: 3 / 1
Меню Вверх Вниз