线性表(散列) - 哈希表

哈希表（Hash Table）—— 基于散列的线性表实现

哈希表（Hash table，也叫散列表）是一种通过散列函数（Hash Function）将关键字映射到表中特定位置的数据结构，用于实现高效的插入、删除和查找操作。
是根据关键码值(Key value)而直接进行访问的数据结构。
也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
这个映射函数叫做散列函数，存放记录的数组叫做散列表。
其核心思想是利用数组的随机访问特性，通过散列函数将关键字转换为数组下标，从而在理想情况下达到 $O(1)$ 的时间复杂度。哈希表是算法与数据结构中的核心内容，其高效性源于散列思想，但需注意冲突处理和扩容机制以避免性能退化。

性质

典型的哈希函数都有无限的输入值域。
当给哈希函数传入相同的输入值时，返回值一样。
当给哈希函数传入不同的输入值时，返回值可能一样，也可能不一样。
很多不同的输入值所得到的返回值会均匀的分布在S上。

1-3是哈希函数的基本性质。
4是评价一个哈希函数优劣的关键。

核心概念

1. 散列函数（Hash Function）

作用：将任意长度的关键字转换为固定范围的整数（即散列值 / 哈希值），通常为数组下标。
要求：
- 均匀性：不同关键字的散列值应均匀分布，减少冲突。
- 高效性：计算散列值的时间复杂度应尽可能低（通常为 $O(1)$ ）。
常见实现：
- 直接定址法： $H(key) = key 或 H(key) = a \times key + b$ （适用于关键字分布连续的场景）。
- 除留余数法： $H(key) = key \mod m$ （m 为哈希表长度，常用质数）。
- 折叠法：将关键字分割成若干部分后叠加（适用于长关键字）。
- Java 示例：Integer.hashCode() 返回自身值，String.hashCode() 通过字符 ASCII 码计算。

2. 哈希冲突（Hash Collision）

定义：不同关键字通过散列函数得到相同散列值的现象。
解决方法：
- 开放寻址法（Open Addressing）：
  若发生冲突，按某种规则（如线性探测、二次探测）寻找下一个空闲位置。
  - 线性探测： $H_i = (H(key) + i) \mod m（i=1,2,\dots）$ 。
  - 二次探测： $H_i = (H(key) + i^2) \mod m$ 。
- 链地址法（Separate Chaining）：
  每个散列值对应一个链表（或红黑树、平衡树），冲突的关键字存入同一链表。
  - Java 的 HashMap：当链表长度超过阈值（如 8）时，自动转为红黑树以提升查询效率。
- 再散列法：使用多个散列函数依次计算，直到找到空闲位置。

实现要素

1. 负载因子（Load Factor）

定义：哈希表中已存储的关键字数量 n 与表长度 m 的比值，即 $\alpha = n/m$ 。
作用：
- 控制哈希表的空间利用率和冲突概率。
- 当 $\alpha$ 过大（如超过 0.75）时，需进行扩容（Rehashing）：创建更大的哈希表，重新计算所有关键字的散列值并迁移数据。

2. 扩容机制

触发条件：当元素数量超过 负载因子 × 表长度 时触发。
示例：Java 的 HashMap 默认初始容量为 16，负载因子为 0.75，当元素数超过 12 时扩容为 32，并重新散列。

代码实现

链地址法哈希表（Java）

import java.util.LinkedList;

public class HashTable {
    private static final int DEFAULT_CAPACITY = 16;
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    private int capacity; // 哈希表容量
    private int size;     // 已存储元素数量
    private LinkedList<Integer>[] table; // 链表数组

    public HashTable() {
        this.capacity = DEFAULT_CAPACITY;
        this.table = new LinkedList[capacity];
        for (int i = 0; i < capacity; i++) {
            table[i] = new LinkedList<>(); // 初始化每个链表
        }
    }

    // 散列函数：除留余数法
    private int hash(int key) {
        return key % capacity;
    }

    // 插入元素
    public void put(int key) {
        int index = hash(key);
        LinkedList<Integer> list = table[index];
        
        // 若已存在则不重复插入（可修改为更新值场景）
        if (list.contains(key)) return;
        
        list.add(key);
        size++;

        // 检查是否需要扩容
        if (size > DEFAULT_LOAD_FACTOR * capacity) {
            resize();
        }
    }

