Хэш - функция для строк, ищу Опции

[a3boot]

Всё ещё занимаюсь поиском в таблице служебных слов...
---
Пока что я пользуюсь чем-то подобным

trunc(a*(ord(s[1]))+b*(ord(s[length(s)])))-k

Такая функция не имеет коллизий, занимает не много памяти (134 ячейки на 34 слова), но, как мне кажется работает медленно.
---
Может, кто сталкивался с разработкой хэш - функций для строк и готов поделиться опытом.
Таблица слов известна (см. table.txt)

[Malice]

занимает не много памяти (134 ячейки на 34 слова)

Не понял, как такое могло получится.. Если у тебя комбинация 2-х символов уникальна, то для хеша одной строки надо 2 байта максимум.
Пусть: o=ord(s[1]); p=ord(s[length(s)]);
Хеш=o shl 8+p; (от умножений лучше избавиться, т.к медленнно это).
В твоем случае можно и в 1 байт засунуть, просто подогнать, вот так например:
Хеш=(o-65) shl 3 xor p;
Тоже уникально получится..
Если строки любые, то такие методы не пройдут, нужно каждый символ в строке учитывать.

[a3boot]

Я, наверно, не корректно высказался по поводу ячеек.
---
Под ячейкой в данном случае понимается один элемент массива служебных слов.
---
Наверно, лучше говорить о множестве значений хэш-функции.

Предложеная функция

(o - 65) shl 3 xor p

принимает значения от 6 до 248 следовательно для хранения такой таблицы требуется 243 ячейки ([6..242]).

Моя функция давала значения от 0 до 133 - 134 ячейки, но она проигрывает по времени выше указанной.
---
Время для меня в данный момент является более важной характеристикой, поэтому Огромное спасибо Malice!!!
Может быть предложишь ещё какие - нибудь хэши, а я поэкспериментирую...

[Malice]

Время для меня в данный момент является более важной характеристикой, поэтому Огромное спасибо Malice!!!
Может быть предложишь ещё какие - нибудь хэши, а я поэкспериментирую...

Небольшой перебор выдал вот такую формулу:
хеш=(o-61) xor (p shl 2)-256; хеш=[0..97]

[a3boot]

Malice, спасибо за помощь.
---
У меня ещё вопрос : нельзя ли сделать более простую функцию, не использующую код последней буквы?
---
Дело в том, что как бы мы не изворачивались, всё равно при обращении к трём элементам массива (нулевому, первому и последнему), и взятию от них ord тратится некое постоянное время, быстрее которого хэш - функцию не вычислить!
---
Видимо придётся оперировать только кодом первого и второго символа(минимальная длина слова - 2), или например кодом первого(второго) символа и длинной...

[Malice]

Только 1-го и 2-го нельзя, т.к. они повторяются в твоем словаре (Else, ElseIF) и хеши одинаковые будут, длина+1+2-ой тоже (RECORD,REPEAT,RETURN).
А так, можно все, экспериментируй и сравнивай результаты.. Могу сказать только, что ни на Length ни на Ord время не тратится. Попробуй переложить на Asm, может сделаешь оптимальнее компилятора паскаля, не вызывай этот код (подсчет хеша) как функцию (на вызов тратится время тоже).