Сверхбыстрый поиск

[ManHack]

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

Таблица фиксированная, в процессе поиска меняться не будет, её можно изначально упорядочить наиболее удобным образом (рекомендации?).

[lxa85]

рекомендации? »
Зависят от типа данных по которому идет поиск.
Приведи пример записи таблицы.

[ManHack]

В таблице два поля: строка и множество (паскалевский перечислимый тип).
Т.е. одна запись таблицы выглядит, например, так:
DEFENITION | ccDef
где DEFENITION - строка - ключ, по которой ведётся поиска, а ccDef - элемент множетства ( ccDef, ccTor, {...} , ccAss, ccOp ) - данные, которые мы ищем по ключу.

[ganselo]

ManHack, думаю хэшь стоит использовать если строки большого размера.

[ManHack]

Строки маленькие, до десяти символов.
Что можно сделать, чтобы не возникало коллизий?

ganselo, а раз не хэш, тогда что? что будет работать быстрее поиска по хэш-таблице в такой ситуации?

[pva]

кажись только хеш по самому различаемому (из 40 статичных строчек) символу + длина строчки (если различается)

[Busla]

Пораскинув мозгами я пришёл к выводу, что без хэш-таблицы тут не обойтись... (к правильному выводу пришёл я?) »
Как вы связываете зрение и слух - Если уши отрезать, папаха на глаза упадёт ;-)
По хэшу тоже надо как-то искать - т.е. это не ответ на вопрос об алгоритме поиска. Тем более, хэш надо вычислять на каждом шаге. Есть большое подозрение, что на таком небольшом количестве данных тупой перебор со сравненим окажется самым выгодным.

[ManHack]

Нужно придумать идеальную хеш-функцию для слов ARRAY, BY, BEGIN, CASE далее по списку (чтобы значения хеш-функции для различных слов из списка не совпадали)
EnterKW('ARRAY', lexNone);
EnterKW('BY', lexNone);
EnterKW('BEGIN', lexBEGIN);
EnterKW('CASE', lexNone);
EnterKW('CONST', lexCONST);
EnterKW('DIV', lexDIV);
EnterKW('DO', lexDO);
EnterKW('ELSE', lexELSE);
EnterKW('ELSIF', lexELSIF);
EnterKW('END', lexEND);
EnterKW('EXIT', lexNone);
EnterKW('FOR', lexNone);
EnterKW('IF', lexIF);
EnterKW('IMPORT', lexIMPORT);
EnterKW('IN', lexNone);
EnterKW('IS', lexNone);
EnterKW('LOOP', lexNone);
EnterKW('MOD', lexMOD);
EnterKW('MODULE', lexMODULE);
EnterKW('NIL', lexNone);
EnterKW('OF', lexNone);
EnterKW('OR', lexNone);
EnterKW('POINTER', lexNone);
EnterKW('PROCEDURE', lexNone);
EnterKW('RECORD', lexNone);
EnterKW('REPEAT', lexNone);
EnterKW('RETURN', lexNone);
EnterKW('THEN', lexTHEN);
EnterKW('TO', lexNone);
EnterKW('TYPE', lexNone);
EnterKW('UNTIL', lexNone);
EnterKW('VAR', lexVAR);
EnterKW('WHILE', lexWHILE);
EnterKW('WITH', lexNone);
Я придумал так:
for i := 1 to length (Stroka) do
result := result + Stroka[i]*31; (символы строки складываются и каждый раз домножается на 31)
hash := result mod SizeOfHashTable;

но в таком случае у меня совпали значение хеш-функции для DIV и NIL.
Что можно придумать лучшее, чтобы значения не совпадали?

Как использовать повторное хеширование?

[pva]

ИМХО первая буква XOR вторая
а сочетание {первая, втроая, последняя} - вобще уникальное

[ManHack]

ИМХО первая буква XOR вторая
а сочетание {первая, втроая, последняя} - вобще уникальное »
первая XOR вторая - не подходит, т.к. REPEAT и RECORD, например.
первая XOR последняя, первая XOR вторая XOR последняя, длина слова XOR первая XOR последняя, длина слова XOR вторая XOR последняя, XOR всех букв - все они дают коллизии на данном множестве из 34 слов.
Пишу так:
hash := ord(Name[1]) XOR ord(Name[length(Name)]);

Какие ещё будут идеи?

[luna2005]

Пишется под 32-разрядный процессор?

Тогда первые 4 байта сравнивать без всяких хешей, к коротким словам естественно перед этим добавить нули/пробелы.

Если известно какие слова будут попадаться чаще, их поместить в начало таблицы.

[pva]

без xor, сочетание {первая, вторая, последняя} - хотя в один байт это не упихать

[ManHack]

Сделал так:
hash := ord(Name[1])*100 + ord(Name[length(Name)]) - 6588;
(коды заглавных латинских букв заведомо двузначные)

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

[pva]

(коды заглавных латинских букв заведомо двузначные) »
их 26 штук, попробуй * 26