Никак не могу разобраться с хешированием.

Нужно построить хеш-таблицу для хранящихся в текстовом файле "слов", разделённых пробелами. "Слово" - последовательность символов. Метод разрешения коллизий - с помощью связных списков.

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








Это сообщение отредактировал(а) Avaj - 26.10.2008, 06:21

        Нет необходимости читать все слова. Читать нужно по одному слову. Далее, по слову с помощью хеш-функции находить место в таблице. Если случилась коллизия, то нужно добавить элемент в гроздь( список ), висящую на этом месте. Получается такая конструкция( Пусть Aij - j - ый элемент грозди i ( Ai0 - элемент нашей первоначальной таблицы) ):
A00 A10 A20 ... An0
A01        A21     An1
A02                   An2
A03

        Далее некоторые мысли, которые могут помочь с определением размерности.

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

        P.S.: просто мысли вслух.