Этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
Политика конфиденциальности
|
|
|
Q: "многомерное хеширование"
|
|||
|---|---|---|---|
|
#18+
Кто-нибудь может растолкоавать чайнику subj? В частности, - что означает "соединяются в цепочку" в Многомерное хеширование Схема многомерного хеширования (метод цепочек, Ф. Уильямс, 1959) довольно проста: в случае возникновения коллизий после вычисления хеш-функции ключи с одним хеш-адресом соединяются в цепочку. ...( Расстановка, или Схемы хеширования Руслан Богатырев, Андрей Шилов 15.06.2001 )? Как это, вообще, РЕАЛИЗУЕТСЯ в коде? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.09.2004, 10:01 |
|
||
|
Q: "многомерное хеширование"
|
|||
|---|---|---|---|
|
#18+
Ну ты даешь, там же ведь картинка есть на которой все понятно :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.09.2004, 11:48 |
|
||
|
Q: "многомерное хеширование"
|
|||
|---|---|---|---|
|
#18+
У меня есть задачка - каждой строке давать УНИКАЛЬНЫЙ код - число типа Long. То есть - у меня хэш-функция h1() преобразует строку в Long ... h1("abra")=12345 - ок, принято, запомнено, используется. h1("kadabra") тоже оказалось =12345 ... коллизия, паанымаэшь! Как я должен определять УНИКАЛЬНЫЙ код для строки "kadabra" - в соответствии с распрекрасным методом "многомерного хеширования"? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.09.2004, 12:50 |
|
||
|
Q: "многомерное хеширование"
|
|||
|---|---|---|---|
|
#18+
Ты получил свой хеш код(12345), допустим это номер строки в хеш таблице, куда ты записываешь свои данные, так вот, все строки у которых хеш код равен 12345 должны записаться в одну и ту же строку. Хеш табица может представлять из себя обычный массив указателей, и каждый указатель указывает на связанный список и если происходит коллизия, то ты всего навсеог в этот связанный список добавляешь ешо один элемент. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.09.2004, 13:49 |
|
||
|
Q: "многомерное хеширование"
|
|||
|---|---|---|---|
|
#18+
авторКак я должен определять УНИКАЛЬНЫЙ код для строки "kadabra" - в соответствии с распрекрасным методом "многомерного хеширования"? Метод "многомерного хеширования" нужен для того, чтобы хранить данные у которых могут быть одинаковые хеш кода, а проблема связанная с тем, чтобы создать хеш функцию, которая выдавала бы уникалный код для любых объектов, это уже совсем другая степь..... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.09.2004, 13:53 |
|
||
|
Q: "многомерное хеширование"
|
|||
|---|---|---|---|
|
#18+
Вообще-то хещирование изначально основано на том, что множество допустимых значений ключа отображается на гораздо менее мощное множество последовательных целых чисел от 0 до N. Так что там изначально не может быть никакой уникальности . Т.е. хеш-функция не может (не должна, если хотите) выдавать уникальные значения для всех возможных ключей. То есть коллизии неизбежны, если говорить по-другому. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.09.2004, 20:24 |
|
||
|
Q: "многомерное хеширование"
|
|||
|---|---|---|---|
|
#18+
Иван FXS Кто-нибудь может растолкоавать чайнику subj? В частности, - что означает "соединяются в цепочку" в Как это, вообще, РЕАЛИЗУЕТСЯ в коде? А, кажется понял, чего ты не понимаешь. Дело в том, что есть хеш-функция, и собственно сам процесс работы с хэш-таблицей. Хэш-функция просто вычисляет для каждого ключа его хэш-код. Это просто какая-то свертка ключа, как-то реализованная. Далее, есть (должны быть в программе) процедуры работы с хэш-таблицей. Это обычно две процедуры - поиск, который выдает нужную запись из таблицы по ее ключу, и добавление , которое добавляет новую запись с известным ключем. Процедуры работы с хэш-таблицей используют хэш-функцию для реализации поиска и добавления. Т.е. в самой хэш-функции никаких "цепочек соединяться" не будет. Да, и если тебе действительно нужно "каждой строке давать УНИКАЛЬНЫЙ код - число типа Long", то хэш-функции тебе не подходят однозначно, как я уже сказал, они в рпинципе дают НЕУНИКАЛЬНЫЕ коды. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.09.2004, 20:32 |
|
||
|
Q: "многомерное хеширование"
|
|||
|---|---|---|---|
|
#18+
Голова, ноги ... хвост!!! ;-) (В смылсе - ближе к практической плоскости.) "... хеш-функция, и собственно сам процесс работы с хэш-таблицей ..." - это я понимаю. Давайте тогда введем еще одно понятие - хеш-алгоритм (и, далее, реализующий его программный код) ... ПРАКТИЧЕСКАЯ задача состоит в том, чтобы кодировать РЕАЛЬНЫЕ строки числами. Множество строк ПОТЕНЦИАЛЬНО мощнее множества 32-битных чисел, но ПРАКТИЧЕСКИ этих чисел достаточно для любых (моих?) реальных задач. Если же окажется недостаточно - перейду на 40- (48-? 56-? 64-битные - как грится: ха-ха, всего-то!) Таким образом, ЯДРО хеш-алгоритма - это процедуры (желательно - как можно более эффективные!) РАЗРЕШЕНИЯ КОЛЛИЗИЙ ... Путь к эффективности: как можно больше использовать ВЫЧИСЛИТЕЛЬНЫЕ процедуры и как можно меньше - поиск и проверки по словарю (той самой хеш-таблице) ... А дальше - возникает такая тема: существует (и можно придумать) МНОГО РАЗНЫХ хеш-алгоритмов ... Наверное, они по разному эффективны В КОНКРЕТНОЙ ЗАДАЧЕ, для которой готовится "система кодирования строк" ... Как понять, какие ТИПЫ хеш-алгоритмов более подходят для тех или иных ТИПОВ задач? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.09.2004, 12:57 |
|
||
|
Q: "многомерное хеширование"
|
|||
|---|---|---|---|
|
#18+
Когда создается хеш-таблица, она конструируется с уже заранее известным количеством ключей. Рекомендуется чтобы количество ключей деленное на количество элементов было-бы меньше 0.75. При этом хеш-таблица сохраняет свои свойства. Если количество элементов (длина цепочки) будет расти то хеш-таблица потеряет свои свойства и время поиска будет линейно зависеть от количества элементов. Пойдут коллизии. Не понимаю, почему тебя волнует разрядность хеш-ключа. Это когда ты сможешь исчерпать 4 млрд. значений (для стандартной хеш-функции)? Для того чтобы строка отображалась к ключ с равномерным распределением вероятностей есть специальные функции, основаные на вычислении остатка от деления и умножения на специальные константы типа "золотое сечение". Здесь не стоит изобретать велосипед. Штатные функции достаточно хороши. Есть более навороченые структуры данных типа Б-Дерево. Тоже можно использовать для быстрых поисковых операций. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.09.2004, 15:14 |
|
||
|
Q: "многомерное хеширование"
|
|||
|---|---|---|---|
|
#18+
Спасибо, все что Вы написали, - я более менее понимаю ... Можно считать, что про "многомерное хеширование" я понял. О задаче, для которой мне все это надо, - я написал в соседнем постере ( Индекс , он же - хранилище (строк) ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 27.09.2004, 10:15 |
|
||
|
Q: "многомерное хеширование"
|
|||
|---|---|---|---|
|
#18+
Иван FXS А дальше - возникает такая тема: существует (и можно придумать) МНОГО РАЗНЫХ хеш-алгоритмов ... Наверное, они по разному эффективны В КОНКРЕТНОЙ ЗАДАЧЕ, для которой готовится "система кодирования строк" ... Как понять, какие ТИПЫ хеш-алгоритмов более подходят для тех или иных ТИПОВ задач? Существует много алгоритмов обработки переполнения (или коллизий, это одно и то же), также существует много способов вычисления хэш-функции. Какие подходять конкретно тебе - чаще всего нужно просто подгонять. Берешь делаешь генератор тестовых ключей и проверяешь на нем свою хэш-функцию, чтобы распределение хэшей было бы равномерным (при равномерном или даже неравномерном распределении ключей). Это все - сплошная теория вероятности, там все надо конкретно прощупывать. Написал бы совсем конкретно, какая задача перед тобой стоит. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 27.09.2004, 10:21 |
|
||
|
Q: "многомерное хеширование"
|
|||
|---|---|---|---|
|
#18+
MasterZivНаписал бы совсем конкретно, какая задача перед тобой стоит. - у-упс ... так я же написал, - только что дал ссылку на "соседнюю ветку"! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 27.09.2004, 10:50 |
|
||
|
|
start [/forum/topic.php?fid=16&msg=32712255&tid=1348184]: |
0ms |
get settings: |
6ms |
get forum list: |
11ms |
check forum access: |
2ms |
check topic access: |
2ms |
track hit: |
27ms |
get topic data: |
6ms |
get forum data: |
4ms |
get page messages: |
28ms |
get tp. blocked users: |
1ms |
| others: | 221ms |
| total: | 308ms |
| 0 / 0 |
