[Java]散列表的数据结构以及对象在JVM堆中的存储过程

1、什么是“散列表”？

大家先看张图，这是我理解的“散列表”底层数据结构图。

我先大致说说 JVM 的内存结构。

JVM内存结构主要由堆、栈和方法区组成。栈主要用于存储基本数据类型变量和引用、以及引用类型变量引用等；堆主要用于存储对象和数组；方法区主要用于存储类信息和常量。

这里主要讲的是“堆”。

对象在堆中不是随意存储的，而是通过一种数据结构散列表 \color{green}{散列表}散列表进行存储（存储于散列表中）。何为散列表？它的数据结构大致如上图所示，纵向是数组，横向是链表（有些资料中也将“链表”称之为“桶” \color{green}{“桶”}“桶”），数组的每一个节点都是链表的表头。

Hash系列（如：java.util.Hashtable、java.util.HashMap）的数据结构就是散列表，下文以 Hashtable 为例。

P S PSPS：散列表的结构为何这样设计？又为何要将对象采用散列表结构进行存储？往下看。

2、关于对象存储过程

2.1 加载过程

关于创建对象方法，可参考博文《Java知识点锦集》的第3.2项。

对象创建完成，为对象在 Hashtable 中选择一个存储位置，需要使用对象的内存地址在 Hashtable 中进行检索。

• 第一步：将对象内存地址（十六进制）转化成十进制，再通过h a s h 算法 hash 算法hash算法，得到一个整型数字，即hashcode；
• 第二步：通过某种运算，得出与此对象具有相同 hashcode 的“桶”的位置（索引）；（关于“运算”，见本文末）
• 第三步：在确定“桶”后，检索，比较entry中的key，找到对象合适的存储位置后插入“桶”。

补充说明： \color{purple}{补充说明：}补充说明：

Hashtable 是一种数据结构，可以存储任何类型数据，对象只是其一。

如果 Hashtable 存储的是对象，则key存储的是内存地址，value存储的是对象。

若 Hashtable 中存储的是对象，则加载过程就是检索对象应存储位置后直接插入对象，不存在覆盖现象。

如：Hashtable，映射（有些资料也称之为“条目” \color{green}{“条目”}“条目”）是Entry。由于key可能重复，故可能会覆盖。

扩展一点： \color{brown}{扩展一点：}扩展一点：

大家可能会疑惑：使用Map时，打印key，显示的是 String，并不是你说的内存地址啊？

因为，如果key的类型是 String，如：映射Map.Entry = {"name", [对象]}，其底层（JVM中）是先在方法区的字符串常量池中创建一个字符串常量"name"，此常量对应一个内存地址，然后将此内存地址经过上文中的“加载过程”作为key存储进Map中。当我们输出key时，在底层会通过其存储的内存地址，去字符串常量池中查找，从而输出"name"。

2.2 注意事项

1. h a s h c o d e \color{green}{hashcode}hashcode的作用主要是用于在数组中，定位与对象具有相同 hashcode 的“桶”的表头位置（索引）， hashcode 本身并不存储于 Hashtable。
2. 散列表的纵向（数组）和横向（链表）的每个节点的数据类型都是entry。
   注：Hashtable 类中节点的数据类型是Map.Entry。
3. 两个不同对象的hashcode可能相同，同一个“桶”中的所有对象的hashcode都相同。
4. 散列表的纵向设计为数组是因为数组便于检索（定位具有相同hashcode的“桶”效率高），横向设计为链表是因为链表便于修改（插入、修改效率高）。
5. “桶”是双向链表 \color{red}{“桶”是双向链表}“桶”是双向链表.。两头都可以是表头，这样设计是为了提高检索对象的速度。
6. “桶”的数据结构不是一成不变的。当entry个数达到一定临界值时，“桶”会重构，从而提高检索对象性能。
   重构规则： \color{blue}{重构规则：}重构规则：当entry个数超过8个时，重构为红黑树 \color{green}{红黑树}红黑树（大家以二叉树的结构理解就行）；当小于等于6时，重构回链表。

3、Hashtable 扩容机制

先说定义：

“扩容”指扩大 Hashtable 的容量（即“桶”的个数），上面第6点中提及的“重构”指修改“桶”的数据结构，两者不要混淆。

3.1 扩容机制是什么？

Hashtable 何时扩容？这里涉及一个概念——加载因子 \color{green}{加载因子}加载因子（又名“负载因子”）。

• 每个“桶”都有一个初始entry容纳个数。
• “加载因子”指填满（“桶”中entry个数达到初始容纳个数）的“桶”的个数占 Hashtable 当前容量（指 Hashtable 的当前“桶”个数）的比例，也称之为“扩容阈值” \color{blue}{“扩容阈值”}“扩容阈值”。
• 加载因子越大，h a s h 碰撞 \color{red}{hash碰撞}hash碰撞越多，性能越低。加载因子的默认值是0.75，这是考虑到空间（内存）和时间（性能）的折中值。
  注：“hash碰撞”就是上文“加载过程”中的第二步。查找与新对象具有相同hashcode的对象所在“桶”的过程。

3.2 扩容时刻

Hashtable 的扩容时刻是：（指当 Hashtable 中entry个数达到的扩容临界值）

x * 0.75 * 8

x是当前容量，默认值为11；0.75是加载因子的默认值；8是“桶”重构的临界值。（注：当entry个数达到8个时，“桶”重构，但仍然可以继续存储，与扩容机制无关）

可实际上，一般情况下，扩容时刻会是：

x * 0.75 * 6

为什么是6，不是8？因为 Hashtable 不存在平均分配的机制，且对象的内存地址是任意的，故 hashcode 任意。

P S \color{red}{PS}PS：这两个“扩容时刻”都是一个估计值，作为理论参考。

补充说明 \color{green}{补充说明}补充说明：

Hashtable 类有一个属性threshold（扩容阈值），值为当前容量 * 加载因子，此处的“扩容时刻”即threshold与“桶”重构时平均节点数之积。

4、Hashtable 实用举例

@Override
public boolean equals(Object obj) {
    if (this.hashCode() == obj.hashCode()) {
        if (this == obj)
            return true;
        else 
            return false;
    } else
        return false;
}

使用散列表提高对象检索性能。

5、扩展

Hashtable 与 HashMap 的区别：

1. Hashtable 的默认容量为11，HashMap 的默认容量为16。
2. Hashtable 继承于 Dictionary，HashMap 继承于 AbstractMap。
3. 由于 Hashtable 是线程安全的，故效率低。因此，在多线程环境下，使用ConcurrentHashMap类；而在单线程环境下，使用 HashMap。

最后

相信这篇文章会让大家对散列表的数据结构有了初步的了解，如果大家想进一步了解其底层实现，可查阅这两篇博文：

1. Java-API简析_java.util.HashTable＜K, V＞类（基于 Latest JDK）（浅析源码）；
2. Java-API简析_java.util.HashMap＜K,V＞类（基于 Latest JDK）（浅析源码）。

本文完结。