哈希表，Hash Table，也稱為散列表。

哈希碰撞

key映射到同一個索引位置，叫做哈希碰撞。

哈希碰撞一般有兩種解決方法：拉鍊法 和 線性探測法。

1. 拉鍊法
   發生哈希衝突的元素被存儲在鏈表中。
2. 線性探測法
   在開放定址算法裏，線性探測法是散列解決衝突的一種方法，當hash一個關鍵字時，發現沒有衝突，就保存關鍵字， 如果出現衝突，則就探測衝突地址下一個地址，依次按照線性查找，直到發現有空地址為止，從而解決衝突。

常見的3種哈希結構

• 數組
• set（集合）
• map（映射）

題目：有效的字母異位詞

力扣 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 僅包含小寫字母

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/valid-anagram
著作權歸領釦網絡所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。

方法1 ：使用Map統計每個字符出現的次數。

import java.util.*;
class Solution {
    public boolean isAnagram(String s, String t) {
        if(s == null || t == null){
            return false;
        }
        if(s.equals(t)){
            return true;
        }

        Map<Character, Integer> map1 = putInMap(s);
        Map<Character, Integer> map2 = putInMap(t);
        return map1.equals(map2);
    }

    /**
        把每一個字符串拆成 char數組，每個char作為key，放到map中，每出現一次，value值加1，最後比較map是否相同
     */
    Map<Character, Integer> putInMap(String s){
        Map<Character, Integer> map1 = new HashMap<>();
        char[] c1 = s.toCharArray();
        for(int i = 0; i < c1.length; i++){
            if(map1.get(c1[i]) == null){
                map1.put(c1[i], 1);
            }else{
                map1.put(c1[i], map1.get(c1[i])+1);
            }
        }
        return map1;
    }
}

方法2：使用每個字符的ASCII值，作為數組的索引，計算每個字符出現的次數。

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s == null || t == null){
            return false;
        }
        if(s.equals(t)){
            return true;
        }

        int[] arr1 = countChar(s);
        int[] arr2 = countChar(t);
        return equalsArray(arr1, arr2);
    }

    /**計算每一個字符出現的次數， 26位長的數組，每一位置代表每個字母表中的一個字母
     */
    int[] countChar(String s){
        int[] alphabet = new int[26];
        char[] c1 = s.toCharArray();
        for(int i = 0; i < c1.length; i++){
            int index = c1[i] - 'a';
            alphabet[index]++;
        }
        return alphabet;
    }
    //比較數組相等
    boolean equalsArray(int[] arr1, int[] arr2){
        for(int i = 0; i < 26; i++){
            if(arr1[i] != arr2[i]){
                return false;
            }
        }
        return true;
    }
}

方法2：優化版，只使用一個數組，先加值，再減值，如果為0則為相同。
(實際測試性能並未提升...)

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s == null || t == null){
            return false;
        }
        if(s.equals(t)){
            return true;
        }

        int[] arr = new int[26];
        char[] chars1 = s.toCharArray();
        for(int i = 0; i < chars1.length; i++){
            arr[chars1[i]-'a']++;
        }

        char[] chars2 = t.toCharArray();
        for(int i = 0; i < chars2.length; i++){
            arr[chars2[i]-'a']--;
        }

        for(int i = 0; i < 26; i++){
            if(arr[i]!=0){
                return false;
            }
        }
        
        return true;
    }

}