Пособие по практике программирования
Хорошо ли она перемешивает короткие
Хорошо ли она перемешивает короткие строки? Длинные строки? Строки одинаковой длины с небольшими изменениями?
Хэшировать можно не только строки. Можно "смешать" три координаты частицы при физическом моделировании, тем самым уменьшив размер хранилища до линейной таблицы (0(количество точек)) вместо трехмерного массива (0(размер_по_х хразмер_nojj X размер_no_z)).
Один примечательный случай использования хэширования — программа Джерарда Холзманна (Gerard Holzmann) для анализа протоколов и параллельных систем Supertrace. Supertrace берет полную информацию о каждом возможном состоянии наблюдаемой системы и хэширует эту информацию для получения адреса единственного бита в памяти. Если этот бит установлен, то данное состояние наблюдалось и раньше; если нет, то не наблюдалось. В Supertrace используется хэш-таблица длиной во много мегабайт, однако в каждой ячейке хранится только один бит. Цепочки не строятся; если два разных состояния совпали по своей хэш-функции, то программа этого не заметит. Supertrace рассчитана на то, что вероятность коллизии мала (она не обязана быть нулем, поскольку Supertrace использует вероятностные, а не детерминированные вычисления). Поэтому хэш-функция здесь очень аккуратна; она использует циклический избыточный код (cyclic redundancy check — CRC) — функцию, которая тщательно перемешивает данные.
Хэш-таблицы незаменимы для символьных таблиц, поскольку они предоставляют (почти всегда) доступ к каждому элементу за константное время. У них есть свои ограничения. Если хэш-функция плоха или размер массива слишком мал, то списки могут стать достаточно длинными. Поскольку списки не отсортированы, это приведет к линейному доступу (0(и)). Элементы нельзя напрямую получить в отсортированном виде, однако их легко подсчитать, выделить память под массив, заполнить его указателями на элементы и отсортировать их. Что и говорить, константное время операций поиска, вставка и удаление — это такое свойство хэш-таблицы, которого не достичь никакими другими технологиями.
