一.介绍

1.什么是 hash 表

哈希表（Hash Table），也称为散列表，是一种数据结构，用于存储键-值对（key-value pairs）。它通过将键（key）映射到一个特定的索引位置来实现高效的数据检索和存储操作。哈希表的核心思想是使用哈希函数将键映射为一个在数组中的位置，然后将值存储在该位置。

2.hash 表特性

以下是哈希表的一些关键特点和概念：

1. 哈希函数（Hash Function）：哈希表中最重要的部分之一，它接受一个键作为输入，然后返回一个索引值，该索引用于存储或检索相关值。哈希函数应该是快速计算的，并且应该具有均匀分布性，以减少冲突（collision）的概率。

2. 数组（Array）：哈希表通常由一个数组构成，该数组的大小可以根据需要动态调整或固定。数组的每个元素被称为一个“桶”（bucket）或“槽”（slot）。

3. 冲突（Collision）：由于哈希函数可能将不同的键映射到相同的索引位置，因此可能会发生冲突。哈希表必须能够处理这些冲突，常见的方法包括链式哈希法（Chaining）和开放寻址法（Open Addressing）。

4. 链式哈希法（Chaining）：在这种解决冲突的方法中，每个桶存储一个链表或其他数据结构，以容纳多个键值对，具有相同哈希值的键值对会存储在同一个链表中。

5. 开放寻址法（Open Addressing）：在这种解决冲突的方法中，如果发生冲突，就会尝试在哈希表中的其他位置查找空的桶来存储键值对，直到找到一个空的桶或达到最大尝试次数。

6. 加载因子（Load Factor）：它是一个表示哈希表空间利用率的指标。加载因子等于哈希表中存储的元素数量除以数组的大小。控制加载因子可以影响哈希表的性能，通常在需要时进行扩容以保持加载因子较低。

哈希表的主要优点是能够提供常数时间复杂度的平均查找时间，即使数据集很大，也可以快速找到键对应的值。然而，要保证其性能，需要选择合适的哈希函数和解决冲突的方法，以及合理管理加载因子。哈希表在许多编程语言和应用中都有广泛的应用，用于快速查找和插入操作。

3.应用场景

哈希表在解决各种算法问题中有广泛的应用场景，特别是用于高效地进行数据检索和存储。以下是一些适合使用哈希表的应用场景和算法题目类型：

1. 查找问题：当需要在一个数据集中快速查找某个元素时，哈希表是一个理想的数据结构。例如，查找某个值是否存在于数组、集合或字符串中。

2. 去重问题：如果需要从一组元素中删除重复项，可以使用哈希表来跟踪已经出现过的元素，并避免重复。

3. 计数问题：哈希表可以用于统计元素出现的次数。例如，统计一组整数中每个整数出现的频率。

4. 字母频率统计：在字符串处理中，哈希表可用于统计字符出现的频率，用于解决字符频率分析问题。

5. 两数之和：给定一个数组和一个目标值，找到数组中两个数的索引，使它们的和等于目标值。这是一个经典的哈希表应用场景。

6. 子数组和问题：寻找数组中连续子数组的和等于特定值的问题，可以通过哈希表来优化。

7. 缓存问题：实现缓存时，可以使用哈希表来存储最近访问的数据，以提高数据访问速度。

8. 映射问题：构建从一组键到一组值的映射关系，例如，实现一个字典或关联数组。

9. 图的表示：在图算法中，哈希表可以用于表示图的节点和边的关系。

10. 存储中间结果：在某些算法中，需要存储中间计算结果以提高性能，哈希表可以用于存储这些中间结果。

总的来说，哈希表特别适合处理需要快速查找、去重、计数或映射的问题。它们提供了平均常数时间复杂度的查找操作，使其成为解决许多算法问题的有力工具。但要注意选择适当的哈希函数和处理冲突的方法，以确保哈希表的性能和正确性。

二.实现 hash 表

