在算法中，哈希法（散列哈希表）是一种通过「键 - 值」映射快速访问数据的方法，核心是利用哈希函数将键映射到内存地址，实现 O (1) 级别的查找效率。常用的哈希结构有数组、Set 和 Map，它们的适用场景和特性各有不同，下面详细讲解：

一、哈希数组（Hash Array）

本质

用数组的下标作为「键」，数组的值作为「值」，直接通过下标访问数据。

特点

• 优势：访问速度最快（直接通过下标定位，无需哈希函数计算），实现简单。
• 限制：
  1. 键必须是整数（因为数组下标只能是整数）。
  2. 键的范围必须有限且已知（否则数组会过大，浪费空间）。

适用场景

• 元素值范围较小且为整数（如 0~1000），例如：
  • 统计数字出现次数（如两数之和、数组交集）。
  • 判断元素是否存在（如判断一个数是否在数组中）。

示例

java

运行

// 统计 nums 中每个数字的出现次数（假设数字范围 0~100）
int[] count = new int[101]; // 下标 0~100 对应数字 0~100
for (int num : nums) {
    count[num]++; // 直接用数字作为下标，累加次数
}

二、哈希集合（Hash Set）

本质

存储不重复的元素（只有键，无值），底层通过哈希表实现，支持快速判断元素是否存在。

特点

• 优势：
  1. 自动去重（相同元素只会存储一次）。
  2. 支持任意类型的元素（整数、字符串等）。
• 限制：
  1. 只能判断元素是否存在，无法存储额外信息（如次数、索引）。
  2. 空间复杂度较高（哈希表需要额外空间存储哈希值）。

适用场景

• 需要去重或判断元素是否存在的场景，例如：
  • 数组去重。
  • 检查两个数组的交集（只需要元素本身，不需要次数）。

示例

java

运行

// 数组去重
int[] nums = {1, 2, 2, 3, 3, 3};
Set<Integer> set = new HashSet<>();
for (int num : nums) {
    set.add(num); // 自动去重，最终 set 中为 {1,2,3}
}

三、哈希映射（Hash Map）

本质

存储键 - 值对（Key-Value），可以通过键快速查找对应的值，底层也是哈希表实现。

特点

• 优势：
  1. 键可以是任意类型（整数、字符串等），值可以存储额外信息（如次数、索引）。
  2. 支持复杂的映射关系（如元素→索引、元素→出现次数）。
• 限制：
  1. 键不能重复（重复会覆盖旧值）。
  2. 空间复杂度较高（比数组大）。

适用场景

• 需要存储键和对应值的场景，例如：
  • 两数之和（存储元素→索引，快速查找互补元素的位置）。
  • 统计元素出现次数（键为元素，值为次数）。

示例

java

运行

// 存储元素及其索引
int[] nums = {2, 7, 11, 15};
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
    map.put(nums[i], i); // 键：元素值，值：元素索引
}
// 查找元素 7 的索引：map.get(7) → 返回 1

四、三者的核心区别

结构	存储内容	键的类型限制	适用场景	优势	劣势
哈希数组	下标→值（次数）	必须是整数	元素范围小且为整数的统计	速度最快，空间最省	键类型和范围受限
Hash Set	不重复的元素	任意类型	去重、判断元素是否存在	自动去重，使用简单	无法存储额外信息
Hash Map	键 - 值对	任意类型	复杂映射关系（如元素→索引）	功能最灵活，支持多信息	空间开销较大

五. 「无序」与「有序」结构的对比

无序结构（Unordered）	有序结构（Ordered）
HashSet、HashMap	LinkedHashSet、LinkedHashMap（保证插入顺序）
无顺序保证，基于哈希表实现	保证顺序（插入顺序或自然排序），部分基于链表 / 红黑树实现
查找、插入、删除效率高（O (1)）	效率略低（如 TreeMap 为 O (log n)）

总结

• 优先用数组：当元素是整数且范围有限时（空间和速度最优）。
• 优先用Set：只需去重或判断存在性，无需额外信息时。
• 优先用Map：需要存储键和对应的值（如索引、次数）时。