我有一份我正在进行的任务,而且我无法掌握教授以明确某些事情.我们的想法是,我们正在使用一组给定的单词编写一个anagram解算器,我们将其存储在3个不同的字典类中:Linear,Binary和Hash.
因此,我们从文本文件中读取单词,对于前2个字典对象(线性和二进制),我们将单词存储为ArrayList ......很简单.
但对于HashDictionary,他希望我们将这些单词存储在HashTable中.我只是不确定HashTable的值是什么,或者为什么要这样做.说明说我们将这些单词存储在Hashtable中以便快速检索,但我只是不明白这一点.将字词存储在arraylist中是有意义的,但我只是不确定键/值配对如何帮助字典.
也许我没有提供足够的细节,但我想也许有人会看到类似这样的事情并且对他们来说很明显.
我们的每个类都有一个contains方法,它返回一个布尔值,表示传入的单词是否在字典中,因此线性搜索arraylist,二进制搜索arraylist,我'我不确定哈希....
不同的是速度.这两种方法都有效,但哈希表很快.
当您使用ArrayList或任何类型List的元素查找元素时,您必须逐个检查每个列表项,直到找到所需的单词.如果这个词不在那里,你就会在整个列表中循环.
当你使用a时HashTable,你在你正在查找的单词上执行一些"魔法",称为计算单词的散列.使用该哈希值,而不是循环遍历值列表,您可以立即推断出在哪里找到您的单词 - 或者,如果您的单词在哈希中不存在,那么您的单词就不存在了.
我在这里过分简化,但这是一般的想法.您可以在此处找到另一个问题,其中包含有关哈希表如何工作的各种解释.
这是一个使用a的小代码片段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";
您描述的问题要求您使用a HashMap作为满足三个要求的字典的基础:
使用存储键和值的映射似乎是违反直觉的,因为您真正想要的只是存储一个键(或只是一个值).但是,如上所述,a 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');
我不想让你了解信息,但我们在这里的要求与称为a的数据结构一致Set.在Java中,常用的Set是HashSet,这几乎就是你用这一部分的作业分配实现的.(事实上,如果这不是明确指示你使用的家庭作业HashMap,我建议你改用HashSet.)