Java面试八股文宝典:初识数据结构-数组的应用扩展之HashTable

前言

上一章我们了解 HashMap 后，让我们深入研究 HashTable，这是另一个键值对存储的数据结构。Hash表是一个非常重要且广泛用于编程中的数据结构，了解其工作原理和用法对于编写高效的程序非常重要。

简述

HashTable 是 Java 中的一个古老的哈希表实现，它在 Java 的早期版本中被引入。虽然它在新的 Java 版本中不太常用，但仍然值得了解其内部实现。
HashTable 使用一个哈希函数将键映射到存储桶（buckets ）中，并在每个桶中存储一个键值对，通过键来快速查找和检索对应的值。Hash表的核心思想是将键通过哈希函数映射到一个桶（bucket ）的索引位置，然后将值存储在该桶中。这个过程使得我们可以以常数时间复杂度 O(1) 来查找值。每个桶实际上是一个链表，用于处理哈希冲突。当多个键映射到同一个桶时，它们会以链表的形式存储在该桶中。如果链表变得太长，性能会下降，因此 HashTable 需要定期进行 rehash 操作来重新分配键值对到新的桶中，以保持性能。

示例代码 - 使用 HashTable

让我们看一下如何使用 HashTable 存储和检索数据：

// 创建一个 HashTable
Hashtable<String, Integer> scores = new Hashtable<>();

// 插入键值对
scores.put("Alice", 95);
scores.put("Bob", 88);
scores.put("Charlie", 92);

// 检索值
int aliceScore = scores.get("Alice"); // 获取 Alice 的成绩
1
2
3
4
5
6
7
8
9
10

HashTable 的底层实现

HashTable 的底层实现与 HashTable 类似，它们都使用哈希表（数组 + 链表或红黑树）来存储键值对。当我们插入或查找键值对时，它们都会使用哈希函数计算键的索引，然后在对应的桶中执行操作。这使得查找操作非常高效。

1.主要代码片段

以下是 HashTable 的主要代码片段，我会添加注释来解释其关键部分。

public class Hashtable<K,V> extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {

    // 哈希表的默认初始容量
    private static final int DEFAULT_INITIAL_CAPACITY = 11;

    // 哈希表的默认负载因子
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 哈希表的键值对数量
    private transient int count;

    // 哈希表的容量
    private int threshold;

    // 哈希表的装载因子
    private float loadFactor;

    // 存储键值对的数组，每个元素是一个链表头
    private transient Entry<?,?>[] table;

    // 哈希表结构发生变化的次数，用于支持快速失败机制
    private transient int modCount;

    // ...

    // 内部类，表示键值对的节点
    private static class Entry<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Entry<K,V> next;

        // ...
    }

    // 构造函数，初始化哈希表
    public Hashtable(int initialCapacity, float loadFactor) {
        // ...
    }

    // 计算键的哈希码
    private static int hash(int h) {
        // ...
    }

    // 扩容哈希表
    protected void rehash() {
        // ...
    }

    // 在哈希表中查找键对应的值
    public synchronized V get(Object key) {
        // ...
    }

    // 在哈希表中插入键值对
    public synchronized V put(K key, V value) {
        // ...
    }

    // ...

    // 内部方法，用于枚举哈希表中的键
    private static class Enumerator<K,V> implements Enumeration<K>, Iterator<K> {
        // ...
    }

    // ...

    // 复制哈希表
    public synchronized Object clone() {
        // ...
    }

    // ...

    // 其他方法，如remove, contains, clear, keys, values, size 等
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

2. put 方法

put 方法用于向 HashTable 中插入键值对：

public synchronized V put(K key, V value) {
    // 省略部分代码
    // 计算哈希值，找到对应桶的索引
    int hash = hash(key);
    int index = (hash & 0x7FFFFFFF) % tab.length;

    // 遍历链表或红黑树，查找是否已经存在相同的键
    for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            V old = e.value;
            e.value = value;
            return old;
        }
    }

    // 如果不存在相同的键，将新键值对插入到桶的头部
    addEntry(hash, key, value, index);
    return null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3. get 方法