1.第一版

未考虑 hash 码的生成，假定该 hash 码由我们提供

public class HashTable {

    // 节点类
    static class Entry {
        int hash; // 哈希码
        Object key; // 键
        Object value; // 值
        Entry next;

        public Entry(int hash, Object key, Object value) {
            this.hash = hash;
            this.key = key;
            this.value = value;
        }
    }

    Entry[] table = new Entry[16];
    int size = 0; // 元素个数
    float loadFactor = 0.75f; // 12 阈值
    int threshold = (int) (loadFactor * table.length);

    /* 求模运算替换为位运算
        - 前提：数组长度是 2 的 n 次方
        - hash % 数组长度 等价于 hash & (数组长度-1)
     */

    // 根据 hash 码获取 value
    Object get(int hash, Object key) {
        int idx = hash & (table.length - 1);
        if (table[idx] == null) {
            return null;
        }
        Entry p = table[idx];
        while (p != null) {
            if (p.key.equals(key)) {
                return p.value;
            }
            p = p.next;
        }
        return null;
    }

    // 向 hash 表存入新 key value，如果 key 重复，则更新 value
    void put(int hash, Object key, Object value) {
        int idx = hash & (table.length - 1);
        if (table[idx] == null) {
            // 1. idx 处有空位, 直接新增
            table[idx] = new Entry(hash, key, value);
        } else {
            // 2. idx 处无空位, 沿链表查找 有重复key更新，否则新增
            Entry p = table[idx];
            while (true) {
                if (p.key.equals(key)) {
                    p.value = value; // 更新
                    return;
                }
                if (p.next == null) {
                    break;
                }
                p = p.next;
            }
            p.next = new Entry(hash, key, value); // 新增
        }
        size++;
        if (size > threshold) {
            resize();
        }
    }

    private void resize() {
        Entry[] newTable = new Entry[table.length << 1];
        for (int i = 0; i < table.length; i++) {
            Entry p = table[i]; // 拿到每个链表头
            if (p != null) {
            /*
                拆分链表，移动到新数组，拆分规律
                * 一个链表最多拆成两个
                * hash & table.length == 0 的一组
                * hash & table.length != 0 的一组
                                          p
                0->8->16->24->32->40->48->null
                            a
                0->16->32->48->null
                        b
                8->24->40->null
             */
                Entry a = null;
                Entry b = null;
                Entry aHead = null;
                Entry bHead = null;
                while (p != null) {
                    if ((p.hash & table.length) == 0) {
                        if (a != null) {
                            a.next = p;
                        } else {
                            aHead = p;
                        }
                        a = p; // 分配到a
                    } else {
                        if (b != null) {
                            b.next = p;
                        } else {
                            bHead = p;
                        }
                        b = p; // 分配到b
                    }
                    p = p.next;
                }
                // 规律： a 链表保持索引位置不变，b 链表索引位置+table.length
                if (a != null) {
                    a.next = null;
                    newTable[i] = aHead;
                }
                if (b != null) {
                    b.next = null;
                    newTable[i + table.length] = bHead;
                }
            }
        }
        table = newTable;
        threshold = (int) (loadFactor * table.length);
    }

    // 根据 hash 码删除，返回删除的 value
    Object remove(int hash, Object key) {
        int idx = hash & (table.length - 1);
        if (table[idx] == null) {
            return null;
        }
        Entry p = table[idx];
        Entry prev = null;
        while (p != null) {
            if (p.key.equals(key)) {
                // 找到了, 删除
                if (prev == null) { // 链表头
                    table[idx] = p.next;
                } else { // 非链表头
                    prev.next = p.next;
                }
                size--;
                return p.value;
            }
            prev = p;
            p = p.next;
        }
        return null;
    }
}

2.什么叫做 hash 算法?

