Теория

lxa85 · Отправлено: **20:52, 24-02-2010** | #2

Цитата ManHack:

рекомендации? »

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

ManHack · Отправлено: **17:54, 25-02-2010** | #3

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

ganselo · Отправлено: **19:27, 25-02-2010** | #4

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

ManHack · Отправлено: **01:04, 26-02-2010** | #5

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

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

pva · Отправлено: **00:02, 28-02-2010** | #6

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

Busla · Отправлено: **11:47, 03-03-2010** | #7

Цитата ManHack:

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

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

ManHack · Отправлено: **23:23, 04-03-2010** | #8

Нужно придумать идеальную хеш-функцию для слов 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 · Отправлено: **07:56, 05-03-2010** | #9

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

ManHack · Отправлено: **12:33, 06-03-2010** | #10

Цитата pva:

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

первая XOR вторая - не подходит, т.к. REPEAT и RECORD, например.
первая XOR последняя, первая XOR вторая XOR последняя, длина слова XOR первая XOR последняя, длина слова XOR вторая XOR последняя, XOR всех букв - все они дают коллизии на данном множестве из 34 слов.
Пишу так:

Код:

hash := ord(Name[1]) XOR ord(Name[length(Name)]);

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