Java 158°C 20-01-2025

^{最近更新于：2025-01-20 18:24:30}

在 Java 中，哈希表（Hashtable）是通过哈希算法将键（key）映射到对应的值（value）的一种数据结构。哈希表内部通常使用一个数组，并通过一个哈希函数将键值映射到数组的索引位置。如果多个键的哈希值相同，则发生冲突，这时可以采用不同的冲突解决方法，常见的有链地址法和开放地址法。

一、创建哈希表

Java 标准库提供了 Hashtable 类，它实现了 Map 接口。Hashtable 是线程安全的，但相较于 HashMap，它的性能较差，因为 Hashtable 在每个操作上都有同步控制。

代码示例

import java.util.Hashtable;

public class HashTableExample {
    public static void main(String[] args) {
        // 创建一个哈希表
        Hashtable<String, Integer> hashTable = new Hashtable<>();

        // 插入数据
        hashTable.put("One", 1);
        hashTable.put("Two", 2);
        hashTable.put("Three", 3);

        // 查找数据
        System.out.println("Value for key 'Two': " + hashTable.get("Two"));

        // 删除数据
        hashTable.remove("One");

        // 遍历哈希表
        System.out.println("\nContents of the hash table:");
        for (String key : hashTable.keySet()) {
            System.out.println(key + ": " + hashTable.get(key));
        }

        // 检查键是否存在
        if (hashTable.containsKey("Three")) {
            System.out.println("\nKey 'Three' exists in the hash table.");
        }
    }
}

代码讲解

创建哈希表:
使用 Hashtable<String, Integer> hashTable = new Hashtable<>(); 创建了一个哈希表，键是字符串类型，值是整数类型。
插入数据:
通过 put(K key, V value) 方法插入键值对。例如，hashTable.put("One", 1); 将键 “One” 和值 1 插入哈希表。
查找数据:
通过 get(K key) 方法查找给定键的对应值。如果键存在，则返回值；否则返回 null。
删除数据:
通过 remove(Object key) 方法删除指定键对应的键值对。例如，hashTable.remove("One"); 删除了键为 “One” 的键值对。
遍历哈希表:
使用 keySet() 方法获取哈希表中所有键的集合，并通过增强型 for 循环遍历这些键，然后使用 get(K key) 获取对应的值。
检查键是否存在:
通过 containsKey(Object key) 方法检查哈希表中是否包含指定的键。

二、常见哈希表操作及其实现

1. 扩展哈希表（Resizing / Rehashing）

哈希表在插入元素时，如果负载因子（表中元素数量与表的总大小之比）超过某个阈值，就需要扩展哈希表的大小。这是为了保持哈希表的查找、插入操作的平均时间复杂度为 O(1) 。

实现说明

负载因子：负载因子一般设置为 0.75（即哈希表被填满 75% 时进行扩展），当哈希表的元素数量超过负载因子时，哈希表需要扩展，通常是将哈希表的大小扩大两倍。
重新哈希：在扩展哈希表时，需要重新计算所有元素的哈希值并重新分配到新的哈希表中。

扩展哈希表的代码示例：

// 自定义哈希表类，支持泛型键（K）和值（V）
class CustomHashTable<K, V> {
    // 嵌套的 Entry 类，用于存储键值对以及链表的下一个节点
    private static class Entry<K, V> {
        K key;          // 键
        V value;        // 值
        Entry<K, V> next; // 指向下一个 Entry 的指针（用于解决哈希冲突）

        // 构造函数，初始化键和值
        Entry(K key, V value) {
            this.key = key;
            this.value = value;
            this.next = null;
        }
    }

    // 哈希表的底层存储结构，一个 Entry 数组
    private Entry<K, V>[] table;
    // 当前哈希表中存储的键值对数量
    private int size;
    // 哈希表的扩容阈值
    private int threshold;

    // 构造函数，初始化哈希表的容量和负载因子
    public CustomHashTable(int initialCapacity) {
        // 初始化 Entry 数组
        table = new Entry[initialCapacity];
        size = 0; // 当前存储的键值对数量为 0
        // 设置阈值为容量的 75%（负载因子为 0.75）
        threshold = (int) (initialCapacity * 0.75);
    }

    // 计算键的哈希值，并将其映射到数组索引
    private int hash(K key) {
        // 使用键的 hashCode 方法计算哈希值，取绝对值后对数组长度取模
        return Math.abs(key.hashCode()) % table.length;
    }

