0

我试图了解 Java 中的实现 HashTables。下面是我的代码：

    Hashtable<Integer, String> hTab = new Hashtable<Integer, String>();
    hTab.put(1, "A");
    hTab.put(1, "B");
    hTab.put(2, "C");
    hTab.put(3, "D");

            Iterator<Map.Entry<Integer, String>> itr = hTab.entrySet().iterator();
    Entry<Integer, String> entry;

    while(itr.hasNext()){
        entry = itr.next();
        System.out.println(entry.getValue());
    }

当我运行它时，我得到以下输出：D C B

这意味着 Key = 1 发生了冲突；并根据实施：

“每当哈希表中发生冲突时，都会在与特定存储桶对应的linkedList中创建一个新节点，并将EntrySet（Key，Value）对存储为列表中的节点，新值插入到列表的开头对于特定的桶”。我完全同意这个实施。

但如果这是真的，那么当我尝试从 hashTable 中检索条目集时，“A”去了哪里？

同样，我尝试使用下面的代码通过实现我自己的 HashCode 和 equals 方法来理解这一点。令人惊讶的是，这非常完美，并且符合 HashTable 实现。下面是我的代码：

public class Hash {

    private int key;

    public Hash(int key){
        this.key = key;
    }

    public int hashCode(){
        return key;
    }

    public boolean equals(Hash o){
        return this.key == o.key;

    }

    }

    public class HashTable1 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        Hashtable<Hash, String> hTab = new Hashtable<Hash, String>();

        hTab.put(new Hash(1), "A");
        hTab.put(new Hash(1), "B");
        hTab.put(new Hash(2), "C");
        hTab.put(new Hash(3), "D");

        Iterator<Map.Entry<Hash, String>> itr = hTab.entrySet().iterator();
        Entry<Hash, String> entry;

        while(itr.hasNext()){
            entry = itr.next();
            System.out.println(entry.getValue());
        }
    }
}

输出：D C B A

这是完美的。我无法理解 Java 中 HashTable 行为的这种歧义。

更新

@garrytan 和@Brian：感谢您的回复。但我还有一个小小的疑问。

在我的第二个代码中，它工作正常。我创建了两个对象，它们是新键，因为它们是 2 个对象，在这种情况下不会发生键冲突，并且工作正常。我同意你的解释。但是，如果在第一组代码中我使用“new Integer(1)”而不是简单的“1”，它仍然不起作用，尽管现在我正在创建 2 个对象并且它们应该不同。我通过写下面的简单行进行了交叉检查：

            Integer int1 = new Integer(1);
            Integer int2 = new Integer(1);
            System.out.println(int1 == int2);

这给出了“错误”。这意味着现在，密钥冲突应该已经解决了。但它仍然不起作用。为什么是这样？

4

3 回答 3

4

按照设计，哈希表并不意味着存储重复的键。

我认为您在“哈希冲突”和“密钥冲突”之间混淆了。简单地说，哈希表由一组链表（即：桶）组成。当您添加新的键值对 (KVP) 时，它会通过键的哈希值分配到存储桶中。当两个键产生相同的哈希时会发生“哈希冲突”（因此它们被放入同一个桶中）

一个好的散列函数是将密钥均匀地分配到多个桶中，从而提高密钥搜索性能。

于 2013-01-10T06:31:53.597 回答
1

第二个示例给出了您想要的行为，因为您的 equals 实现不正确。

签名是

public boolean equals(Object o) {}

不是

public boolean equals(Hash h) {}

所以你创建的是一个哈希碰撞，其中两个对象具有相同的哈希码（键），但是根据equals方法它们不相等（因为你的签名是错误的，它仍然使用==运算符而不是你的this .key == h.key 代码）。与键冲突相反，在第一个示例中，对象都具有相同的 hashCode 并且也相等。如果您修复第二个示例中的代码以实现实际equals(Object o)方法，您将看到值中再次缺少“A”。

于 2013-01-10T06:57:01.363 回答
0

在您的第二个示例中，您没有覆盖原始 equals 函数，因为您使用以下签名：

public boolean equals(Hash h) {}

因此，仍然使用以 Object 作为参数的原始 equals 函数，并且当您为每个插入创建一个新对象哈希时，该 Object 与另一个不同，因此 A 和 B 的键不相等。

此外，HashTable 设计为每个键都有一个值。并且键确实是依靠equals函数来进行比较的。

关于您使用两个新整数的示例，请尝试将它们与 .equals() 进行比较。您还可以重写 hashCode 函数来为每个对象生成或不生成不同的 hashCode，即取决于时间，但这不是一个好的编码原则。相同的对象应该散列到相同的代码。

于 2013-01-10T07:05:05.190 回答