Все зависит от точной постановки задачи, можно вообще обойтись без явных идентификаторов и вместо них использовать номера слов в массивах отдельно для каждой длины слова.
@---,---`-----
Массивов может быть несколько для каждой длины слова отдельно что позволит как лучше использовать память при этом ускоряя поиск и обновление так возможно и обойтись 16 бит идентификаторами для слов при этом используя длину слова в качестве неявного расширения пространства идентификаторов. А если для Вашей задачи достаточно скорости последовательного поиска то словарь можно даже сжать причем намного плотнее чем обычный текст.
И при этом использовать двоичный поиск в массиве без всякого хэширования.
2^19 = 524288
То есть за 20 простых сравнений слово будет найдено что быстрее чем вычислить хэш функцию и потом разбираться с совпадениями.
Действительно, зачем все это городить? Если Вы уточните задачу то возможно еще идеи появятся.
Я и не старался быть понятным. А по теме можно вспомнить о том что великий Кнут явно пишет о непригодности чистого хэширования для серьезных задач потому что у этого способа индексации очень плохая производительность в наихудшем случае. Возможно что то что предлагает euhenio по поводу дополнения хэширования деревом будет оптимальным решением. Только я бы хэшировал не часть слова а все слово полностью чем нибудь типа md5 для лучшего распределения при этом не обращая внимания на совпадения и брал бы столько бит что их бы хватило на хэширование без совпадений при идеальном случае то есть дерево было бы только страховкой для наихудшего случая при совпадениях.