    // 扩容方法，当哈希表的负载因子超过阈值时调用
    private void resize() {
        // 创建一个新的 Entry 数组，容量为原数组的两倍
        Entry<K, V>[] newTable = new Entry[table.length * 2];
        // 计算新的阈值
        threshold = (int) (newTable.length * 0.75);

        // 遍历原数组，将所有键值对重新映射到新数组
        for (int i = 0; i < table.length; i++) {
            Entry<K, V> entry = table[i];
            while (entry != null) {
                // 计算当前键在新数组中的索引
                int index = Math.abs(entry.key.hashCode()) % newTable.length;
                // 将当前 Entry 插入到新数组的对应位置
                Entry<K, V> nextEntry = entry.next;
                entry.next = newTable[index];
                newTable[index] = entry;
                entry = nextEntry;
            }
        }
        // 将新数组替换为原数组
        table = newTable;
    }

    // 向哈希表中插入键值对
    public void put(K key, V value) {
        // 如果当前负载因子超过阈值，则扩容
        if (size >= threshold) {
            resize();
        }

        // 计算键的哈希值，确定存储位置
        int index = hash(key);
        Entry<K, V> newEntry = new Entry<>(key, value);

        // 如果该位置为空，直接插入
        if (table[index] == null) {
            table[index] = newEntry;
        } else {
            // 如果该位置已有键值对，将新键值对追加到链表末尾
            Entry<K, V> current = table[index];
            while (current.next != null) {
                current = current.next;
            }
            current.next = newEntry;
        }
        size++; // 增加键值对数量
    }

    // 根据键获取对应的值
    public V get(K key) {
        // 计算键的哈希值，确定存储位置
        int index = hash(key);
        Entry<K, V> current = table[index];

        // 遍历链表，查找匹配的键
        while (current != null) {
            if (current.key.equals(key)) {
                return current.value; // 返回对应的值
            }
            current = current.next;
        }
        return null; // 如果找不到键，返回 null
    }

    // 从哈希表中删除指定键的键值对
    public void remove(K key) {
        // 计算键的哈希值，确定存储位置
        int index = hash(key);
        Entry<K, V> current = table[index];
        Entry<K, V> prev = null;

        // 遍历链表，查找匹配的键
        while (current != null) {
            if (current.key.equals(key)) {
                // 如果找到匹配的键，调整链表指针以删除该节点
                if (prev == null) {
                    // 如果删除的是链表头部节点
                    table[index] = current.next;
                } else {
                    // 如果删除的是链表中间或尾部节点
                    prev.next = current.next;
                }
                size--; // 减少键值对数量
                return;
            }
            prev = current; // 更新前驱节点
            current = current.next; // 继续遍历
        }
    }
}

代码说明：

哈希表的实现方式：
- 使用拉链法（Separate Chaining）解决哈希冲突，即每个数组位置存储一个链表。
- 当多个键映射到同一个索引时，它们会被存储在同一个链表中。
动态扩容机制：
- 当哈希表的负载因子（size / table.length）超过阈值（0.75）时，会将数组扩容为原来的两倍，并重新映射所有键值对。
基本操作：
- put(K key, V value)：插入或更新键值对。
- get(K key)：根据键获取值。
- remove(K key)：删除指定键的键值对。
哈希函数：
- 使用键的 hashCode() 方法计算哈希值，并通过取模操作将其映射到数组索引。

注意事项：

扩容操作的复杂度较高 O(n) ，但通过合理设置负载因子，可以平衡时间和空间效率。

2. 获取所有键值对

有时候我们需要遍历整个哈希表并获得所有的键值对，这对于进行一些批量操作或调试非常有用。

实现代码：

// 打印哈希表中所有键值对的方法
public void printAll() {
    // 遍历底层存储数组的每一个位置
    for (int i = 0; i < table.length; i++) {
        // 获取当前索引位置的链表头节点
        Entry<K, V> current = table[i];
        // 遍历当前链表
        while (current != null) {
            // 打印当前节点的键和值
            System.out.println(current.key + ": " + current.value);
            // 移动到链表的下一个节点
            current = current.next;
        }
    }
}

代码说明：