    // 删除元素
    public void remove(int key) {
        int index = hash(key);
        LinkedList<Integer> list = table[index];
        list.remove(Integer.valueOf(key));
        size--;
    }

    // 查找元素
    public boolean contains(int key) {
        int index = hash(key);
        LinkedList<Integer> list = table[index];
        return list.contains(key);
    }

    // 扩容方法
    private void resize() {
        int newCapacity = capacity * 2;
        LinkedList<Integer>[] newTable = new LinkedList[newCapacity];
        
        for (int i = 0; i < newCapacity; i++) {
            newTable[i] = new LinkedList<>();
        }
        
        // 重新散列所有元素
        for (LinkedList<Integer> list : table) {
            for (int key : list) {
                int newIndex = key % newCapacity;
                newTable[newIndex].add(key);
            }
        }
        
        table = newTable;
        capacity = newCapacity;
    }

    // 测试用例
    public static void main(String[] args) {
        HashTable ht = new HashTable();
        int[] keys = {5, 15, 25, 3, 13, 23, 7, 17, 27};
        
        System.out.println("=== 插入元素 ===");
        for (int key : keys) {
            ht.put(key);
            System.out.println("插入 " + key + "，哈希值：" + ht.hash(key));
        }
        
        System.out.println("\n=== 查找元素 ===");
        System.out.println("查找 13：" + ht.contains(13)); // true
        System.out.println("查找 99：" + ht.contains(99)); // false
        
        System.out.println("\n=== 删除元素 ===");
        ht.remove(15);
        System.out.println("删除 15 后，是否包含：" + ht.contains(15)); // false
    }
}

性能分析

操作	理想情况（无冲突）	平均情况	最坏情况（全冲突）
插入 / 删除 / 查找	$O(1)$	$O(1 + \alpha)$	$O(n)$

优化关键：
1. 选择高效的散列函数，减少冲突。
2. 合理设置负载因子和扩容策略，平衡空间与时间。
3. 冲突处理方式：链地址法比开放寻址法更适合频繁删除操作。

应用场景

数据去重：利用contains操作快速判断元素是否存在（如 LeetCode 多数元素问题）。
缓存系统：如 CPU 高速缓存、Redis 键值对存储。
编译器符号表：存储变量名与地址的映射。
Java 集合框架：HashMap、HashSet基于哈希表实现。

常见问题

如何避免哈希冲突？

使用高质量散列函数（如 MD5、SHA-1），选择合适的表长度（质数），并结合链地址法。

我们知道，对象Hash的前提是实现equals()和hashCode()两个方法，那么HashCode()的作用就是保证对象返回唯一hash值，但当两个对象计算值一样时，这就发生了碰撞冲突。如下将介绍如何处理冲突，当然其前提是一致性hash。

1.开放地址法

开放地执法有一个公式: $Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1)$
其中，m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为 $1,2,3,…m-1$ ，称线性探测再散列。
如果di取1，则每次冲突之后，向后移动1个位置.如果di取值可能为 $1,-1,2,-2,4,-4,9,-9,16,-16,…k*k,-k*k(k<=m/2)$ ，称二次探测再散列。
如果di取值可能为伪随机数列。称伪随机探测再散列。

2.再哈希法

当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。

缺点：计算时间增加。

比如上面第一次按照姓首字母进行哈希，如果产生冲突可以按照姓字母首字母第二位进行哈希，再冲突，第三位，直到不冲突为止

3.链地址法（拉链法）

将所有关键字为同义词的记录存储在同一线性链表中。

优点：

①拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
②由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
③开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
④在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。
而对开放地址法构造的散列表，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。
这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。
因此在用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。

缺点：

指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。

4.建立一个公共溢出区

假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表，另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。

开放寻址法和链地址法的区别？

开放寻址法将冲突元素存储在数组内，链地址法使用额外链表存储，后者更灵活且适合动态数据。

为什么一般hashtable的桶数会取一个素数

假如有一个哈希函数： $H( c ) = c % N$

当N取一个合数时，最简单的例子是取 $2^n$ ，比如说取 $2^3=8$ ,这时候

