java - 使用哈希表创建单词字典

Question

我正在使用以下类(class)自学哈希表: http://algs4.cs.princeton.edu/34hash/

在练习部分，我发现了以下内容:

密码检查器。编写一个程序，从命令行读取字符串并从标准输入读取单词字典，并检查它是否是“好”密码。这里，假设“好”意味着它 (i) 至少有 8 个字符长，(ii) 不是字典中的单词，(iii) 不是字典中后跟数字 0-9 的单词(例如， hello5), (iv) 不是由数字分隔的两个单词(例如 hello2world)

我想我对如何使用哈希表(HashMap)感到困惑。假设一个更简单的练习:我们只需要检查该单词是否在字典中，我需要使用哈希表来完成此操作。我的猜测是，我应该使用单词作为键添加字典中的所有单词，如果我想检查给定的单词是否在字典中，我使用“get”方法。如果找到，则该单词不是一个好的密码。但是:

1)我必须将与给定键关联的值设置为多少？

2) 如果两个单词散列到同一个地方怎么办？我知道碰撞部分是使用线性探测或分离链接解决的，所以当我使用get时，它将在数据结构中处理？

我不想让你编写任何代码，我只是想了解它是如何工作的。

提前致谢!

@Edit:我的另一个想法是只使用 hashCode。假设我有一个包含字典中所有单词的字符串数组。然后，如果它们具有相同的哈希码，我必须进行比较(因为哈希必须与 equals 一致)。如果我理解得很好，这个值并不重要，在这种情况下，我只需要检查这个词是否在字典中。所以我应该检查一下是否给我退回了一些东西。

Answer 1

1) What should be the value that I have to put associated with a given key?

如果你看一下 java HashSet 实现，你会发现它内部使用 HashMap，项目作为键添加到映射中，值是一个虚拟对象，由所有条目共享。如果您没有与键关联的特定值(例如流行度)，那么您的字典键结构更像是 HashSet 而不是 HashMap。

2) What if two words hash to the same place? I know the collision part is solved using Linear Probing or Separate Chaining, so when I use get, it will be handled in the data structure?

Java HashMap 实现使用单独的链接，所有具有相同哈希码的项都放在一个链表结构中。当您使用 HashMap 时，您不必担心冲突解决(除非您的目标是防止哈希攻击)。