哈希表。它是如何工作的？

Question

现在，我正在尝试了解如何构造Hashtable。

最有趣的是-当对象添加到Hashtable时会发生什么？

我在一本书中读到：

第一步： 计算对象的hashCode()。

接下来，我们确定此对象在Hashtable中的位置：obj.hashCode()％Hashtable.length。

例如，向Hashtable添加更多元素：

Hashtable<String, String> hm=new Hashtable<String, String>(100);

        hm.put("Lee","Lee");
        hm.put("lee","lee");
        hm.put("eel","eel");

定义一个存储对象的桶：

    System.out.println("Lee".hashCode() % 100);
    System.out.println("lee".hashCode() % 100);
    System.out.println("eel".hashCode() % 100);

如果我理解算法的话，对象必须按照以下方式放置在表格中：

eel /*because,"eel".hashCode() % 100=0*/, 
lee /*because, "lee".hashCode() % 100=20*/, 
Lee /*because, "Lee".hashCode() % 100=68*/

但是我们看到的结果是什么？

System.out.println(hm);

{Lee=Lee, lee=lee, eel=eel} 

请问，我哪里做错了吗？

- user471011

Answer 1

Hashtable（以及HashMap）元素的迭代顺序不受保证（取决于实现），因此我认为没有必要试图在其上建立理论。甚至可能在不同的Java版本之间发生变化（从Java5到Java6确实发生了变化）。

顺便说一下，Hashtable已经过时，建议使用（并分析）HashMap。

作为基本哈希映射实现，您的描述对我来说很好。然而，HashMap的实际实现比这要复杂得多，至少自Java4以来如此。例如，哈希表的大小始终是2的幂（对于您所描述的基本哈希表来说，这将是一个相当糟糕的决定），从键对象获取的哈希值会在内部重新哈希，以实现更加均匀地分布在表的实际大小上。有关更多详细信息，请参见Java Specialist Newsletter的以下问题：

• HashMap requires a better hashCode()
• Follow-up to JDK 1.4 HashMap hashCode() mystery

- Péter Török

---

在Java中，“它甚至可能在不同的Java版本之间发生变化。”而在Perl中，则会在程序调用之间发生变化，以防止使用哈希碰撞进行拒绝服务攻击。 - Thilo

为了防止不同的键落入同一个桶中发生冲突，需要添加额外的哈希函数。 - Dead Programmer

Answer 2

一个Hashtable是从键到值的映射。当你打印一个Hashtable时，就会显示这个映射关系。

关于.hashCode和.equals的故事是它如何在内部跟踪键/值对的粗略描述。

不过，对于你的问题有几点说明：

- 你在示例中设置的容量为100的"capacity"并不代表存储对象的桶(bucket)数量。它表示Hashtable具有.75负载因子的容量。 - 桶(bucket)的数量在运行时可能会发生变化。如果你长时间添加对象，负载因子将增加，桶(bucket)可能会被重新分配，对象会被"rehashed"。 来自文档 负载因子是哈希表在其容量自动增加之前允许填满的程度的度量。初始容量和负载因子参数仅仅是对实现的提示。关于何时以及是否调用重新哈希方法的确切细节取决于实现。

- aioobe

Answer 3

哈希表的概念是根据某个哈希函数（接受对象并返回索引）将对象添加到表中。

你对哈希表的描述只是其中之一（很多...），如果Java实现方式与你所读的方式相同，我会感到惊讶。

- Neowizard

Answer 4

如先前提到的，Hashtable 是实现相关的，我建议先了解 Hashtable 的一般概念，然后在理解其工作原理后再阅读 Java 或其他语言中的具体实现。

维基百科 上有关于这个主题的相当不错的文章，所以我建议先阅读这篇文章。

- Vitalij