|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Andrey Tarasevich 2:5020/400 08 Dec 2001 00:59:50 To : Arthur Vartanov Subject : Re: Гоpодская олимпиада по инфоpматике -------------------------------------------------------------------------------- From: Andrey Tarasevich <atarasevich@telocity.com> Arthur Vartanov wrote: > > >> ... > >> файлов. А если в файле с десяток тысяч строк? Поэтому делаем так: по > >> более длинному файлу строим хеш-таблицу, упорядочиваем ее по > >> возрастанию/убыванию хэша и делаем бинарный поиск, используя хеши > >> строк второго файла. > >> Естественно, учитываем коллизии. > >> ... > > AT> Так все таки 'хэш-таблица' или 'бинарный поиск' ? Если > AT> соответствующая данному ключу позиция в таблице ищется при помощи > AT> бинарного поиска, то к хэш-таблицам и хэшированию в целом все это > AT> никак не относится. > > А что по-твоему здесь есть ключ? Ключ и есть значение хеш-функции от строки. > Так что все-таки относится :) > ... Hет. Ключ - это то, что идет на _вход_ xэш-функции, а результатом хэш-функции является точка входа в хэш-таблицу. В идеальном случае в этой точке и будет располагаться искомый элемент. В неидеальном - модет быть придется его еще немножко поискать (локально, как правило). Hо о безусловном глобальном поиске ключа во всей таблице речи не идет. Иначе это будет уже не хэширование. В том то вся идея хэш-таблицы и заключается, чтобы избежать поиска вообще или по крайней мере сделать его как можно более локальным. Ключом в данном случае является сама строка. Hа основе данной строки хэш-функция должна вычислить точку входа в хэш-таблицу. Вот это будет хэшированием. Если тебе хочется сначала превратить строку в некоторый промежуточный ключ и вычислять хеш-функцию уже от него - пожалуйста. Это будет просто неприниципиальной деталью реализации хэш-функции. А принципиальной деталью является именно то, что если ты хочешь называть это хэшированием, то никакого безусловного глобального поиска ключа быть не должно. Поиск в хешировании применяется только тогда, когда надо найти в таблице конкретный ключ среди нескольких ключей, для которых произошла коллизия. Повторяю, вся идея хеширования заключается в том, чтобы _избежать_ любого поиска. Best regards, Андрей. --- ifmail v.2.15dev5 * Origin: good enough (2:5020/400) Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/6682686af99e.html, оценка из 5, голосов 10
|