哈希算法（Hash Algorithm），也称为哈希函数（Hash Function），是一种将输入数据（通常是任意长度的数据）转换为固定长度的输出数据的数学函数或算法。这个输出数据通常被称为哈希值（Hash Value）或摘要（Digest）。哈希算法的主要特点是：

1. 固定长度输出：不论输入数据的大小如何，哈希算法都会生成一个固定长度的哈希值。这使得哈希值的大小与输入数据的大小无关，通常以字节为单位。

2. 唯一性：不同的输入数据通常会产生不同的哈希值，但哈希值是有限的，因此不同的输入数据有可能生成相同的哈希值，这就是所谓的哈希冲突。

3. 不可逆性：从哈希值不能反推出原始输入数据。这是哈希算法的一个重要特性，使得哈希值通常用于存储密码、数据完整性验证等安全相关的应用中。

4. 高效性：哈希算法应该能够在合理的时间内计算出哈希值，无论输入数据的大小如何。

3.hash 算法的应用?

哈希算法在计算机科学和信息安全领域有广泛的应用，包括但不限于以下情况：

1. 数据完整性验证：用于检测数据在传输或存储过程中是否被篡改。接收方可以计算接收到的数据的哈希值，与发送方提供的哈希值进行比较，以验证数据是否完整。

2. 密码学应用：用于存储密码的哈希值，而不是明文密码。这样，即使数据库被泄露，攻击者也不能轻易获取原始密码。

3. 数据结构：哈希表（散列表）中使用哈希算法来确定键在数组中的存储位置，以实现高效的数据检索。

4. 文件检测：用于检测文件是否在传输过程中发生了更改，例如，在下载文件时验证文件的完整性。

5. 数字签名：哈希算法与非对称加密算法结合使用，用于生成数字签名，验证文档的来源和完整性。

6. 数据分区和分布式系统：在分布式系统中，哈希算法用于将数据均匀分布到多个节点上，以实现负载均衡。

不同的哈希算法具有不同的性质和适用场景。常见的哈希算法包括 MD5、SHA-1、SHA-256、SHA-3 等。选择适当的哈希算法取决于具体的需求，尤其是在安全性方面需要特别小心选择。因为一旦选择了不安全的哈希算法，可能会导致数据泄露或数据完整性受损。

4.常见的 hash 算法有哪些?

以下是一些常见的哈希算法：

1. MD5（Message Digest Algorithm 5）：MD5 是一种广泛使用的哈希算法，生成 128 位（16 字节）的哈希值。然而，它已经被证明存在一些弱点，不再被推荐用于安全敏感的应用。

2. SHA-1（Secure Hash Algorithm 1）：SHA-1 生成 160 位（20 字节）的哈希值。与 MD5 一样，SHA-1 也已经被证明存在弱点，不适用于安全性要求高的场景。

3. SHA-256（Secure Hash Algorithm 256）：SHA-256 是 SHA-2 家族中的一员，生成 256 位（32 字节）的哈希值。它在许多安全应用中广泛使用，提供了更高的安全性。

4. SHA-3（Secure Hash Algorithm 3）：SHA-3 是 SHA-2 的后续版本，它使用不同的哈希函数设计，提供了与 SHA-2 相似的安全性，但具有不同的内部结构。

5. SHA-512（Secure Hash Algorithm 512）：SHA-512 是 SHA-2 家族中的一员，生成 512 位（64 字节）的哈希值，提供了更高的安全性，但通常也需要更多的计算资源。

6. CRC32（Cyclic Redundancy Check）：CRC32 通常用于数据校验，而不是安全哈希。它生成 32 位的哈希值，主要用于检测数据传输中的错误。

7. bcrypt：bcrypt 是一种用于密码存储的哈希算法，它具有“慢哈希”的特性，使得破解密码更加困难。

8. Argon2：Argon2 是一种用于密码哈希和密钥派生的现代密码哈希算法，特别设计用于抵抗密码破解攻击。