get 方法用于根据键查找值：

public synchronized V get(Object key) {
    // 省略部分代码
    // 计算哈希值，找到对应桶的索引
    int hash = hash(key);
    int index = (hash & 0x7FFFFFFF) % tab.length;

    // 遍历链表或红黑树，查找键值对
    for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return e.value;
        }
    }
    return null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4. remove 方法

remove 方法用于根据键删除键值对：

public synchronized V remove(Object key) {
    // 省略部分代码
    // 计算哈希值，找到对应桶的索引
    int hash = hash(key);
    int index = (hash & 0x7FFFFFFF) % tab.length;

    // 遍历链表或红黑树，查找并删除键值对
    for (Entry<K,V> e = tab[index], prev = null; e != null; prev = e, e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            // 从桶中移除键值对
            modCount++;
            if (prev != null) {
                prev.next = e.next;
            } else {
                tab[index] = e.next;
            }
            count--;
            V oldValue = e.value;
            e.value = null;
            return oldValue;
        }
    }
    return null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

5.迭代器

HashTable 的迭代器是线程安全的，可以在迭代过程中修改 HashTable，不会引发异常。示例：

Hashtable<String, Integer> scores = new Hashtable<>();
scores.put("Alice", 95);
scores.put("Bob", 88);

for (Map.Entry<String, Integer> entry : scores.entrySet()) {
    if (entry.getKey().equals("Alice")) {
        scores.put("Alice", 100); // 在迭代过程中修改 HashTable
    }
    System.out.println(entry.getKey() + ": " + entry.getValue());
}
1
2
3
4
5
6
7
8
9
10

6. rehash 方法

HashTable 的 rehash 原理可以概括如下：

1. 初始化：当创建一个新的 HashTable 实例时，它会分配一定数量的桶（通常是默认大小的素数）。这些桶会存储键值对，每个桶可以存储多个键值对。

2. 插入操作：当执行插入操作时，HashTable 首先使用哈希函数确定键应该存储在哪个桶中。然后，它将键值对插入到相应的桶中。如果该桶中已经存在键值对，它会将新键值对追加到链表的末尾。

3. Rehash 触发：当 HashTable 中的键值对数量达到一定阈值（通常是桶数量的 75%）时，触发 rehash 操作。这个阈值被称为负载因子。

4. Rehash 过程：在 rehash 过程中，HashTable 将创建一个新的更大的桶数组。新的桶数量通常是原来的两倍。然后，它会遍历旧桶数组中的每个桶，将其中的键值对重新分配到新的桶数组中，根据它们的哈希值重新计算它们应该存储的位置。这个过程可能会导致链表被重新排列，以便更均匀地分布键值对。

5. 完成 Rehash：一旦所有键值对都被重新分配到新的桶数组中，旧的桶数组会被丢弃，完成了 rehash 过程。

6. 继续操作：在 rehash 过程中，HashTable 仍然可以处理其他操作，例如查询和删除。但是，新的插入操作可能需要等待 rehash 完成。

以下是 HashTable 的部分 rehash 源码分析。请注意，HashTable 是一个古老的类，不建议在新代码中使用，但仍然有助于理解其内部工作原理。