$H( 11100(二进制） ) = H( 36 ) = 4$ $H( 10100(二进制) ) = H( 28）= 4$

这时候c的二进制第4位（从右向左数）就”失效”了，也就是说，无论第c的4位取什么值，都会导致 $H( c )$ 的值一样．这时候c的第四位就根本不参与 $H( c )$ 的运算，这样 $H( c )$ 就无法完整地反映c的特性，增大了导致冲突的几率．

取其他合数时，都会不同程度的导致c的某些位”失效”，从而在一些常见应用中导致冲突．

在实际中往往关键字有某种规律，例如大量的等差数列，那么公差和模数不互质的时候发生碰撞的概率会变大，而用质数就可以很大程度上回避这个问题。基本可以保证c的每一位都参与 $H( c )$ 的运算，从而在常见应用中减小冲突几率.

相关题目

哈希表使用 $O(N)$ 空间复杂度存储数据，并且以 $O(1)$ 时间复杂度求解问题。

Java 中的 HashSet 用于存储一个集合，可以查找元素是否在集合中。如果元素有穷，并且范围不大，那么可以用一个布尔数组来存储一个元素是否存在。例如对于只有小写字符的元素，就可以用一个长度为 26 的布尔数组来存储一个字符集合，使得空间复杂度降低为 O(1)。
Java 中的 HashMap 主要用于映射关系，从而把两个元素联系起来。
HashMap 也可以用来对元素进行计数统计，此时键为元素，值为计数。和 HashSet 类似，如果元素有穷并且范围不大，可以用整型数组来进行统计。
在对一个内容进行压缩或者其它转换时，利用 HashMap 可以把原始内容和转换后的内容联系起来。
例如在一个简化 url 的系统中 Leetcdoe : 535. Encode and Decode TinyURL (Medium)在新窗口打开，利用 HashMap 就可以存储精简后的 url 到原始 url 的映射，使得不仅可以显示简化的 url，也可以根据简化的 url 得到原始 url 从而定位到正确的资源。

数组中两个数的和为给定值

1. Two Sum (Easy)在新窗口打开

可以先对数组进行排序，然后使用双指针方法或者二分查找方法。这样做的时间复杂度为 $O(nlog n)$ ，空间复杂度为 $(1)$ 。

用 HashMap 存储数组元素和索引的映射，在访问到 nums[i] 时，判断 HashMap 中是否存在 target - nums[i]，如果存在说明 target - nums[i] 所在的索引和 i 就是要找的两个数。该方法的时间复杂度为 O(N)，空间复杂度为 O(N)，使用空间来换取时间。

public int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> indexForNum = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        if (indexForNum.containsKey(target - nums[i])) {
            return new int[]{indexForNum.get(target - nums[i]), i};
        } else {
            indexForNum.put(nums[i], i);
        }
    }
    return null;
}

判断数组是否含有重复元素

217. Contains Duplicate (Easy)在新窗口打开

public boolean containsDuplicate(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        set.add(num);
    }
    return set.size() < nums.length;
}

最长和谐序列

594. Longest Harmonious Subsequence (Easy)在新窗口打开

Input: [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

和谐序列中最大数和最小数只差正好为 1，应该注意的是序列的元素不一定是数组的连续元素。

public int findLHS(int[] nums) {
    Map<Integer, Integer> countForNum = new HashMap<>();
    for (int num : nums) {
        countForNum.put(num, countForNum.getOrDefault(num, 0) + 1);
    }
    int longest = 0;
    for (int num : countForNum.keySet()) {
        if (countForNum.containsKey(num + 1)) {
            longest = Math.max(longest, countForNum.get(num + 1) + countForNum.get(num));
        }
    }
    return longest;
}

最长连续序列

128. Longest Consecutive Sequence (Hard)在新窗口打开

Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

要求以 O(N) 的时间复杂度求解。

public int longestConsecutive(int[] nums) {
    Map<Integer, Integer> countForNum = new HashMap<>();
    for (int num : nums) {
        countForNum.put(num, 1);
    }
    for (int num : nums) {
        forward(countForNum, num);
    }
    return maxCount(countForNum);
}

private int forward(Map<Integer, Integer> countForNum, int num) {
    if (!countForNum.containsKey(num)) {
        return 0;
    }
    int cnt = countForNum.get(num);
    if (cnt > 1) {
        return cnt;
    }
    cnt = forward(countForNum, num + 1) + 1;
    countForNum.put(num, cnt);
    return cnt;
}

private int maxCount(Map<Integer, Integer> countForNum) {
    int max = 0;
    for (int num : countForNum.keySet()) {
        max = Math.max(max, countForNum.get(num));
    }
    return max;
}

参考

https://blog.csdn.net/single6/article/details/81353084