我有一个用于插入到使用顺序链接的哈希表中的实现:
public void insert(String word, Definition definition) {
int hash = hashFunction(word);
if (table[hash] == null) {
EntryImplSub chainedEntry = new EntryImplSub(null);
chainedEntry.addDefinition(definition);
chainedEntry.setWord(word);
table[hash] = chainedEntry;
numProbes++;
entries++;
}
else{
EntryImplSub chainedEntry = new EntryImplSub(table[hash]);
chainedEntry.addDefinition(definition);
chainedEntry.setWord(word);
table[hash] = chainedEntry;
numProbes++;
}
}
本质上,我正在尝试制作一本字典。有一个 EntryImpl 类,充当条目对象,每个条目都有一个单词和定义(或多个定义)。现在我创建了一个新的扩展类 EntryImplSub ,它是要链接的。这个新类有一个 getNext() 方法,并继承了普通 EntryImpl 类的所有其他功能。 EntryImplSub构造函数用于设置next。
问题
但是这不起作用。当我加载大量单词时,它们并未全部输入。我不确定为什么。
我的尝试
我的实现逻辑是,如果表条目为 null,我们插入一个新的 EntryImplSub 对象,其中 next = null,然后设置单词和定义。
但是,如果我们尝试插入的位置已经有一个单词,那么我们必须将新条目添加到列表的前面。因此,我们创建一个新的 EntryImplSub 对象,并将下一个属性设置为表中已有的属性。然后我为新的 EntryImplSub 设置单词并将其插入表中。所以我们应该有一个EntryImplSub的链表。
我真的不知道为什么这个装置会起作用。我花了几个小时试图找到错误,任何帮助将不胜感激。如果您需要澄清任何事情,请告诉我。
非常感谢!
编辑
这是检查条目是否在表中的代码
public List<Definition> getDefinitions(String word) {
int hash = hashFunction(word);
//ChainedEntry head = table[hash];
while (table[hash] != null) {
numSearches++;
if (((EntryImpl) table[hash]).getWord().equals(word)) {
return ((EntryImpl) table[hash]).getDefinitions();
}
table[hash] = table[hash].getNext();
}
return null;
}
如果返回 null,则该单词不在表中
最佳答案
我会像这样简化代码并编写一个简短的单元测试。很可能需要 2 - 3 个条目才能重现该问题,该问题很可能出现在您未显示的代码中。
public void insert(String word, Definition definition) {
int hash = 0; // put everything in one bucket for now // hashFunction(word);
if (table[hash] == null)
entries++;
EntryImplSub chainedEntry = new EntryImplSub(table[hash]);
chainedEntry.addDefinition(definition);
chainedEntry.setWord(word);
table[hash] = chainedEntry;
numProbes++;
}
由于 word
无法更改,我会将其作为构造函数参数(和 final
字段)
关于java - 使用链式对象实现 HashTable,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30011559/