16哈希表-基础操作

目录

哈希表

散列思想

哈希表的实现

简单示例

开胃菜：LeetCode之路——242. 有效的字母异位词

分析

---

哈希表

英文名字为Hash table，散列表的英文叫“Hash Table”，我们平时也叫它“哈希表”或者“Hash表”。

哈希表（Hash Table）是一种数据结构，用于存储和检索键值对数据。它的核心思想是通过散列函数将键映射到一个特定的位置，该位置通常称为桶（Bucket），然后在该位置存储相应的值。这使得在平均情况下，我们可以在常数时间内（O(1)）进行数据的插入、查找和删除操作。

散列思想

散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。以下是哈希表的核心思想和实现：

1. 散列函数（Hash Function）： 哈希表的关键部分是散列函数，它接受一个键作为输入并返回一个整数，这个整数通常称为哈希码。散列函数的目标是将不同的键均匀地映射到不同的桶，最大程度地减少冲突（即多个键映射到同一个桶的情况）。

2. 桶（Bucket）： 哈希表的底层数据结构是由一组桶组成的数组，每个桶可以存储一个或多个键值对。通过散列函数计算的哈希码确定了键值对应该存储在哪个桶中。

3. 解决冲突： 由于不同的键可能映射到相同的桶，因此需要一种方法来处理冲突。常见的冲突解决方法包括链地址法（Chaining）和开放地址法（Open Addressing）等。

哈希表的实现

1. 初始化： 创建一个包含一定数量桶的数组。桶的数量通常是一个质数，它的选择会影响哈希表的性能。

2. 散列函数： 实现一个散列函数，将键映射到数组的索引位置。散列函数的设计很关键，它应该尽量避免冲突，同时也要尽可能均匀地分布键。

3. 插入操作： 当要插入一个键值对时，首先计算键的哈希码，然后根据哈希码找到对应的桶，将键值对插入到桶中。如果发生冲突，根据冲突解决策略来处理。

4. 查找操作： 当要查找一个键对应的值时，通过散列函数计算键的哈希码，然后找到对应的桶，进一步在桶中查找键值对。

5. 删除操作： 删除操作类似于查找操作。首先计算键的哈希码，找到对应的桶，然后在桶中查找并删除键值对。同样，如果发生冲突，需要根据冲突解决策略来处理。

简单示例

1. 字典应用： 就像上面图中的示例一样，哈希表可以用于实现字典，其中单词是键，含义是值。

2. 电话簿： 电话号码和联系人名称可以存储在哈希表中，以便快速查找联系人信息。

3. 缓存： 缓存数据结构通常使用哈希表来存储已检索的数据，以便快速查找并避免重复计算或查询。

4. 文件索引： 用于快速查找文件或文件块的文件索引可以使用哈希表来实现。

5. 身份验证： 存储用户名和密码的数据库可以使用哈希表来加速用户身份验证。

6. 统计信息： 统计信息，如网站访问计数器或用户活动记录，可以使用哈希表来实现。

7. 缓存控制： 用于记录最近访问的网页或资源的缓存管理可以使用哈希表来提高性能。

8. 路由表： 在网络路由器中，路由表可以使用哈希表来存储目的地址和下一跳信息，以便路由数据包。

开胃菜：LeetCode之路——242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

提示:

• 1 <= s.length, t.length <= 5 * 104

• s 和 t 仅包含小写字母

分析

1.如果s和t长度不相等，那么必然不合题意。

2.题意可知，如果s和t异位，那么对应字符的数量是一致的。所以这里用map存储key/value键值对。

3.先遍历s存储字符，然后再遍历t，删除字符，如果删除出现value<0，那么就说明t中包含一个不在s中的额外字符，返回false。

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        Map map = new HashMap();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            map.put(c, table.getOrDefault(c, 0) + 1); // getOrDefault可以避免NPE异常
        }
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            map.put(c, table.getOrDefault(c, 0) - 1);
            if (map.get(c) < 0) {
                return false;
            }
        }
        return true;
    }
}

• 时间复杂度：O(n)

• 空间复杂度：O(n)