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

Question

Я готовлюсь к собеседованию и наткнулся на вопрос:

Считайте, что у меня есть 1000 000 слов, и я хочу создать словарь.Структура данных, которую я могу использовать - это карта или деревья B +.Но по каким критериям я должен написать свой хэш-код (), чтобы поиск мог быть быстрым.

приветствовал бы все взгляды ...

Answer 1

Я бы не использовал ни один, и вместо этого сохранил бы словарь как Патриция .

Он также использует меньше памяти, так как вы не храните все общие префиксы всех строк отдельно.

Answer 2

В «старые времена» (1980-е годы) мы, как правило, использовали деревья B * (или B * +) и очень требовательны к ударам диска, но в настоящее время 1 000 000 ключей не годятся в памяти, поэтому вставьте диктовать и покончить с этим.

И скажите это своему интервьюеру: память близка к бесплатной по сравнению со стоимостью разработчиков. Количество времени, которое вы тратите, пытаясь быть умным в этом, никогда не будет восстановлено в эффективности с помощью чего-либо, что вы можете придумать. Если они не понимают, почему это так, тогда ... эх.