hashmap - 如何确定存储字典单词的哈希码值？

Question

我正在准备面试，遇到了这个问题：

考虑一下我有 1000,000 个单词，我想创建一个字典。我可以使用的数据结构是 Map 或 B+ 树。但是我应该根据什么标准编写我的 hashcode()，以便检索可以快速。

欢迎大家的意见...

Answer 1

我不会使用，而是将字典存储为Patricia trie。

它还使用更少的内存，因为您没有单独存储所有字符串的所有公共前缀。

Answer 2

在“旧时代”（1980 年代），我们倾向于使用 B*（或 B*+）树，并且对敲击磁盘非常挑剔，但现在 1,000,000 个键无法存储在内存中，因此将其放入 dict 中即可完成它。

并告诉你的面试官：与开发人员的成本相比，内存几乎是免费的。你花在试图聪明上的时间量永远不会被你能想到的任何东西在效率上恢复。如果他们不明白为什么这是真的，那么……嗯。