java 哈希表。怎么运行的？

Hashtable. How it works?

提问by user471011

Now, I'm trying to understand how to construct the Hashtable.

现在，我试图了解如何构建Hashtable.

The most interesting - as objects are added to the Hashtable?

最有趣的 - 将对象添加到Hashtable?

I have read in a book that:

我在一本书中读到：

at first step: Calculated hashCode()object.

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

Next, we determine the position of this object in the Hashtable: obj.hashCode() % Hashtable.length.

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

For example, add more elements to the Hashtable:

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

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

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

Define a bucket into which is placed the object:

定义一个放置对象的桶：

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

If I understand the algorithm, the objects must be placed in the table as follows:

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

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

but what we see as a result?

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

System.out.println(hm);

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

Please, tell me, where did I go wrong?

请告诉我，我哪里做错了？

回答by Péter T?r?k

The iteration order of Hashtable(as well as HashMap) elements is not guaranteed (implementation dependent), so IMHO there is not much point trying to build a theory on it. It may even change between different Java versions (it did change from Java5 to Java6).

不保证（Hashtable以及HashMap）元素的迭代顺序（取决于实现），所以恕我直言，试图在其上建立理论并没有多大意义。它甚至可能在不同的 Java 版本之间发生变化（它确实从 Java5 更改为 Java6）。

Btw Hashtableis obsolete, it is recommended to use (and analyse) HashMapinstead.

顺便说一句Hashtable，已经过时了，建议改用（和分析）HashMap。

Your description sounds OK to me as a basic hash map implementation. However, the actual implementation of HashMapis quite a bit more sophisticated than that, at least since Java4. E.g. the size of the hash table is always a power of two (which would be quite a bad decision for a basic hashtable like you describe), and hash values got from the key objects are rehashed internally to achieve a more even distribution over the actual size of the table. For more details on this, see the following issues of the Java Specialist Newsletter:

您的描述在我看来是基本的哈希映射实现。然而， 的实际实现HashMap比这复杂得多，至少从 Java4 开始。例如，哈希表的大小始终是 2 的幂（对于像您描述的基本哈希表来说，这将是一个非常糟糕的决定），并且从关键对象获得的哈希值在内部重新散列，以实现更均匀的分布。桌子的大小。有关这方面的更多详细信息，请参阅 Java 专家通讯的以下问题：

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

• HashMap 需要更好的 hashCode()
• JDK 1.4 HashMap hashCode() 之谜的后续

回答by aioobe

A Hashtable is a mapping from keys to values. It is this mapping that is shown when you print a Hashtable.

哈希表是从键到值的映射。打印哈希表时会显示此映射。

The story about .hashCodeand .equalsis a rough description of how it manages to keep track of the key/value pairs internally.

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

A few remarks on your question though:

不过，对您的问题有几点意见：

• The capacitythat you set to 100 in your example, does not represent the number of bucketsto store objects in. It represents the number of objects the Hashtable has capacity for, with a load factor of .75.

• The number of buckets may vary during runtime. If you keep adding objects for a long time, the load factor will be increased, and the buckets may be reallocated and the objects "rehashed".

• 在capacity您在例如设置为100，并不代表桶的数量在存储中的对象。它代表的对象的数量Hashtable中有能力，有0.75的负载因数。

• 运行时桶的数量可能会有所不同。如果长时间不断添加对象，负载因子将增加，并且可能会重新分配桶和对象“重新散列”。

From the docs:

从文档：

The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. The initial capacity and load factor parameters are merely hints to the implementation. The exact details as to when and whether the rehash method is invoked are implementation-dependent.

负载因子是衡量哈希表在其容量自动增加之前允许达到多满的指标。初始容量和负载系数参数只是对实现的提示。关于何时以及是否调用 rehash 方法的确切细节取决于实现。

回答by Neowizard

The concept of hashtable is to add the objects into the table acording to some hash function (takes object and returns an index).

哈希表的概念是根据一些哈希函数（获取对象并返回索引）将对象添加到表中。

Your description of a hashtable is just one of many (many...), and I'd be surprised if it was implemented in Java the same way you read.

您对哈希表的描述只是众多（许多...）中的一个，如果它以与您阅读的方式相同的方式在 Java 中实现，我会感到惊讶。

回答by Vitalij

As previously mentioned Hashtable is implementation dependent and I would reccomend to read about the Hashtable in general, to get the idea of how they work and then after understanding how it works to read about specific implementation in Java or other language.

如前所述，Hashtable 依赖于实现，我建议您阅读有关 Hashtable 的一般信息，以了解它们的工作原理，然后在了解它的工作原理后阅读 Java 或其他语言中的特定实现。

Wikipediahas quite a good article on this topic, so I suggest read this first.

维基百科在这个主题上有一篇很好的文章，所以我建议先阅读这篇文章。