1

我有一个正在处理的任务，我无法联系到教授来弄清楚某些事情。这个想法是我们正在编写一个字谜求解器，使用给定的一组单词，我们将其存储在 3 个不同的字典类中：线性、二进制和哈希。

因此，我们从文本文件中读取单词，对于前 2 个字典对象（线性和二进制），我们将单词存储为 ArrayList……很简单。

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

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

我们的每个类都有一个 contains 方法，它返回一个布尔值，表示传入的单词是否在字典中，因此线性对 arraylist 进行线性搜索，二进制对 arraylist 进行二进制搜索，并且 I'我不确定哈希值....

4

3 回答 3

7

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

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

当您使用 aHashTable时，您会对正在查找的单词执行一些“魔术”，即计算单词的哈希值。使用该哈希值，而不是遍历值列表，您可以立即推断在哪里找到您的单词 - 或者，如果您的单词在哈希中不存在，那么您的单词不存在。

我在这里过于简单化了，但这是一般的想法。您可以在此处找到另一个问题，其中包含有关哈希表如何工作的各种解释。

这是一个使用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";

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

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

使用存储键和值的映射似乎违反直觉，因为您真正想要的只是存储一个键（或只是一个值）。但是，如上所述，aHashMap可以非常快速地找到与键关联的值。同样，它可以非常快速地查看是否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，这几乎正是您在这部分家庭作业中实现的。（事实上​​，如果这不是明确指示您使用 a 的家庭作业HashMap，我建议您改用 a HashSet。）

于 2012-09-07T00:39:07.683 回答
2

数组很难找到东西。如果我给你array[0] = "cat"; array[1] = "dog"; array[2] = "pikachu";，你必须检查每个元素才能知道 jigglypuff 是否是一个词。如果我给了您hash["cat"] = 1; hash["dog"] = 1; hash["pikachu"] = 1;"，立即执行此操作，您只需直接查找即可。在这种特殊情况下，值 1 无关紧要，尽管您可以在其中放置有用的信息，例如您查找单词的次数，或者 1 表示真实单词，2 表示口袋妖怪的名称，或者一个真正的字典，它可以包含一个句子长的定义。不太相关。

于 2012-09-07T00:42:16.650 回答
1

听起来你并不真正了解哈希表。甚至维基百科对这种数据结构也有很好的解释。

您的哈希表将是一个大字符串数组（最初都是空的）。您使用单词中的字符计算哈希值，然后将单词插入表中的该位置。

当两个单词的哈希值相同时会出现问题。并且有一些解决方案。一种是在每个数组位置存储一个列表，然后将单词推到该列表中。另一种方法是按已知数量在表格中步进，直到找到空闲位置。另一种方法是使用不同的算法计算二级散列。

重点是哈希查找速度很快。计算哈希值非常快，然后您所要做的就是检查该数组位置的单词是否存在（并且与搜索单词匹配）。您遵循用于插入的哈希值冲突（在本例中为不匹配）的相同规则。

您希望您的表大小是一个大于您打算存储的元素数量的素数。您还需要一个快速发散的散列函数，以便您的数据更有可能通过散列表广泛分布（而不是在一个区域中大量聚集）。

希望这对您有所帮助，并为您指明正确的方向。

于 2012-09-07T00:40:58.540 回答