9. PBKDF2（Password-Based Key Derivation Function 2）：PBKDF2 是一种用于从密码生成密钥的算法，通常用于加密存储的密码。

10. CityHash：CityHash 是一种用于快速哈希的算法，通常用于数据结构和分布式系统的键的哈希。

这些哈希算法在不同的应用中具有不同的特点和用途。在选择哈希算法时，应根据具体的需求考虑安全性、性能和适用性，并避免使用已知存在弱点的算法。此外，随着时间的推移，一些哈希算法可能会被认为不再安全，因此选择现代和安全的算法是至关重要的。

5.好的哈希算法?

一个好的哈希算法应该满足以下几个关键条件：

1. 一致性（Consistency）：相同的输入始终产生相同的哈希值。这是哈希算法的基本要求，确保了可预测性和可重复性。

2. 高效性（Efficiency）：算法应该能够在合理的时间内计算出哈希值，无论输入数据的大小如何。高效性是算法在实际应用中可行性的关键。

3. 均匀分布（Uniform Distribution）：理想情况下，哈希算法应该能够将不同的输入均匀映射到哈希值空间中的不同位置，以减少哈希冲突的概率。

4. 不可逆性（Irreversibility）：从哈希值不能反推出原始输入数据。这是保护敏感信息和密码的重要特性。

5. 抗碰撞性（Collision Resistance）：算法应该具有抗碰撞的特性，即很难找到两个不同的输入，它们产生相同的哈希值。这可以减少攻击者通过找到冲突来破解系统的机会。

6. 抗彩虹表攻击性（Resistance to Rainbow Table Attacks）：哈希算法应该对彩虹表攻击具有抵抗力，这是一种预先计算哈希值并存储在表中的攻击方式。

7. 盐值支持（Salt Support）：对于存储密码或生成安全哈希的情况，算法应该支持盐（salt）的概念，以增加安全性。盐是随机生成的额外数据，附加到密码或输入数据上，以使相同的输入产生不同的哈希值。

8. 可伸缩性（Scalability）：对于分布式系统或大规模应用，哈希算法应该能够容易地扩展以处理大量数据。

9. 安全性（Security）：算法应该经过广泛的安全分析和测试，以确保它抵抗各种攻击，包括穷举攻击、彩虹表攻击、碰撞攻击等。

10. 适用性（Applicability）：哈希算法的选择应该基于特定的应用需求。不同的应用可能需要不同级别的安全性和性能。

一个好的哈希算法应该提供高度的安全性、性能和可用性，同时满足特定应用的需求。选择合适的哈希算法取决于应用的具体用途，以及对安全性和性能的权衡。不同的应用可能需要不同的哈希算法，因此应根据具体情况进行选择。

6.JDK 中的 hashCode

Object.hashCode

• Object 的 hashCode 方法默认是生成随机数作为 hash 值（会缓存在对象头当中）
• 缺点是包含相同值的不同对象，他们的 hashCode 不一样，不能够用 hash 值来反映对象的值特征，因此诸多子类都会重写 hashCode 方法

String.hashCode

public static void main(String[] args) {
    String s1 = "bac";
    String s2 = new String("abc");

    System.out.println(s1.hashCode());
    System.out.println(s2.hashCode());

    // 原则：值相同的字符串生成相同的 hash 码, 尽量让值不同的字符串生成不同的 hash 码
    /*
    对于 abc  a * 100 + b * 10 + c
    对于 bac  b * 100 + a * 10 + c
     */
    int hash = 0;
    for (int i = 0; i < s1.length(); i++) {
        char c = s1.charAt(i);
        System.out.println((int) c);
        // (a*10 + b)*10 + c  ==>  a*100 + b*10 + c  2^5
        hash = (hash << 5) - hash + c;
    }
    System.out.println(hash);
}

• 经验表明如果每次乘的是较大质数，可以有更好地降低 hash 冲突，因此改【乘 10】为【乘 31】
• 【乘 31】可以等价为【乘 32 - hash】，进一步可以转为更高效地【左移 5 位 - hash】