遍历底层存储数组：
- 使用 for 循环遍历哈希表的底层存储数组 table 的每一个索引位置。
遍历链表：
- 对于每个索引位置，获取链表的头节点 current 。
- 使用 while 循环遍历链表，直到链表的末尾（current == null）。
打印键值对：
- 在遍历链表的过程中，使用 System.out.println() 打印当前节点的键和值，格式为 key: value 。
链表的遍历逻辑：
- 每次循环中，通过 current = current.next 移动到链表的下一个节点，直到链表结束。

示例：

假设哈希表中有以下键值对：

键 "A"，值 1
键 "B"，值 2
键 "C"，值 3

调用 printAll() 方法后，输出可能如下：

A: 1
B: 2
C: 3

注意事项：

该方法的时间复杂度为 O(n) ，其中 n 是哈希表中存储的键值对总数。（因为需要遍历整个哈希表的所有链表）
如果哈希表的某些索引位置为空（即没有键值对），则不会有任何输出。

3. 键存在性检查

除了使用 get() 方法查找值之外，我们有时候会只关心某个键是否存在，可以通过 containsKey() 方法进行检查。

实现代码：

// 检查哈希表中是否包含指定键的方法
public boolean containsKey(K key) {
    // 计算键的哈希值，确定其在哈希表中的索引位置
    int index = hash(key);

    // 获取该索引位置的链表头节点
    Entry<K, V> current = table[index];

    // 遍历链表，查找是否存在与指定键相等的节点
    while (current != null) {
        // 如果当前节点的键与目标键相等，返回 true
        if (current.key.equals(key)) {
            return true;
        }
        // 移动到链表的下一个节点
        current = current.next;
    }

    // 如果遍历完整个链表仍未找到匹配的键，返回 false
    return false;
}

代码说明：

计算哈希值：
- 使用 hash(key) 方法计算键的哈希值，并确定其在哈希表数组中的索引位置。
获取链表头节点：
- 根据计算出的索引，获取对应位置的链表头节点 current 。
链表遍历：
- 使用 while 循环遍历链表，直到链表结束（current == null）。
键的比较：
- 在遍历过程中，使用 current.key.equals(key) 比较当前节点的键是否与目标键相等。
- 如果找到匹配的键，返回 true 。
返回结果：
- 如果遍历完整个链表仍未找到匹配的键，返回 false 。

示例：

假设哈希表中有以下键值对：

键 "A"，值 1
键 "B"，值 2

调用 containsKey("A") 时，返回 true，因为键 "A" 存在于哈希表中。
调用 containsKey("C") 时，返回 false，因为键 "C" 不存在于哈希表中。

注意事项：

平均情况下，时间复杂度为 O(1)，因为哈希表的查找效率较高。
在最坏情况下（所有键都映射到同一个索引，形成很长的链表），时间复杂度为 O(n)，其中 n 是哈希表中键值对的数量。

4. 获取所有键

有时我们可能只关心哈希表中的键，而不关心对应的值。这时可以通过遍历哈希表获取所有的键。

实现代码：

// 返回哈希表中所有键的集合
public Set<K> keySet() {
    // 创建一个 HashSet 来存储所有键
    Set<K> keys = new HashSet<>();

    // 遍历哈希表的底层存储数组
    for (int i = 0; i < table.length; i++) {
        // 获取当前索引位置的链表头节点
        Entry<K, V> current = table[i];

        // 遍历当前链表
        while (current != null) {
            // 将当前节点的键添加到集合中
            keys.add(current.key);

            // 移动到链表的下一个节点
            current = current.next;
        }
    }

    // 返回包含所有键的集合
    return keys;
}

代码说明：

创建集合：
- 使用 HashSet<K> 创建一个集合 keys，用于存储哈希表中的所有键。
遍历底层存储数组：
- 使用 for 循环遍历哈希表的底层存储数组 table 的每一个索引位置。
遍历链表：
- 对于每个索引位置，获取链表的头节点 current。
- 使用 while 循环遍历链表，直到链表结束（current == null）。
添加键到集合：
- 在遍历链表的过程中，使用 keys.add(current.key) 将当前节点的键添加到集合中。
- HashSet 会自动处理重复键，确保集合中不会出现重复的键。
返回结果：
- 遍历完成后，返回包含所有键的集合 keys。

示例：

假设哈希表中有以下键值对：

键 "A"，值 1
键 "B"，值 2
键 "C"，值 3

调用 keySet() 方法后，返回的集合可能为：

[“A”, “B”, “C”]

注意事项：

