哈希方法问题，具体是get方法

所以，我在一个数据结构类，我们正在编写代码和不同的哈希方法。事实上，我在"get"这个词上遇到了麻烦。方法。在最后一个"关键字"之前，我们的测试都运行良好。它被断言返回null。由于某些原因，for循环退出，keyStartIndex再次实例化。这个方法不是递归的，所以我不知道为什么会这样。代码如下。如有任何帮助，不胜感激。

方法我正在尝试完成，这是有问题。

...
public String get(String key) {
//TODO : complete the method
int keyStartIndex = (int) hashFunction(key) % items.length;
for(int i = keyStartIndex; i < items.length; i++){
if(items[i].key == hashFunction(key)){
return items[i].item;
} else if(i == items.length-1){
i=0;
continue;
}
}
return null;
}
...

该类中应用于此方法的所有先前代码

...
import java.util.Arrays;
import jdk.internal.org.objectweb.asm.tree.analysis.Value;
class DataItem {
long key;
String item;
public DataItem(long key, String item) {
this.key = key;
this.item = item;
}
@Override
public String toString() {
return String.format("{%s:%s}", key, item);
}
}
public class HashMap {
private int size = 0;
private static final int INITIAL_SIZE = 10;
private static final int DELETED_KEY = 0;
private DataItem[] items;

public HashMap() {
items = new DataItem[INITIAL_SIZE];
}
public int size() {
return size;
}
public long hashFunction(String key) {
long hashed = 0;
for(int i = 0; i < key.length(); i++){
hashed += key.charAt(i)*(Math.pow(27, i));
}
return hashed;
}
public void put(String key, String value) throws TableIsFullException {
if (size >= items.length-1){
throw new TableIsFullException();
} else {
DataItem input = new DataItem(hashFunction(key), value);

for(int i = ((int) input.key % items.length); i < items.length; i++){
if(items[i] != null){
continue;
}else if(i == items.length - 1 && items[i] != null){
i = 0; 
continue;
} else {
items[i] = input;
size++;
break;
}
}
} 
}
...

---------------------------------------------- 和测试正在运行中,只有最后一个再次失败,与"key9"。我已经运行调试器，它说有一个nullPointerException。同样，对于断点，由于某种原因，它离开for循环并处理另一个键，具体为key3。我不知道为什么会这样。

@Test
public void testGet() throws TableIsFullException {
map.put("key1", "value1");
map.put("key2", "value2");
map.put("key3", "value3");
map.put("key4", "value4");
map.put("key5", "value5");
map.put("key6", "value6");
assertEquals("value3", map.get("key3"));
assertEquals(null, map.get("key9"));   
}

您的put和get方法没有正确实现环绕。这意味着当你在表的末尾遇到一些哈希冲突时，事情就会变得混乱。

其次，两种方法都没有正确处理哈希冲突。哈希的契约是obj1.equals(obj2)意味着hash1 == hash2，而不是相反。这意味着DataItem必须记录原始对象和散列。我将假设您已经添加了适当的字段，并且DataItem现在有三个字段名称key,hash和value。

让我们从put:

开始

结束条件是i >= items.length，所以如果你绕行，你要么有一个无限循环，要么你从不绕行。
因为你先检查items[i] != null,i == items.length - 1 && items[i] != null永远不会被触发，所以当表的末尾是满的时候你永远不会绕。
不检查现有项是否与新键匹配。

纠正put的一种方法是将items视为循环缓冲区。这意味着你减去一个偏移模items.length:

int hash = hashFunction(key);
int offset = hash % items.length);

for(int i = 0; i < items.length; i++) {
int k = (i + offset) % items.length;
if(items[k] == null) {
items[k] = new DataItem(key, hash, value);
size++;
break;
}
if(items[k].hash == hash && items[k].key.equals(key)) {
items[k].value = value;
break;
}
}

您还需要在抛出异常之前修复大小检查。当有一个空闲槽位可用时，检查size >= items.length - 1将抛出异常。正确的条件是

if(size >= items.length) {

你的get方法也有和put一样的环绕问题。它也有一个问题，你检查哈希相等，而不是对象相等，当你检索一个对象。

int hash = hashFunction(key);
int offset = hash % items.length;
for(int i = 0; i < items.length; i++) {
int k = (i + offset) % items.length
if(items[k].hash == hash && items[k].key.equals(key)){
return items[i].value;
}
}
return null;

检查items[k].item.equals(key)对于正确解决哈希冲突至关重要。注意，它只在哈希匹配时执行，因为短路。

尽量避免在循环中重新计算像hash这样的值。

如果你试图支持remove操作，整个方案就会崩溃。如果您注意到，put将停止搜索匹配，一旦它找到一个空槽。如果您可以在匹配对象之前创建空槽，则此操作将中断。

您看到的NullPointerException发生是因为在get()方法中您编写了

if(items[i].key == hashFunction(key))

现在，如果特定的键没有添加到HashMap(items数组尚未满)，条目items[i]仍然是null，并且试图访问items[i].key会给出您所看到的NullPointerException。

导致你的问题的最短测试用例是:

@Test
public void keyNotFound() throws TableIsFullException {
assertEquals(null, map.get("key9"));   
}

除此之外，仔细阅读"疯狂的物理学家"的回答。因为它解决了实现中的其他设计缺陷(尽管不是这个)。

相关内容

最新更新

热门标签：