检查 hash 表的分散性

public void print() {
    int[] sum = new int[table.length];
    for (int i = 0; i < table.length; i++) {
        Entry p = table[i];
        while (p != null) {
            sum[i]++;
            p = p.next;
        }
    }
    System.out.println(Arrays.toString(sum));

    Map<Integer, Long> result = Arrays.stream(sum).boxed()
        .collect(Collectors.groupingBy(s -> s, Collectors.counting()));
    System.out.println(result);
}

测试

public static void main(String[] args) throws IOException {
    // 测试 Object.hashCode
    HashTable table = new HashTable();
    for (int i = 0; i < 200000; i++) {
        Object obj = new Object();
        table.put(obj, obj);
    }
    table.print();

    // 测试 String.hashCode
    table = new HashTable();
    List<String> strings = Files.readAllLines(Path.of("words"));
    for (String string : strings) {
        table.put(string, string);
    }
    table.print();
}

7.MurmurHash

MurmurHash（又称 Murmur Hash）是一系列非加密哈希函数，最初由 Austin Appleby 于 2008 年创建。它是一种快速、高效、均匀分布的哈希算法，经常用于哈希表、数据结构和分布式系统等应用。MurmurHash 以其简单性和性能而闻名，并且有多个变种，如 MurmurHash1、MurmurHash2、MurmurHash3 等。

下面是关于 MurmurHash 的一些特点和信息：

1. 高速性：MurmurHash 的设计目标之一是快速计算哈希值。它在处理大量数据时表现出色，适合需要快速哈希计算的应用场景。

2. 均匀分布：MurmurHash 被设计为生成均匀分布的哈希值，这意味着不同的输入数据倾向于在哈希空间中均匀分散，减少了哈希冲突的可能性。

3. 非加密性：MurmurHash 是一种非加密哈希函数，不适用于安全性要求高的应用，因为它的设计目标是性能而不是安全性。

4. 可变种：MurmurHash 有多个变种，其中 MurmurHash3 是最新版本。不同版本的 MurmurHash 具有不同的性能和特性，可以根据需要选择适当的版本。

5. 输入长度不受限制：MurmurHash 可以处理任意长度的输入数据，包括长字符串或字节流。

6. 使用场景：MurmurHash 通常用于快速数据哈希和分布式系统中的数据分片、负载均衡等操作。由于其高性能和均匀分布的特性，它在很多应用中都有广泛的应用。

需要注意的是，由于 MurmurHash 是一种非加密哈希算法，不适合用于密码存储或数字签名等安全性关键的应用。对于需要强安全性保障的场景，应该选择专门设计用于安全性的哈希算法，如 SHA-256 或 bcrypt。但对于一般的快速哈希需求，MurmurHash 通常是一个性能出色的选择。

三.hash 表练习题

1.两数之和-力扣 1 题

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

public class E01Leetcode1 {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int k = target - nums[i];
            if (map.containsKey(k)) {
                return new int[]{i, map.get(k)};
            }
            map.put(nums[i], i);
        }
        return null; // 不会执行
    }
}

• 注意：题目明确说明只会存在一个有效答案，因此不会执行到最后的 return null

2.无重复字符的最长字串-力扣 3 题

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

public int lengthOfLongestSubstring(String s) {
    HashMap<Character, Integer> map = new HashMap<>();
    int begin = 0;
    int maxLength = 0;
    for (int end = 0; end < s.length(); end++) {
        char ch = s.charAt(end);
        if (map.containsKey(ch)) { // 重复时调整 begin
            begin = Math.max(begin, map.get(ch) + 1);
            map.put(ch, end);
        } else { // 不重复
            map.put(ch, end);
        }
        System.out.println(s.substring(begin, end + 1));
        maxLength = Math.max(maxLength, end - begin + 1);
    }
    return maxLength;
}