时间复杂度：
- 该方法的时间复杂度为 O(n)，其中 n 是哈希表中存储的键值对总数。这是因为方法需要遍历整个哈希表的所有链表。
集合的特性：
- 返回的集合是一个 HashSet，因此键的顺序是无序的。如果需要有序的键集合，可以使用 LinkedHashSet 或 TreeSet。
线程安全性：
- 如果哈希表在多线程环境中被修改，调用 keySet() 方法可能会抛出 ConcurrentModificationException。如果需要线程安全的操作，可以使用 Collections.synchronizedSet() 或其他线程安全的集合实现。
内存占用：
- 返回的集合是一个独立的 HashSet，它会占用额外的内存来存储键的副本。如果哈希表很大，这可能会导致一定的内存开销。

5. 获取所有值

类似地，我们也可以获取哈希表中所有的值，而不需要关心键。

实现代码：

// 返回哈希表中所有值的集合
public Collection<V> values() {
    // 创建一个 ArrayList 来存储所有值
    List<V> values = new ArrayList<>();

    // 遍历哈希表的底层存储数组
    for (int i = 0; i < table.length; i++) {
        // 获取当前索引位置的链表头节点
        Entry<K, V> current = table[i];

        // 遍历当前链表
        while (current != null) {
            // 将当前节点的值添加到列表中
            values.add(current.value);

            // 移动到链表的下一个节点
            current = current.next;
        }
    }

    // 返回包含所有值的集合
    return values;
}

代码说明：

创建集合：
- 使用 ArrayList<V> 创建一个动态数组 values，用于存储哈希表中的所有值。
遍历底层存储数组：
- 使用 for 循环遍历哈希表的底层存储数组 table 的每一个索引位置。
遍历链表：
- 对于每个索引位置，获取链表的头节点 current。
- 使用 while 循环遍历链表，直到链表结束（current == null）。
添加值到集合：
- 在遍历链表的过程中，使用 values.add(current.value) 将当前节点的值添加到列表中。
返回结果：
- 遍历完成后，返回包含所有值的集合 values。

示例：

假设哈希表中有以下键值对：

键 "A"，值 1
键 "B"，值 2
键 "C"，值 3

调用 values() 方法后，返回的集合可能为：

[1, 2, 3]

注意事项：

时间复杂度：
- 该方法的时间复杂度为 O(n)，其中 n 是哈希表中存储的键值对总数。这是因为方法需要遍历整个哈希表的所有链表。
返回值类型：
- 返回的是一个 ArrayList，因此值的顺序是按照哈希表中存储顺序返回的（通常是插入顺序，但由于哈希冲突和链表的存在，顺序可能不固定）。
线程安全性：
- 如果哈希表在多线程环境中被修改，调用 values() 方法可能会抛出 ConcurrentModificationException。如果需要线程安全的操作，可以使用 Collections.synchronizedList() 或其他线程安全的集合实现。
内存占用：
- 返回的集合是一个独立的 ArrayList，它会占用额外的内存来存储值的副本。如果哈希表很大，这可能会导致一定的内存开销。
重复值：
- 如果哈希表中有多个键映射到同一个值，这些值会被重复添加到返回的集合中。如果需要去重，可以在返回之前将 ArrayList 转换为 HashSet。

三、哈希表操作分析

1. 哈希函数：

哈希表的核心是哈希函数，它将键映射到数组索引。Java 内部 Hashtable 使用了 hashCode() 方法来计算键的哈希值，哈希值之后会经过处理以映射到数组的一个有效索引。

2. 冲突解决：

当不同的键有相同的哈希值时，就发生了冲突。Hashtable 在遇到冲突时，会采用链地址法（每个索引存储一个链表，链表中的每个元素保存哈希冲突的键值对）。

3. 性能考虑：

查找操作：由于哈希表能够通过哈希值直接找到元素，所以查找操作的时间复杂度是 O(1)，但最坏情况下会退化为 O(n)（当哈希冲突非常严重时）。
插入和删除操作：插入和删除操作的平均时间复杂度也是 O(1)。
同步问题：Hashtable 是线程安全的，每次访问或修改都需要同步，因此会导致性能较低。如果不需要线程安全，推荐使用 HashMap。

四、哈希表操作的时间复杂度分析

1. 插入（put）：

在最好的情况下（无冲突），插入操作的时间复杂度为 O(1)。当发生哈希冲突时，链表中的每个插入操作的时间复杂度为 O(n)，其中 n 是链表的长度。因此，在哈希表较为均匀分布且负载因子较低的情况下，插入操作通常是 O(1)。

