cupper
16.05.2010, 20:02
Значит, начинается все с того что есть таблицы с прямой адресацией. Они удобно когда множество всех возможных ключей U={0,...m} невелико. Тогда таблица с ключами имеет небольшой размер m, и нестрашно что из них только пару ключей реально используются.
Если U очень охрененно большое и реально используемых ключей нетак уж много тогда будет слижком большая таблица (со всеми ключами) из которых только небольшое количество реально используемых. Плохо.
Для этого придумали хэш функции и хештаблицы. Тогда вместо значение ключа k из U можно применить хешфункцию h(k) таблицу строить именно из значений хешфункции для ключей k из U.
И вот тут у меня начинаются проблемы.
С одной стороны говорят чот хешфункция - это такая функция которая отображает множество возможных ключей U в более маленькое множестно, что позволяет делать хештаблицу мешьшего размера чем еслибы она делалась для всех ключей из U. НО тогда возникает коолизия, так как для разных ключей из U могут быть одинаковые значения зеш функции. Это решаеться путем цепочек. (не буду рассказывать кто знает поймет). И шо мы имее в итоге, таблица стала в длину меньше в толищину больше, ХРЕНЬ.
С другой стороны стремяться подобрать такую хешфункицю чтобы для каждого ключа из U было неповторяющееся значение. В этом случае мы имеем множество значений хешфункции равное множеству всех ключей из U. Хештаблица будет такаяже как и без хеширования.
В чем соль ?)
Битый час уже не могу понять плюсы хеширования.
Если U очень охрененно большое и реально используемых ключей нетак уж много тогда будет слижком большая таблица (со всеми ключами) из которых только небольшое количество реально используемых. Плохо.
Для этого придумали хэш функции и хештаблицы. Тогда вместо значение ключа k из U можно применить хешфункцию h(k) таблицу строить именно из значений хешфункции для ключей k из U.
И вот тут у меня начинаются проблемы.
С одной стороны говорят чот хешфункция - это такая функция которая отображает множество возможных ключей U в более маленькое множестно, что позволяет делать хештаблицу мешьшего размера чем еслибы она делалась для всех ключей из U. НО тогда возникает коолизия, так как для разных ключей из U могут быть одинаковые значения зеш функции. Это решаеться путем цепочек. (не буду рассказывать кто знает поймет). И шо мы имее в итоге, таблица стала в длину меньше в толищину больше, ХРЕНЬ.
С другой стороны стремяться подобрать такую хешфункицю чтобы для каждого ключа из U было неповторяющееся значение. В этом случае мы имеем множество значений хешфункции равное множеству всех ключей из U. Хештаблица будет такаяже как и без хеширования.
В чем соль ?)
Битый час уже не могу понять плюсы хеширования.