begin 调整时的解释，遇到重复的 begin 应该向右调整，例如

abca

• 遇到重复的 a，这时 begin 应该调整到上个重复字符 a 索引加 1 处，即 map.get('a') + 1 = 1，

但还有一种情况需要考虑，就是连续遇到两次重复，例如

abba

• 遇到重复的 b，这时 begin 应该调整到上个重复字符 b 索引加 1 处，即 map.get('b') + 1 = 2
• 不过接下来，又遇到了重复的 a，此时若还执行 map.get('a') + 1 = 1，则 begin 相当于向左退了，不对
• 应该是 Math.max(2, map.get('a') + 1)，即 begin 应该是两个重复字符索引中更靠右者

题目中说明 s 由英文字母、数字、符号和空格组成，因此它的范围是有限的（在 0 ~127 之内），可以用数组来替代 HashMap 优化，如下

public int lengthOfLongestSubstring(String s) {
    int[] hash = new int[128];
    Arrays.fill(hash, -1);
    int begin = 0, max = 0;
    final char[] chars = s.toCharArray();
    for (int end = 0; end < chars.length; end++) {
        char ch = chars[end];
        if (hash[ch] != -1) {
            // 遇到重复字符
            begin = Math.max(begin, hash[ch] + 1);
            hash[ch] = end;
        } else {
            hash[ch] = end;
        }
        max = Math.max(max, end - begin + 1);
    }
    return max;
}

3.字母异位词分组-力扣 49 题

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例一:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例二:

输入: strs = [""] 输出: [[""]]

示例三:

输入: strs = ["a"] 输出: [["a"]]

解法 1:使用HashMap进行存储数据和putIfAbsent的使用

public List<List<String>> groupAnagrams(String[] strs) { // 6ms
    HashMap<String, List<String>> map = new HashMap<>();
    for (String str : strs) {
        final char[] chars = str.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);
        map.putIfAbsent(key, new ArrayList<>());
        map.get(key).add(str);
    }
    return new ArrayList<>(map.values());
}

解法 2:

computeIfAbsent的使用

public List<List<String>> groupAnagrams(String[] strs) {
    HashMap<String, List<String>> map = new HashMap<>();
    for (String str : strs) {
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);
        List<String> strings = map.computeIfAbsent(key, k -> new ArrayList<>());
        strings.add(str);
    }
    return new ArrayList<>(map.values());
}

解法 3

static class ArrayKey {
    int[] key = new int[26];

    public ArrayKey(String str) {
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            key[ch - 'a']++;
        }
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        ArrayKey arrayKey = (ArrayKey) o;

        return Arrays.equals(key, arrayKey.key);
    }

    @Override
    public int hashCode() {
        return Arrays.hashCode(key);
    }
}

public List<List<String>> groupAnagrams(String[] strs) {
    HashMap<ArrayKey, List<String>> map = new HashMap<>();
    for (String str : strs) {
        List<String> strings = map.computeIfAbsent(new ArrayKey(str), k -> new ArrayList<>());
        strings.add(str);
    }
    return new ArrayList<>(map.values());
}

4.判断有没有重复元素-力扣 217

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

输入：nums = [1,2,3,1]
输出：true

解法 1

public boolean containsDuplicate(int[] nums) { // 6ms
    HashMap<Integer, Integer> map = new HashMap<>(nums.length * 2);
    for (int key : nums) {
        Integer put = map.put(key, 1);
        if (put != null) {
            return true;
        }
    }
    return false;
}

解法 2

public boolean containsDuplicate(int[] nums) { // 5ms
    HashSet<Integer> set = new HashSet<>();
    for (int key : nums) {
        if (!set.add(key)) {
            return true;
        }
    }
    return false;
}

5.找出出现一次的数字-力扣 136

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

输入：nums = [2,2,1]
输出：1

解法 1：用 HashSet

