java - 将字典存储在哈希表中

Question

我有一项作业正在完成，但我无法联系教授来弄清楚某件事。我们的想法是，我们正在编写一个变位词求解器，使用一组给定的单词，我们将其存储在 3 个不同的字典类中:线性、二进制和哈希。

所以我们从文本文件中读取单词，对于前 2 个字典对象(线性和二进制)，我们将单词存储为 ArrayList...非常简单。

但是对于 HashDictionary，他希望我们将单词存储在 HashTable 中。我只是不确定 HashTable 的值是什么，或者您为什么要这样做。说明说我们将单词存储在哈希表中以便快速检索，但我只是不明白那是什么意思。将单词存储在数组列表中是有意义的，但我只是不确定键/值对对字典有何帮助。

也许我没有提供足够的细节，但我想也许有人会看到这样的事情，而且这对他们来说是显而易见的。

我们的每个类都有一个 contains 方法，它返回一个 boolean 值，表示传入的单词是否在字典中，所以 linear 对 arraylist 进行线性搜索，binary 对 arraylist 进行二分搜索，我不确定哈希....

Answer 1

区别在于速度。两种方法都有效，但哈希表速度很快。

当您使用 ArrayList 或任何类型的 List 查找元素时，您必须逐一检查每个列表项，直到找到所需的元素单词。如果该词不存在，则您已经遍历了整个列表。

当您使用HashTable 时，您会对要查找的单词执行一些“魔法”，称为计算单词的哈希值。使用该散列值，而不是遍历值列表，您可以立即推断出在哪里可以找到您的词 - 或者，如果您的词不存在于散列中，则您的词不存在。

我在这里过于简单化了，但这是一般的想法。可以再找一个问题here以及关于哈希表如何工作的各种解释。

这是一个使用 HashMap 的小代码片段。

// We will map our words to their definitions; word is the key, definition is the value
Map<String, String> dictionary = new HashMap<String, String>();
map.put("hello","A common salutation");
map.put("chicken","A delightful vessel for protein");

// Later ...
map.get("chicken"); // Returns "A delightful vessel for protein"; 

---

您描述的问题要求您使用 HashMap 作为满足三个要求的字典的基础:

• 向字典中添加一个词
• 从字典中删除一个词
• 检查一个词是否在字典中

使用存储键和值的映射似乎违反直觉，因为您真正想要的只是存储一个键(或只是一个值)。但是，正如我上面所描述的，HashMap 可以非常快速地找到与键关联的值。同样，它可以非常快速地查看 HashMap 是否知道某个键。我们可以通过将字典中的每个单词作为键存储在 HashMap 中，并将其与垃圾值相关联(因为我们不关心它)来利用这种特性，例如 null 。

您可以看到如何满足这三个要求，如下所示。

Map<String, Object> map = new HashMap<String, Object>();
// Add a word
map.put('word', null);

// Remove a word
map.remove('word');

// Check for the presence of a word
map.containsKey('word');

我不想给你过多的信息，但我们这里的要求与称为 Set 的数据结构一致.在 Java 中，常用的 Set 是 HashSet ，这几乎正是您在这段家庭作业中要实现的。 (事实上​​，如果这不是明确指示您使用 HashMap 的家庭作业，我建议您改为使用 HashSet。)