|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
29.12.2010, 15:49 | #1 |
Старожил
Регистрация: 04.02.2009
Сообщений: 17,351
|
Как организовать хеш?
Пока думаю сделать для строк (про THashStrigList слышал). Меня интересует такой вопрос - хочу организовать функцию AddStr(строка), которая бы возвращала идентификатор. Так вот как мне всегда генерировать незанятые идентификаторы? Ведь элементы могут и добавляться и удаляться (умными ссылками). Эффективно ли для этого заюзать какой-нибудь рандом, или же есть какой хитрый план (уж простите нас деревенских)?
Маньяк-самоучка
Utkin появился в результате деления на нуль. Осторожно! Альтернативная логика |
29.12.2010, 16:58 | #2 |
я получил эту роль
Старожил
Регистрация: 25.05.2007
Сообщений: 3,694
|
Завести глобальную/классовую переменную, которую AddStr будет инкрементить, очевидно.
Если нужна уникальность при каждом следующем запуске — можно эту переменную обьявить как TGuid, инициализировать её CoCreateGuid, дальше см. п.1 - дёшево и сердито
пыщь
|
29.12.2010, 22:44 | #3 |
Старожил
Регистрация: 13.08.2009
Сообщений: 2,581
|
http://www.transl-gunsmoker.ru/2010/...g-post_03.html
Говоря кратко: всё зависит от конкретной задачи. Хотите общий случай - будут коллизии. Не хотите коллизий - надо разбираться с конкретными данными.
Опытный программист на C++ легко решает любые не существующие в Паскале проблемы.
|
30.12.2010, 06:54 | #4 |
Старожил
Регистрация: 04.02.2009
Сообщений: 17,351
|
JTG, мне бы целое число получать. Чтобы потом проводить с ним всякие махинации было проще.
Да идентификатор должен быть уникальным. Коллизий не хочу. Сделать решил на основе динамического массива элементов, где каждый элемент содержит строку, идентификатор (или ключ) и количество ссылок на строку. Проблема (как мне видится) в том, чтобы генерировать такой ключ, который бы никогда не повторился с ключами для уже имеющихся строк. При этом элементы будут и удаляться тоже. Все остальные операции я уже продумал. Конечно можно приращивать какой-нибудь очень большой встроенный целый тип, но не факт, что рано или поздно он закончится....
Маньяк-самоучка
Utkin появился в результате деления на нуль. Осторожно! Альтернативная логика Последний раз редактировалось Utkin; 30.12.2010 в 06:56. |
30.12.2010, 15:46 | #5 |
Старожил
Регистрация: 13.08.2009
Сообщений: 2,581
|
Не бывает такого.
Все претензии к Иоганну Петеру Густаву Лежён-Дирихле.
Опытный программист на C++ легко решает любые не существующие в Паскале проблемы.
|
31.12.2010, 06:57 | #6 |
Старожил
Регистрация: 04.02.2009
Сообщений: 17,351
|
Однако, суть в следующем - это немного переработанный хитрый план от JTG - у меня есть идентификаторы и глобальная переменная паскалевские Cardinal. Число же элементов, кажись, не больше integer - то есть даже в идеале в плотно забитом массиве всегда существует свободный идентификатор. Как и писал JTG, я занимаюсь приращиванием глобальной переменной, которая собой олицетворяет следующий свободный идентификатор. Однако, при этом проводится проверка не занят ли он случаем (а если занят, то снова приращиваем и проверяем и так до тех пор пока не найдем свободный). То есть для большого числа элементов это будет медленно.
Работать-то оно работает, но я подозреваю, что возможны случаи с заметными паузами в работе. Я вот думаю не лучше ли вместо стандартного приращения брать какое-нибудь случайное число? Просто если вдруг счетчик обнулится (ну мало ли), то время поиска нового идентификатора может значительно возрасти... С другой стороны такая ситуация наступит не очень скоро...
Маньяк-самоучка
Utkin появился в результате деления на нуль. Осторожно! Альтернативная логика Последний раз редактировалось Utkin; 31.12.2010 в 08:08. |
01.01.2011, 22:24 | #7 |
Старожил
Регистрация: 22.05.2007
Сообщений: 9,065
|
Как этот счетчик спасает от коллизий? Все эти приращения и есть по сути реализация проблемы коллизий, а не избежание их. В идеале нужно выработать алгоритм, который для любой строки выдаст уникальное значение ключа и при этом это значения будет постоянно для всех копий этой строки. Рандом тут не поможет, т.к. не понятна реализация поиска строки по ключу.
|
02.01.2011, 10:22 | #8 |
Старожил
Регистрация: 04.02.2009
Сообщений: 17,351
|
Ну я поэтому и советуюсь .
Вообще поиск осуществляется перебором элементов динамического массива - если в соответствующем элементе (это запись) идентификатор совпал, значит здесь искомая строка. Я понимаю, что это все не совсем то, что нужно, но пока ничего более умного не придумал.
Маньяк-самоучка
Utkin появился в результате деления на нуль. Осторожно! Альтернативная логика |
02.01.2011, 10:52 | #9 | |
Участник клуба
Регистрация: 06.03.2009
Сообщений: 1,346
|
Цитата:
|
|
03.01.2011, 18:27 | #10 | |
Старожил
Регистрация: 22.05.2007
Сообщений: 9,065
|
Цитата:
1) Тупо записываем элемент в следущую ячейку, если хеш совпал. Допустим алгоритм выдал для строки хэш 10, но соответствующая ячейка уже занята другой строкой (произошла коллизия), следовательно записываем строку как хэш 11 (если конечно он свободен, а иначе перебираем 12, 13,..). Минусы тут в том, что коллизии будут расти в геометрической прогрессии. Да и поиск строки будет долгим, если вместо 10 она запишется в 100 ячейку из-за всех этих самых коллизий. 2) Каждая ячейка - есть односвязный список и в случае коллизий он заполняется новыми элементами, т.е. все строки с хэшем 10 будут в одном месте находиться, в одном отдельном списке. Можно небольшую оптимизацию произвести в плане поддержания его отсортированного состояния. Тут поиск будет быстрее работать, но памяти больше в разы будет расходоваться, чем на первый вариант. Но в идеале реализовать хеш-функцию, чтобы коллизий не было. Это и упростит дальнейшую разработку и работать всё это дело будет быстрее и экономичнее по памяти. |
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
при подсчете хеш-суммы ошибка Integer Overflow. как обойти? | Человек_Борща | Общие вопросы Delphi | 2 | 09.02.2011 11:20 |
хеш-функция | chyngyz91 | Общие вопросы C/C++ | 2 | 12.12.2010 12:32 |
Графы. Хранение хранить список смежностей как хеш-таблицу. Чем не идеал? | Kn793 | Свободное общение | 7 | 08.11.2010 17:55 |
ХЕШ-таблица | iceman2112 | Общие вопросы C/C++ | 0 | 09.05.2010 13:07 |
Как лучше организовать базу данных типо как в ICQ | Руслантус | БД в Delphi | 3 | 09.08.2008 23:57 |