Java中使用数组实现简单的HashTable？

Question

我使用数组实现了一个非常简单的HashTable，但是在使用过程中遇到了问题。问题是第一个放入HashTable中的Item总是AVAILABLE。也许你们可以看出哪里出了问题。这是HashTable类：

public class HashTable {

    private Item[] data;
    private int capacity;
    private int size;
    private static final Item AVAILABLE = new Item("Available", null);

    public HashTable(int capacity) {

        this.capacity = capacity; 
        data = new Item[capacity];
        for(int i = 0; i < data.length; i++) {

            data[i] = AVAILABLE;
        }
        size = 0;
    }

    public int size() {

        return size;
    }

    public int hashThis(String key) {

        return key.hashCode() % capacity; 
    }

    public Object get(String key) {

        int hash = hashThis(key);

        while(data[hash] != AVAILABLE && data[hash].key() != key) {

            hash = (hash + 1) % capacity;
        }
        return data[hash].element();
    }

    public void put(String key, Object element) {

        if(key != null) {
            size++;
            int hash = hashThis(key);
            while(data[hash] != AVAILABLE && data[hash].key() != key) {

                hash = (hash + 1) % capacity;
            }

            data[hash] = new Item(key, element);

        }

    }

    public Object remove(String key) {
        // not important now.
        throw new UnsupportedOperationException("Can't remove");
    }

    public String toString() {

        String s = "<HashTable[";
        for(int i = 0; i < this.size(); i++) {

            s += data[i].toString();
            if(i < this.size() - 1) {

                s += ",";
            }
        }
        s += "]>";
        return s;
    }

}

更好地理解，这是 Item 类的定义：

public class Item {

    private String key;
    private Object element;

    public Item(String key, Object element) {

        this.setKey(key);
        this.setElement(element);
    }

    public String key() {
        return key;
    }

    public void setKey(String key) {
        this.key = key;
    }

    public Object element() {
        return element;
    }

    public void setElement(Object element) {
        this.element = element;
    }

    public String toString() {

        String s = "<Item(";
        s += this.key() + "," + this.element() + ")>";
        return s;
    }

}

举个例子：

HashTable ht = new HashTable(10);
ht.put("1", "a");

toString() 的输出必须是：

"<HashTable[<Item(1,a)>]>"

但是我得到的是：

"<HashTable[<Item(Available,null)>]>"

更新：我应该提到下一个项目被正确放置，而再接下来的项目又没有放置正确。

- Loolooii

Answer 1

我认为问题出在你的toString方法中。当size = 1时，你循环0 - size只执行一次，因此你只打印出哈希表中的第一个值，而问题是哈希表中的第一个值不是真正的值，而是AVAILABLE。你需要像这样做：

编辑：抱歉，我忘记将索引移动过去了。

public String toString() {
   String s = "<HashTable[";
   int i = 0;
   int count = 0;
   while(count < this.size()) {

        //Skip the AVAILABLE cells
        if(data[i] == AVAILABLE) {
            i++;
            continue;
        }

        s += data[i].toString();
        if(count < this.size() - 1) {
            s += ",";
        }
        count++;
    }
    s += "]>";
    return s;
}

- twain249

---

@Loolooii toString 方法中的循环是什么意思？每当您有一个不是 AVAILABLE 的单元格时，i 就会增加，因此它应该在 i=size 时停止。因此，如果 size 被正确设置（看起来是这样），并且数组中有一个元素不等于 AVAILABLE，它应该停止。 - twain249

是的，toString方法里的循环。我知道，它应该停止，但不知怎么回事它就是不停止？！ - Loolooii

当我将&&更改为||时，put()中的循环也不会停止。 - Loolooii

是的，我刚刚尝试了调试：它进入了第一个if语句，然后在执行continue之后返回到while条件，并一直这样做。因此，data [i]始终是AVAILABLE。 - Loolooii

@Loolooii 我知道为什么了，是我的错。我会把它修复。 - twain249

Answer 2

如果您仍然对解决方案感兴趣，请尝试使用以下toString()方法，我已经运行过了，它很好：

public String toString()
{
    String s = "<HashTable[";
    for (int i = 0; i < this.capacity; i++)
    {
        if (data[i].Element != null)
        {
            s += data[i].toString();
            if (i < this.size - 1)
            {
                s += ",";
            }
         }
     }
     s += "]>";
     return s;
}

- varshnes