7

我正在阅读关于 Hashtable 类的 Java api 文档并遇到了几个问题。在文档中，它说“注意哈希表是打开的：在“哈希冲突”的情况下，单个存储桶存储多个条目，必须按顺序搜索。 ”我自己尝试了以下代码

Hashtable<String, Integer> me = new Hashtable<String, Integer>();
me.put("one", new Integer(1));
me.put("two", new Integer(2));
me.put("two", new Integer(3));
System.out.println(me.get("one"));  
System.out.println(me.get("two"));

输出是

1
3
  1. 这就是“开放”的意思吗？
  2. 整数 2 发生了什么？作为垃圾收集？
  3. 有没有“封闭”的例子？
4

6 回答 6

12

不，这不是“开放”的意思。

请注意密钥冲突和哈希冲突之间的区别。

Hashtable 将不允许多个条目具有相同的键（如在您的示例中，您使用键“two”放置了两个条目，第二个 (3) 替换了第一个 (2)，而您只剩下哈希表中的第二个）。

哈希冲突是指两个不同的键具有相同的哈希码（由它们的 hashCode() 方法返回）。不同的哈希表实现可以以不同的方式处理这个问题，主要是在低级实现方面。作为“开放”，Hashtable 将存储其键散列到相同值的条目的链接列表。在最坏的情况下，这可能会导致简单操作的 O(N) 性能，通常在散列映射中是 O(1)，其中散列主要是不同的值。

于 2009-08-17T15:49:45.910 回答
3

这意味着具有相同哈希码的具有不同键的两个项目最终位于同一个桶中。

在您的情况下，键“两个”是相同的，因此第二个 put 会覆盖第一个。

但是假设你有自己的班级

class Thingy {
    private final String name;

    public Thingy(String name) {
         this.name = name;
    }

    public boolean equals(Object o) {
        ...

    }

    public int hashcode() {
       //not the worlds best idea
       return 1;
    }

}

并创建了它的多个实例。IE

Thingy a = new Thingy("a"); 
Thingy b = new Thingy("b"); 
Thingy c = new Thingy("c");

并将它们插入到地图中。然后一个桶，即包含哈希码为 1 的东西的桶将包含三个项目的列表（链）。

Map<Thingy, Thingy> map = new HashMap<Thingy, Thingy>();
map.put(a, a);
map.put(b, b);
map.put(c, c);

因此，通过任何 Thingy 键获取项目将导致查找哈希码 O(1)，然后在哈希码为 1 的桶中的项目列表上进行线性搜索 O(n)。

在实现 hashcode 和 equals 时还要注意确保遵循正确的关系。也就是说，如果两个对象相等，那么它们应该具有相同的哈希码，但不一定相反，因为多个键可能会获得相同的哈希码。

哦，关于开放散列和封闭散列表的完整定义，请看这里http://www.c2.com/cgi/wiki?HashTable

于 2009-08-17T15:54:57.273 回答
2

这意味着 Hashtable 使用开放散列（也称为分离链）来处理散列冲突。如果两个单独的键具有相同的哈希码，则它们都将存储在同一个桶中（在列表中）。

于 2009-08-17T15:53:21.253 回答
2

开放意味着如果两个键不相等，但具有相同的哈希值，那么它们将被存储在同一个“桶”中。在这种情况下，您可以将每个存储桶视为一个链表，因此如果在同一个存储桶中存储了很多东西，搜索性能就会下降。

桶 0：无
桶 1：项目 1
桶 2：项目 2 -> 项目 3
桶 3：无
桶 4：项目 4

在这种情况下，如果您搜索散列到存储桶 2 的键，则必须在列表上执行 O(n) 搜索以找到与您正在搜索的键相同的键。如果密钥散列到桶 0、1、3 或 4，那么您将获得 O(1) 的搜索性能。

于 2009-08-17T15:54:16.633 回答
1

哈希是一个计算函数，它将一个对象（示例中的“一”或“二”）映射到（在本例中）一个整数。这意味着可能有多个值映射到同一个整数（一个整数具有有限数量的允许值，而可能有无限数量的输入）。在这种情况下，“等于”必须能够区分这两个。所以你的代码示例是正确的，但可能有一些其他键具有相同的哈希码（并将与“两个”放在同一个桶中）

于 2009-08-17T15:49:00.637 回答
1

警告：常用的“开放散列”定义相互矛盾：

引用另一个答案中引用的http://www.c2.com/cgi/wiki?HashTable ：

注意：有些人使用术语“开放散列”来表示我在这里所说的“封闭散列”！此处的用法与 TheArtOfComputerProgramming 和 IntroductionToAlgorithms 中的用法一致，如果您想了解更多关于哈希表的信息，建议参考这两篇文章。

例如，上面的页面定义“开放哈希”如下：

有两种主要策略。开放式哈希，也称为开放式寻址， 表示：当新键/值对所需的表条目已被占用时，以某种方式找到另一个未使用的条目并将其放在那里。封闭散列表示：表中的每个条目都是包含实际数据的二级数据结构（通常是链表，但也有其他可能），并且这种数据结构可以无限扩展。

相比之下，维基百科提供的定义是：

在称为分离链、直接链或简单链的策略中，桶数组的每个槽都是指向链表的指针，链表包含散列到同一位置的键值对。查找需要扫描列表以查找具有给定键的条目。插入需要将新条目记录附加到散列槽中列表的任一端。删除需要搜索列表并删除元素。（该技术也称为开放式哈希或封闭式寻址，不应与“开放式寻址”或“封闭式哈希”混淆。）

如果所谓的“专家”不能同意“开放哈希”一词的含义，最好避免使用它。

于 2009-08-17T23:06:23.890 回答