哈希表（Hash Table）详解

哈希表是一种用于存储数据的结构，它通过哈希函数将键映射到数组的索引位置，从而实现高效的数据存取。哈希表通常用于实现键值对（key-value）存储，如数据库、缓存系统等。

1. 什么是哈希表

哈希表（Hash Table）是一种特殊的数据结构，它支持快速的插入、删除和查找操作。哈希表的核心思想是利用哈希函数将数据映射到一个固定大小的数组中，通过键来确定数据在数组中的位置，从而提高查询效率。

哈希表的工作原理可以分为以下几个步骤：

哈希函数：将输入的键值（key）转换为数组的索引位置。
冲突解决：由于数组大小有限，哈希表中不同的键可能映射到相同的索引，这种情况叫做冲突，需要解决冲突。
数组：哈希表通常通过一个数组来存储数据，每个位置可以存储一个键值对。

2. 哈希表的工作原理

哈希函数

哈希表通过哈希函数将键（key）转换为数组的索引。常见的哈希函数形式为：

index = hash(key) % array_size

其中，hash(key) 是根据键生成的哈希值，array_size 是数组的大小。通过取模操作确保生成的索引在数组范围内。

插入数据

当需要将一个键值对插入哈希表时，首先使用哈希函数计算出该键的索引位置。如果该位置为空，就直接将键值对存入该位置；如果该位置已被占用，就需要处理冲突（详见下文）。

查找数据

查找数据时，首先使用哈希函数计算出键的索引位置，如果该位置存储的键与目标键相同，则直接返回值；如果不同，则需要根据冲突解决策略继续查找。

3. 哈希表的冲突处理

由于哈希函数的输出范围是有限的，而键的数量是无限的，因此冲突是不可避免的。哈希表有几种常见的冲突解决方法：

3.1 开放地址法（Open Addressing）

开放地址法是指在发生冲突时，哈希表会继续尝试数组中其他位置，直到找到一个空位置。

线性探测（Linear Probing）：如果当前位置已经被占用，就依次检查下一个位置，直到找到一个空位置。
二次探测（Quadratic Probing）：在发生冲突时，不是检查下一个位置，而是根据某个二次函数计算下一个位置。
双重哈希（Double Hashing）：使用第二个哈希函数计算步长，解决冲突时按照该步长依次探测。

3.2 链式地址法（Chaining）

链式地址法是将哈希表的每个位置变为一个链表（或其他数据结构），当发生冲突时，将冲突的键值对添加到链表中。链式地址法不需要探测，因此可以有效避免开放地址法中的“聚集问题”。

4. Java代码案例

下面是一个简单的哈希表实现，包括哈希函数、插入、查找操作以及链式解决冲突的实现。

import java.util.LinkedList;

class HashTable<K, V> {
    // 定义哈希表的大小
    private static final int SIZE = 10;
    // 存储哈希表数据的数组
    private LinkedList<Node<K, V>>[] table;

    // 构造函数，初始化哈希表
    public HashTable() {
        table = new LinkedList[SIZE];
        for (int i = 0; i < SIZE; i++) {
            table[i] = new LinkedList<>();
        }
    }

    // 哈希函数，计算键的索引
    private int hash(K key) {
        return key.hashCode() % SIZE;
    }

    // 插入数据
    public void put(K key, V value) {
        int index = hash(key);
        LinkedList<Node<K, V>> bucket = table[index];
        
        // 检查该位置是否已有键相同的元素，如果有，则更新值
        for (Node<K, V> node : bucket) {
            if (node.key.equals(key)) {
                node.value = value;  // 更新已有的值
                return;
            }
        }
        
        // 如果没有相同键，则新增键值对
        bucket.add(new Node<>(key, value));
    }

    // 查找数据
    public V get(K key) {
        int index = hash(key);
        LinkedList<Node<K, V>> bucket = table[index];

        // 遍历链表，查找键是否存在
        for (Node<K, V> node : bucket) {
            if (node.key.equals(key)) {
                return node.value;
            }
        }
        return null;  // 如果没有找到，返回null
    }

    // 内部节点类，用于存储键值对
    private static class Node<K, V> {
        K key;
        V value;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    // 测试哈希表
    public static void main(String[] args) {
        HashTable<String, Integer> hashTable = new HashTable<>();
        
        // 插入数据
        hashTable.put("apple", 3);
        hashTable.put("banana", 5);
        hashTable.put("orange", 7);

        // 查找数据
        System.out.println("apple: " + hashTable.get("apple"));  // 输出 3
        System.out.println("banana: " + hashTable.get("banana")); // 输出 5
        System.out.println("orange: " + hashTable.get("orange")); // 输出 7
    }
}