2. 查找（get）：

查找操作的时间复杂度与插入操作类似，最好的情况是 O(1)，最坏的情况是 O(n)，取决于哈希冲突的严重程度。

3. 删除（remove）：

删除操作与查找类似，需要遍历链表来删除元素，因此时间复杂度最坏情况下也是 O(n)。

4. 扩展和重新哈希（resize）：

扩展哈希表时，需要重新计算每个元素的哈希值并重新分配到新表中，因此扩展操作的时间复杂度是 O(n)，其中 n 是表中的元素个数。然而，扩展操作是较少发生的，因此平均情况下对操作性能的影响较小。

五、与 `HashMap` 的比较

线程安全：Hashtable 是线程安全的，每个方法都有同步机制。而 HashMap 是非线程安全的，适用于单线程或外部加锁的场景。
空键和空值：Hashtable 不允许键或值为 null，而 HashMap 允许键和值为 null。
性能：由于 Hashtable 进行同步操作，因此性能上通常不如 HashMap。

六、扩展：自定义哈希表

如果需要实现一个自定义的哈希表，可以按照以下步骤进行：

定义一个 Entry 类，用于存储键值对。
实现哈希表的插入、查找、删除等操作。
处理冲突（例如，使用链地址法）。

简单的自定义哈希表的代码示例如下：

class CustomHashTable<K, V> {
    private static class Entry<K, V> {
        K key;
        V value;
        Entry<K, V> next;

        Entry(K key, V value) {
            this.key = key;
            this.value = value;
            this.next = null;
        }
    }

    private Entry<K, V>[] table;
    private int size;

    public CustomHashTable(int capacity) {
        table = new Entry[capacity];
        size = 0;
    }

    private int hash(K key) {
        return Math.abs(key.hashCode()) % table.length;
    }

    public void put(K key, V value) {
        int index = hash(key);
        Entry<K, V> newEntry = new Entry<>(key, value);
        if (table[index] == null) {
            table[index] = newEntry;
        } else {
            Entry<K, V> current = table[index];
            while (current.next != null) {
                current = current.next;
            }
            current.next = newEntry;
        }
        size++;
    }

    public V get(K key) {
        int index = hash(key);
        Entry<K, V> current = table[index];
        while (current != null) {
            if (current.key.equals(key)) {
                return current.value;
            }
            current = current.next;
        }
        return null; // If key not found
    }

    public void remove(K key) {
        int index = hash(key);
        Entry<K, V> current = table[index];
        Entry<K, V> prev = null;

        while (current != null) {
            if (current.key.equals(key)) {
                if (prev == null) {
                    table[index] = current.next;
                } else {
                    prev.next = current.next;
                }
                size--;
                return;
            }
            prev = current;
            current = current.next;
        }
    }
}

这段代码实现了一个简单的哈希表，使用链表解决冲突。

七、总结

Java 提供的 Hashtable 类非常适用于需要线程安全的场景，但它的性能较低。对于单线程或外部加锁的场景，推荐使用 HashMap。自定义哈希表时，需要考虑哈希函数的设计和冲突解决方法。

评论留言

欢迎您，！您可以在这里畅言您的的观点与见解！

0 条评论

Java：哈希表操作

一、 创建哈希表

代码示例

代码讲解

二、 常见哈希表操作及其实现

1. 扩展哈希表（Resizing / Rehashing）

实现说明

扩展哈希表的代码示例：

代码说明：

注意事项：

2. 获取所有键值对

实现代码：

代码说明：

示例：

注意事项：

3. 键存在性检查

实现代码：

代码说明：

示例：

注意事项：

4. 获取所有键

实现代码：

代码说明：

示例：

注意事项：

5. 获取所有值

实现代码：

代码说明：

示例：

注意事项：

三、 哈希表操作分析

1. 哈希函数：

2. 冲突解决：

3. 性能考虑：

四、 哈希表操作的时间复杂度分析

1. 插入（put）：

2. 查找（get）：

3. 删除（remove）：

4. 扩展和重新哈希（resize）：

五、 与 HashMap 的比较

六、 扩展：自定义哈希表

七、 总结

评论留言

一、创建哈希表

二、常见哈希表操作及其实现

三、哈希表操作分析

四、哈希表操作的时间复杂度分析

五、与 `HashMap` 的比较

六、扩展：自定义哈希表

七、总结