Значит, начинается все с того что есть таблицы с прямой адресацией. Они удобно когда множество всех возможных ключей U={0,...m} невелико. Тогда таблица с ключами имеет небольшой размер m, и нестрашно что из них только пару ключей реально используются.
Если U очень охрененно большое и реально используемых ключей нетак уж много тогда будет слижком большая таблица (со всеми ключами) из которых только небольшое количество реально используемых. Плохо.
Для этого придумали хэш функции и хештаблицы. Тогда вместо значение ключа k из U можно применить хешфункцию h(k) таблицу строить именно из значений хешфункции для ключей k из U. 
И вот тут у меня начинаются проблемы. 

С одной стороны говорят чот хешфункция - это такая функция которая отображает множество возможных ключей U в более маленькое множестно, что позволяет делать хештаблицу мешьшего размера чем еслибы она делалась для всех ключей из U. НО тогда возникает коолизия, так как для разных ключей из U могут быть одинаковые значения зеш функции. Это решаеться путем цепочек. (не буду рассказывать кто знает поймет). И шо мы имее в итоге, таблица стала в длину меньше в толищину больше, ХРЕНЬ.

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

В чем соль ?)
Битый час уже не могу понять плюсы хеширования.

или я все неправильно понимаю ?

Все не правильно. Ключ это почти синоним хэша. Хотя разница в этих понятиях большая.

Хэш придуман для уменьшения времени сравнения.

Есть у нас набор данных. Некоторый record ... end. Пусть это строки.

Что бы сравнить s1 и s2 нам надо пройтись по всем байтам этих строк.
Тогда как хэш это некоторое число которое заведомо меньше, и фактически сравнение занимает гораздо меньше времени.

Второй плюс хэша это хэш таблицы. Скорость выборки составляет O(1)

Для того что бы найти точную нужную запись в таблице мы можем либо перебирать все записи(число сравнений O(n)) либо использовать бинарный поиск (число сравнений O(log(n)) ).
 

я как раз только про хештаблици и спрашивал. И в своей мессаге выразил свое не понимаие этого O(1) (хотя это вроде понятно, тут все обстоит также как и в случае с массивами только вместо индекса используется хеш значение) и какого либо качественного отличия его от просто таблицы с прямой адресацией (а вот это как раз не могу понять)

Не очень понятно, что Вам не понятно.

Всреднем хеш дает О(1), худшего случая для хорошего хеша нет.

А для массива есть худший случай

то что O(1) это понятно, но в таблицах с прямой адресацией (аля массив) тоже O(1), я в первом посте пытался свести к тому что массивы это невыгодно когда из большого множества ключей U реально используется маленькое количество, тогда память занимаемая таблицей расходуется в пустую. А хешфункции позволяют отобразить это самое большое множество U на более компактное M которое меньше чем U, но тут позникают коллизии, но стремять их убрать, но тогда M будет равно U, я в этом немогу разобраться.

PS. что за худший случай для массива ?

Это сообщение отредактировал(а) cupper - 19.5.2010, 12:44

Худший случай для массива известен, послать все числа в одну ячейку.

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

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

esperanto, 
Учись как надо.
cupper, 
Вот тебе задача сделай через хэш и через таблицы тогда поймешь в чем разница.
Возьми составь таблицу всех файлов диска.  Два поля первое папка второе имя файла(или его путь).
И сделай поиск файлов в заданной папки.  Названия папки вводится с клавиатуры и выдаются все файлы содержащиеся в папки с таким именем.
Сделай двумя способами первый через хэш второй через таблицы.



Далеко не O(1).

гыы  так забавно, мы уже довольно долго непонимаем друг друга, или просто я непонимаю чего мне хотят сказать %) 

я прекрасно понимаю выгоду хеш функций при поиске, сравнении и прочем, КРОМЕ сокращения размера таблицы (пространства ключей).

Блин вот вы все говорите про таблицу с прямым доступом но не кто не объясняет своих утверждение, поэтому я в сотый раз переспрашиваю, чего в них не так ? ни первого (про все значения в одну ячейку) ни второго (про O(1)) я нифига не понимаю на основе чего вы так говорите. 

Я чес слово заманался одну и туже мысль описывать разными словами, приведу просто теперь вырезки и книги "Алгоритмы. Построение и анализ"
по поводу массивов и O(1)

теперь то что у меня вызывает вопрос





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

Коллизии - побочный эффект.

Если я правильно понял вашу проблему...

Имеет около 4 миллиардов целых 4-байтных чисел. Для прямого доступа надо массив в 16 гигабайт.

Но если вы будете использовать, скажем, только 4 тысячи чисел - то зачем вам тягать в миллион раз большую память? Если у вас найдется такая ИДЕАЛЬНАЯ функция, которая на каждое число из ваших 4000 возвращает свое, не совпадающее с другими значение, скажем, от 1 до 5000 - вот вам уже и хватит памяти в 5000 чисел. Другое дело, что найти такую идеальную функцию крайне сложно (вернее, зная числа заранее, несложно, но вот чтоб она еще и быстро работала - это уже проблема...), и потому идут на то, что какая-то часть разных чисел будет получать одинаковые значения, т.е. будут коллизии.

Просто обычно их мало, и влияние на скорость работы они оказывают небольшое.

Так что коллизии - это не более чем компромисс между скоростью и памятью  Теоретически функция без коллизий для заранее известного множества значений строится мгновенно, только вот время ее вычисления O(n) 

Это сообщение отредактировал(а) disputant - 2.11.2013, 12:03

прочитайте еще раз: доступ к произвольной позиции. это совсем не то, что доступ по ключу (который в неотсортированном массиве выполняется за O(n) ). а доступ к хэш таблице "по позиции" и вовсе лишен смысла.
так что тут не совсем то обобщение)))