Как организовать хеш?

[Utkin]

Пока думаю сделать для строк (про THashStrigList слышал). Меня интересует такой вопрос - хочу организовать функцию AddStr(строка), которая бы возвращала идентификатор. Так вот как мне всегда генерировать незанятые идентификаторы? Ведь элементы могут и добавляться и удаляться (умными ссылками). Эффективно ли для этого заюзать какой-нибудь рандом, или же есть какой хитрый план (уж простите нас деревенских)?

[JTG]

Завести глобальную/классовую переменную, которую AddStr будет инкрементить, очевидно.
Если нужна уникальность при каждом следующем запуске — можно эту переменную обьявить как TGuid, инициализировать её CoCreateGuid, дальше см. п.1 - дёшево и сердито

[GunSmoker]

http://www.transl-gunsmoker.ru/2010/...g-post_03.html

Говоря кратко: всё зависит от конкретной задачи.

Хотите общий случай - будут коллизии. Не хотите коллизий - надо разбираться с конкретными данными.

[Utkin]

JTG, мне бы целое число получать. Чтобы потом проводить с ним всякие махинации было проще.
Да идентификатор должен быть уникальным.
Коллизий не хочу. Сделать решил на основе динамического массива элементов, где каждый элемент содержит строку, идентификатор (или ключ) и количество ссылок на строку. Проблема (как мне видится) в том, чтобы генерировать такой ключ, который бы никогда не повторился с ключами для уже имеющихся строк. При этом элементы будут и удаляться тоже. Все остальные операции я уже продумал. Конечно можно приращивать какой-нибудь очень большой встроенный целый тип, но не факт, что рано или поздно он закончится....

[GunSmoker]

Не бывает такого.

Все претензии к Иоганну Петеру Густаву Лежён-Дирихле.

[Utkin]

Сообщение от GunSmoker

Не бывает такого.

Однако, суть в следующем - это немного переработанный хитрый план от JTG - у меня есть идентификаторы и глобальная переменная паскалевские Cardinal. Число же элементов, кажись, не больше integer - то есть даже в идеале в плотно забитом массиве всегда существует свободный идентификатор. Как и писал JTG, я занимаюсь приращиванием глобальной переменной, которая собой олицетворяет следующий свободный идентификатор. Однако, при этом проводится проверка не занят ли он случаем (а если занят, то снова приращиваем и проверяем и так до тех пор пока не найдем свободный). То есть для большого числа элементов это будет медленно.
Работать-то оно работает, но я подозреваю, что возможны случаи с заметными паузами в работе.
Я вот думаю не лучше ли вместо стандартного приращения брать какое-нибудь случайное число? Просто если вдруг счетчик обнулится (ну мало ли), то время поиска нового идентификатора может значительно возрасти... С другой стороны такая ситуация наступит не очень скоро...

[pu4koff]

Как этот счетчик спасает от коллизий? Все эти приращения и есть по сути реализация проблемы коллизий, а не избежание их. В идеале нужно выработать алгоритм, который для любой строки выдаст уникальное значение ключа и при этом это значения будет постоянно для всех копий этой строки. Рандом тут не поможет, т.к. не понятна реализация поиска строки по ключу.

[Utkin]

Ну я поэтому и советуюсь .
Вообще поиск осуществляется перебором элементов динамического массива - если в соответствующем элементе (это запись) идентификатор совпал, значит здесь искомая строка. Я понимаю, что это все не совсем то, что нужно, но пока ничего более умного не придумал.

[Вадим Буренков]

Однако, при этом проводится проверка не занят ли он случаем (а если занят, то снова приращиваем и проверяем и так до тех пор пока не найдем свободный).

Я вот одно не понял. Зачем проверка на занятость ID если при создании элемента каждый новый ID будет больше предыдущего (следовательно и всех других). Просто я сам использовал такую методику и проблем не возникало...

[pu4koff]

Сообщение от Utkin

Ну я поэтому и советуюсь .
Вообще поиск осуществляется перебором элементов динамического массива - если в соответствующем элементе (это запись) идентификатор совпал, значит здесь искомая строка. Я понимаю, что это все не совсем то, что нужно, но пока ничего более умного не придумал.

Из курса университета я помню 2 варианта разрешения коллизий:
1) Тупо записываем элемент в следущую ячейку, если хеш совпал.
Допустим алгоритм выдал для строки хэш 10, но соответствующая ячейка уже занята другой строкой (произошла коллизия), следовательно записываем строку как хэш 11 (если конечно он свободен, а иначе перебираем 12, 13,..). Минусы тут в том, что коллизии будут расти в геометрической прогрессии. Да и поиск строки будет долгим, если вместо 10 она запишется в 100 ячейку из-за всех этих самых коллизий.
2) Каждая ячейка - есть односвязный список и в случае коллизий он заполняется новыми элементами, т.е. все строки с хэшем 10 будут в одном месте находиться, в одном отдельном списке. Можно небольшую оптимизацию произвести в плане поддержания его отсортированного состояния.
Тут поиск будет быстрее работать, но памяти больше в разы будет расходоваться, чем на первый вариант.
Но в идеале реализовать хеш-функцию, чтобы коллизий не было. Это и упростит дальнейшую разработку и работать всё это дело будет быстрее и экономичнее по памяти.