private void rehash() {
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;

    // 计算新的桶数组大小，通常是原来的两倍
    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            // Keep running with MAX_ARRAY_SIZE buckets
            return;
        newCapacity = MAX_ARRAY_SIZE;
    }
    
    // 创建新的桶数组
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
    
    modCount++;
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;

    // 重新分配旧桶中的键值对到新桶数组中
    for (int i = oldCapacity ; i-- > 0 ;) {
        for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
            Entry<K,V> e = old;
            old = old.next;

            // 计算新的桶索引并插入到新的桶中
            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = (Entry<K,V>)newMap[index];
            newMap[index] = e;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

这段代码展示了 HashTable 的 rehash 过程：

• 首先，计算新的桶数组大小 newCapacity，通常是原来的两倍，并确保不会超过 MAX_ARRAY_SIZE。

• 创建新的桶数组 newMap。

• 更新 threshold，它表示下一次触发 rehash 的阈值。

• 遍历旧的桶数组，将每个桶中的键值对重新分配到新的桶数组中，根据它们的哈希值计算新的桶索引。

• 最后，更新 table，将旧的桶数组替换为新的桶数组。

这样就完成了 HashTable 的 rehash 过程，以保持性能并维护负载因子。需要注意的是，HashTable 的 rehash 过程是同步的，因此可能会影响其他线程的操作，需要小心使用。在现代 Java 中，推荐使用 HashMap 或 ConcurrentHashMap，它们提供更好的性能和灵活性。

上述代码摘录展示了 HashTable 类的关键部分。它使用了一个数组来存储键值对，每个数组元素是一个链表的头节点，解决哈希冲突。哈希表的扩容、查找、插入等操作都有对应的方法来实现。

需要注意的是，HashTable 是线程安全的，但性能不如后续引入的 ConcurrentHashMap，因为 HashTable 使用了全表锁来保证线程安全。在多线程环境中，通常建议使用 ConcurrentHashMap 来获得更好的性能。

此外，HashTable 在现代 Java 中很少使用，因为它的功能有限，不支持 null 键和值，而且性能相对较差。通常情况下，推荐使用 HashMap 或 ConcurrentHashMap 来替代 HashTable。

特性与注意事项

在使用 HashTable 时，HashTable 和 HashTable 之间有一些重要的区别，有一些重要的注意事项，特别是在多线程环境下。以下是一些关键的注意事项：

1. 线程安全性：HashTable 是线程安全的数据结构，所有公共方法都是同步的。这意味着多个线程可以同时访问和修改 HashTable 的内容而不会出现数据不一致的情况。但要注意，虽然它是线程安全的，但性能相对较低，不适用于高度并发的场景。

2. null 键和值：HashTable 不允许键或值为 null。如果尝试将 null 键或值放入 HashTable，将会抛出 NullPointerException。这一点与 HashMap 不同，后者允许键和值都为 null。

3. 遍历：在遍历 HashTable 时，可以使用迭代器或枚举器。请注意，在遍历期间修改 HashTable 的结构可能会导致 ConcurrentModificationException 异常。

4. 初始化容量和负载因子：与 HashMap 类似，HashTable 也有初始容量和负载因子的概念。可以在构造函数中指定这些参数，以适应不同的应用场景。

5. 性能考虑：HashTable 在多线程环境下提供了线程安全，但其性能可能相对较低。如果需要更高性能的线程安全哈希表，可以考虑使用 ConcurrentHashMap。

6. 不建议使用：尽管 HashTable 是一个线程安全的数据结构，但由于其性能相对较差，不允许 null 键和值，以及其他限制，通常不建议在新的 Java 代码中使用它。更常见的做法是使用 HashMap 或 ConcurrentHashMap，根据需求选择合适的实现。

总的来说，HashTable 是一个古老而受限的数据结构，虽然它具有线程安全性，但在现代 Java 中有更好的替代方案。在编写新的 Java 代码时，通常建议选择更现代的线程安全哈希表实现，以获得更好的性能和更多的灵活性。

结语

HashTable 是一个重要的哈希数据结构，用于存储键值对。它具有快速查找、线程安全、不允许 null 键和值等特性。了解其底层实现和用法对于编写高效且安全的程序至关重要。在使用 HashTable 时，请注意线程安全性和性能方面的考虑，并根据实际需求进行调整。

下一章我们将继续探讨其他数据结构，包括 ConcurrentHashMap、HashSet、LinkedHashMap 。这些数据结构在特定的应用场景中发挥了重要作用，它们具有不同的特性和性能特点，我将详细介绍它们的使用方法、优势以及适用的情况。如果您在这些内容中发现任何不准确或需要进一步说明的地方，欢迎提出，我将尽力提供准确和有用的信息。让我们共同学习，共同进步。