| Цитата(Pavia @ 19.5.2010, 21:06) | esperanto,
Учись как надо.
cupper,
Вот тебе задача сделай через хэш и через таблицы тогда поймешь в чем разница.
Возьми составь таблицу всех файлов диска. Два поля первое папка второе имя файла(или его путь).
И сделай поиск файлов в заданной папки. Названия папки вводится с клавиатуры и выдаются все файлы содержащиеся в папки с таким именем.
Сделай двумя способами первый через хэш второй через таблицы.
Цитата(cupper @ 19.5.2010, 12:40  ) | | но в таблицах с прямой адресацией (аля массив) тоже O(1), |
Далеко не O(1). |
гыы  так забавно, мы уже довольно долго непонимаем друг друга, или просто я непонимаю чего мне хотят сказать %)
я прекрасно понимаю выгоду хеш функций при поиске, сравнении и прочем, КРОМЕ сокращения размера таблицы (пространства ключей).
Блин вот вы все говорите про таблицу с прямым доступом но не кто не объясняет своих утверждение, поэтому я в сотый раз переспрашиваю, чего в них не так ? ни первого (про все значения в одну ячейку) ни второго (про O(1)) я нифига не понимаю на основе чего вы так говорите.
Я чес слово заманался одну и туже мысль описывать разными словами, приведу просто теперь вырезки и книги "Алгоритмы. Построение и анализ"
по поводу массивов и O(1)
| Цитата |
Хеш-таблица представляет собой обобщение обычного массива. Возможность прямой индексации элементов обычного массива обеспечивает доступ к произвольной позиции в массиве за время O(1); она применима, если мы в состоянии выделить массив размера, достаточного для того, чтобы для каждого возможного значения ключа имелась своя ячейка.
|
теперь то что у меня вызывает вопрос
| Цитата |
Если количество реально хранящихся в массиве ключей мало по сравнению с количеством возможных значений ключей, эффективной альтернативой массива с прямой индексацией становится хеш-таблица, которая обычно использует массив с размером, пропорциональным количеству реально хранящихся в нем ключей. Вместо непосредственного использования ключа в качестве индекса массива,
индекс вычисляется по значению ключа.
|
| Цитата |
Когда множество К хранящихся в словаре ключей гораздо меньше пространства возможных ключей U, хеш-таблица требует существенно меньше места, чем таблица с прямой адресацией. Точнее говоря, требования к памяти могут быть снижены до O(|K|), при этом время поиска элемента в хеш-таблице остается равным O(1). Надо только заметить, что это граница среднего времени поиска, в то время как в случае таблицы с прямой адресацией эта граница справедлива для наихудшего случая.
В случае прямой адресации элемент с ключом к хранится в ячейке к. При хешировании этот элемент хранится в ячейке h (к), т.е. мы используем хеш-функцию h для вычисления ячейки для данного ключа k. Функция h отображает пространство ключей U на ячейки хеш-таблицы Т [0..m — 1]:
|
| Цитата |
хеширования. Цель хеш-функции состоит в том, чтобы уменьшить рабочий диапазон индексов массива, и вместо |U| значений мы можем обойтись всего лишь m значениями. Соответственно снижаются и требования к количеству памяти.
|
| Цитата |
Однако здесь есть одна проблема: два ключа могут быть хешированы в одну и ту же ячейку. Такая ситуация называется коллизией.
|
| Цитата |
Само собой разумеется, функция h должна быть детерминистической и для одного и того же значения к всегда давать одно и то же хеш-значение h (к). Однако поскольку |U| > m, должно существовать как минимум два ключа, которые имеют одинаковое хеш-значение. Таким образом, полностью избежать коллизий невозможно в принципе, и хорошая хеш-функция в состоянии только минимизировать количество коллизий. Таким образом, нам
крайне необходим метод разрешения возникающих коллизий.
|
Хм... вот из данной подборки ключевых моментов я теперь четко осознаю что выгода хеширования для уменьшения U достигается непосредственно только за счет коллизий. Это в принципе и есть то с чего я начал эту тему. Только я думал что я неправильно понял этот момент, оказывается правильно |