public int singleNumber(int[] nums) {
    HashSet<Integer> set = new HashSet<>();
    for (int num : nums) {
        if (!set.add(num)) {
            set.remove(num);
        }
    }
    return set.toArray(new Integer[0])[0];
}

解法 2：用 xor

public int singleNumber(int[] nums) {
    int num = nums[0];
    for (int i = 1; i < nums.length; i++) {
        num = num ^ nums[i];
    }
    return num;
}

6.判断字母异位词-力扣 242

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

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

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

public boolean isAnagram(String s, String t) { // 1ms
    return Arrays.equals(getKey(s), getKey(t));
}

private static int[] getKey(String s) {
    int[] array = new int[26];
    char[] chars = s.toCharArray();
    for (char ch : chars) {
        array[ch - 97]++;
    }
    return array;
}

• 其中用 s.toCharArray() 性能明显高于用 s.charAt() 一个个获取字符

7.第一个不重复字符-力扣 387

给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。

输入: s = "leetcode"
输出: 0

public int firstUniqChar(String s) {
    int[] array = new int[26];
    char[] chars = s.toCharArray();
    for (char ch : chars) {
        array[ch-97]++;
    }
    for (int i = 0; i < chars.length; i++) {
        char ch = chars[i];
        if (array[ch - 97] == 1) {
            return i;
        }
    }
    return -1;
}

8.出现次数最多的单词-力扣 819

简洁解法 14 ms

public String mostCommonWord(String paragraph, String[] banned) {
    Set<String> banSet = Set.of(banned);
    HashMap<String, Integer> map = new HashMap<>();
	String[] split = paragraph.toLowerCase().split("[^A-Za-z]+");
    for (String key : split) {
        if(banSet.contains(key)) {
            continue;
        }
        map.compute(key, (k, v) -> v == null ? 1 : v + 1);
    }
	Optional<Map.Entry<String, Integer>> optional = map.entrySet().stream().max(Map.Entry.comparingByValue());
    return optional.map(Map.Entry::getKey).orElse(null);
}

后两行避免 lambda，12 ms

public String mostCommonWord(String paragraph, String[] banned) {
    Set<String> banSet = Set.of(banned);
    String[] split = paragraph.toLowerCase().split("[^A-Za-z]+");
    HashMap<String, Integer> map = new HashMap<>();
    for (String key : split) {
        if(banSet.contains(key)) {
            continue;
        }
        map.compute(key, (k, v) -> v == null ? 1 : v + 1);
    }
    Integer max = 0;
    String maxKey = null;
    for (Map.Entry<String, Integer> e : map.entrySet()) {
        Integer value = e.getValue();
        if (value > max) {
            max = value;
            maxKey = e.getKey();
        }
    }
    return maxKey;
}

避免正则匹配 5ms

public String mostCommonWord(String paragraph, String[] banned) {
    Set<String> banSet = Set.of(banned);
    HashMap<String, Integer> map = new HashMap<>();
    char[] chars = paragraph.toLowerCase().toCharArray();
    StringBuilder sb = new StringBuilder();
    for (char ch : chars) {
        if (ch >= 'a' && ch <= 'z') {
            sb.append(ch);
        } else {
            put(banSet, map, sb);
            sb = new StringBuilder();
        }
    }
    put(banSet, map, sb);

    Integer max = 0;
    String maxKey = null;
    for (Map.Entry<String, Integer> e : map.entrySet()) {
        Integer value = e.getValue();
        if (value > max) {
            max = value;
            maxKey = e.getKey();
        }
    }
    return maxKey;
}

private static void put(Set<String> banSet, HashMap<String, Integer> map, StringBuilder sb) {
    if (sb.length() > 0) {
        String key = sb.toString();
        if(!banSet.contains(key)) {
            map.compute(key, (k, v) -> v == null ? 1 : v + 1);
        }
    }
}

sb 避免每次新建 4ms

sb.setLength(0);