|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Arthur Vartanov 2:5020/400 09 Dec 2001 01:29:06 To : Andrey Tarasevich Subject : Re: Гоpодская олимпиада по инфоpматике -------------------------------------------------------------------------------- Hello, Andrey! You wrote to Arthur Vartanov on Fri, 7 Dec 2001 20:59:50 +0000 (UTC): AT>>> Так все таки 'хэш-таблица' или 'бинарный поиск' ? Если AT>>> соответствующая данному ключу позиция в таблице ищется при помощи AT>>> бинарного поиска, то к хэш-таблицам и хэшированию в целом все это AT>>> никак не относится. >> А что по-твоему здесь есть ключ? Ключ и есть значение хеш-функции от >> строки. >> Так что все-таки относится :) >> ... AT> Hет. Ключ - это то, что идет на _вход_ xэш-функции, а результатом AT> хэш-функции является точка входа в хэш-таблицу. В идеальном случае в AT> этой точке и будет располагаться искомый элемент. В неидеальном - AT> модет быть придется его еще немножко поискать (локально, как AT> правило). Hо о безусловном глобальном поиске ключа во всей таблице AT> речи не идет. Иначе это будет уже не хэширование. В том то вся идея AT> хэш-таблицы и заключается, чтобы избежать поиска вообще или по AT> крайней мере сделать его как можно более локальным. Опс.. В первом письме вышла ошибочка. Когда написал "хеш-таблица" имел ввиду таблицу пар <некая функция строки, строка>. Торопился :) А идея хеширования мне известна. Просто данная задача была решена мной именно простроением таблицы пар. Отсюда и бинарный поиск. AT> Ключом в данном случае является сама строка. Hа основе данной строки AT> хэш-функция должна вычислить точку входа в хэш-таблицу. Вот это AT> будет хэшированием. Хеш функцию следует понимать шире. Это необязательно "точка входа в таблицу". Это всего лишь отображение элементов из множества большей мощности на множество меньшей мощности. Пример типичных хеш-функций - CRC32 или MD5. Или sign(x) :) Sincerely, Arthur (arvar@penza.net) --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/3951afa291c9.html, оценка из 5, голосов 10
|