java - 为什么我的 get 方法没有将分配的值返回给我的键？

Question

我在数据结构和算法类(class)中被分配了以下任务，但我不知道为什么它不起作用。

任务是实现一个链接哈希表。我创建了两个类，一个充当键 <-> 值对，代表一个元素(Entry 类)，另一个具有方法的 Hashtable 类(当前只有 put 和 get)，但我似乎看不到任何他们去工作。 Hashfunction方法是我们老师提供的，所以我无法回答任何相关问题。

每当我执行该程序时，我都不会收到错误，但列表返回空。这里有人可以指导我做错的地方的正确方向吗？我假设错误出在 put 方法中，但我似乎无法弄清楚问题可能在哪里。

最诚挚的问候，维克多

 package Laboration2;

/**
 * A class that works as a container for the key and value.
 * 'Entry' will become an element in our hashtable
 *
 * @author Victor Marante
 * @version 1.0
 * @since 2016-09-22
 */
public class Entry {

    private Object key;
    private Object value;
    private Entry next;

    public Entry(Object key, Object value) {
        this.key = key;
        this.value = value;
    }

    @Override
    public boolean equals(Object obj) {
        Entry keyToCompare = new Entry(obj, null);
        return key.equals(keyToCompare.key);
    }

    public Object getValue() {
        return value;
    }

    public void setValue(Object value) {
        this.value = value;
    }

    public Object getKey() {
        return key;
    }

    public Entry getNext() {
        return next;
    }

    public void setNext(Entry next) {
        this.next = next;
    }
}

包含哈希表本身所有方法的类:

package Laboration2;

import javax.swing.*;
import java.util.Iterator;
import java.util.LinkedList;

/**
 * Created by Victor on 22/09/16.
 */
public class Hashtable {

    private LinkedList<Object> insertionOrder = new LinkedList<Object>();
    private LinkedList<Entry>[] table;

    // Constructor that initiates a hashtable
    public Hashtable(int size) {
        table = (LinkedList<Entry>[]) new LinkedList<?>[size];
        for (int i = 0; i < size; i++) {
            table[i] = new LinkedList<Entry>();
        }
    }

    // Hashfunction
    private int hashIndex(Object key) {
        int hashCode = key.hashCode();
        hashCode = hashCode % table.length;
        return (hashCode < 0) ? -hashCode : hashCode;
    }

    public Object get(Object key) {
        int hashIndex = hashIndex(key);
        LinkedList<Entry> entries = table[hashIndex];
        Iterator<Entry> it = entries.listIterator();
        while (it.hasNext()) {
            Entry entry = it.next();
            if (entry.equals(key)) {
                return entry.getValue();
            }
        }
        return null;
    }

    public void put(Object key, Object value) {
        int hashIndex = hashIndex(key);
        LinkedList<Entry> entries = table[hashIndex];
        Iterator<Entry> it = entries.listIterator();

        while (it.hasNext()) {
            Entry entry = it.next();
            if (entry.equals(key)) {
                entry.setValue(value);
                insertionOrder.add(value);
            } else {
                entry.setNext(new Entry(key, value));
                insertionOrder.add(value);
            }
        }
    }

    public static void main(String[] args) {

        Hashtable table = new Hashtable(15);
        table.put("hej", "hello");
        table.put("nej", "no");
        table.put("senare", "later");
        table.put("idag", "today");
        table.put("igår", "yesterday");

        table.get("hej");
    }
}

EDIT1(针对 Krishas 评论):

public void put(Object key, Object value) {
        int hashIndex = hashIndex(key);
        LinkedList<Entry> entries = table[hashIndex];
        Iterator<Entry> it = entries.listIterator();

        if (table[hashIndex] == null) {
            table[hashIndex] = new LinkedList<Entry>(key, value);

        } else {

            while (it.hasNext()) {
                Entry entry = it.next();
                if (entry.equals(key)) {
                    entry.setValue(value);
                    insertionOrder.add(value);
                } else {
                    entry.setNext(new Entry(key, value));
                    insertionOrder.add(value);
                }
            }
        }
    }

Answer 1

出了什么问题

这确实是因为你的 put 方法。您对 setNext 的调用位于错误的位置，这会产生 2 个后果:

• 由于列表最初是空的，it.hasNext() 将返回 false，并且您永远不会向列表添加任何内容
• 即使您成功向列表中添加了某些内容，只有当列表中的 first 键不匹配时，您才会调用 setNext。所以你总是丢弃第二个元素。

我认为你的一些清晰性来自于你混淆了你在这里处理的两种列表:一种是表内的列表，其目的是处理冲突，这意味着不同的键最终出现在表的同一索引中。另一种是全局列表，其目的是记录插入的顺序。

对于第一种类型，您不需要“setNext”，只需“添加”即可。 SetNext 实际上是针对第二种类型的(见下文)。

你应该做什么

只有在处理整个列表后没有匹配项(也包括列表为空的情况)时(即在 while 循环之后)，您才应该添加新条目。

有关代码的其他注释

• 您可以使用 for-each 语句来简化列表上的迭代。而不是写

  Iterator<Entry> it = list.iterator();
  Entry entry;
  while(it.hasNext()){
     entry = it.next();
  

  你可以写

  for(Entry entry : list){
  

• 在我看来，您发布的代码无法编译，因为您多次重新定义变量entry。您应该在循环外部定义它，并且仅在循环中为其赋值。

• 正如其他人所提到的，Entry 类的 equals 方法过于复杂。您可以通过以下方式替换代码:

  return key.equals(obj);
  

• 您不需要 insertionOrder 列表。在 Entry 类中拥有 next 字段的全部目的是能够链接条目，以便您可以根据插入顺序迭代它们。您需要记录的只是列表的头部(第一个 Entry)以及列表的尾部(最新插入的 Entry)，以便您可以从中进行链接。

put 方法的最终结果

public void put(Object key, Object value) {
    int hashIndex = hashIndex(key);
    LinkedList<Entry> entries = table[hashIndex];

    for(Entry entry : entries) {
        if (entry.equals(key)) {
            entry.setValue(value);
            // You might want to update listTail here too
            return;
        }
    }
    Entry newEntry = new Entry(key, value);
    entries.add(newEntry);
    listTail.setNext(newEntry);
    listTail = newEntry;
}