一、概念

1.1 哈希表的概念

（1）顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找⼀个元素时，必须要经过关键码的多次⽐较。顺序查找时间复杂度为O(N)，平衡树中为树的⾼度，即O(log2N)，搜索的效率取决于搜索过程中元素的⽐较次数。

（2） 理想的搜索⽅法：可以不经过任何⽐较，⼀次直接从表中得到要搜索的元素。如果构造⼀种存储结
构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建⽴⼀一映射的关系，那么在 查找时通过该函数可以很快找到该元素。

（3）当向该结构中：

• 插入元素
根据待插⼊元素的关键码，以此函数计算出该元素的存储位置并按此位置进⾏存放。
• 搜索元素
对元素的关键码进⾏同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素
⽐较，若关键码相等，则搜索成功。

该⽅式即为哈希(散列)⽅法，哈希⽅法中使⽤的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)。

（4）举例

1.2 冲突-概念

不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

1.3 冲突-避免

由于哈希表底层数组的容量往往是⼩于实际要存储的关键字的数量的，这就导致⼀个问题，冲突的发生是必然的，但我们能做的应该是尽量的降低冲突率。

二、冲突-避免-哈希函数设计

1. 设计合理的哈希函数
2. 调节负载因子

三、 常见哈希函数

3.1 直接定制法–(常⽤)

（1）取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

• 优点：简单、均匀
• 缺点：需要事先知道关键字的分布情况。
• 使⽤场景：适合查找⽐较⼩且连续的情况。

（2）OJ题

LC387.字符串中的第一个唯一字符

3.2 除留余数法–(常⽤)

设散列表中允许的地址数为m，取⼀个不⼤于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址。

三、冲突-避免-负载因子调节

已知哈希表中已有的关键字个数是不可变的，那我们能调整的就只有哈希表中的数组的⼤⼩。

四、 冲突-解决

解决哈希冲突两种常⻅的⽅法是：闭散列和开散列

4.1 冲突-解决-闭散列

闭散列：也叫开放地址法，当发⽣哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位 置，那么可以把key存放到冲突位置中的“下⼀个” 空位置中去。那如何寻找下⼀个空位置呢？

4.2 冲突-解决-开散列/哈希桶（重点）

手动实现哈希桶：

//手动实现哈希桶
public class HashBucket {
    //节点数组
    static class Node{
        //hashmap 是 K V 形式
        public int key;
        public int val;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
     }

    public Node[] array = new Node[10];//array数组
    public int usedSize;// 负载因子 = usedSize / len
    public static final float LOAD_FACTOR  = 0.75f;

    public void put(int key,int val){
        int index = key % array.length;
        //遍历index数组下的链表，如果有相同的key 则更新val
        Node cur = array[index];
        while(cur != null){
            if(cur.key == key){
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        //2.这里写头插法 尾插法可自己再完善
        Node node = new Node(key,val);
        node.next = array[index];
        array[index] = node;
        usedSize++;

        //3.重新计算当前的负载因子 是不是超过了 我们规定的负载因子
        if(calcloadFactor() >= LOAD_FACTOR){
            //扩容
            resize();
        }
    }

    private void resize(){//实现扩容

        Node[] newArray = new Node[array.length*2];
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while(cur != null){
                int newIndex = cur.key % newArray.length;
                //把当前节点 放到新的数组的newIndex 位置 -- 头插法
                Node curN = cur.next;
                cur.next = newArray[newIndex];
                newArray[newIndex] = cur;
                cur = curN;
            }
            array = newArray;
        }
    }

    private float calcloadFactor(){
        return usedSize*0.1f / array.length;
    }

    public int get(int key){
        int index = key % array.length;
        Node cur = array[index];
        while(cur != null){
            if(cur.key == key){
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }
}

五、哈希表相关 Oj题

5.1 只出现一次的数字

（1）LC136.只出现一次的数字

（2）图解

（3）Java 实现

class Solution {
    public int singleNumber(int[] nums) {
       Set<Integer> set = new HashSet<>();

       for(int i = 0;i < nums.length;i++){
            if(!set.contains(nums[i])){
                set.add(nums[i]);
            }else{
                set.remove(nums[i]);
            }
       } 

       for(int i = 0;i < nums.length;i++){
            if(set.contains(nums[i])){
                return nums[i];
            }
       }
       return -1;
    } 
}

5.2 随机链表的复制

（1）LC138.随机链表的复制

（2）图解

（3）Java 代码实现

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null; // 处理空链表
        
        Map<Node, Node> map = new HashMap<>();
        
        // 第1遍遍历：创建新节点，并建立原节点->新节点的映射
        Node cur = head;
        while (cur != null) {
            Node newNode = new Node(cur.val); // 修正：构造方法参数应为 cur.val
            map.put(cur, newNode);
            cur = cur.next;
        }
        
        // 第2遍遍历：连接新节点的 next 和 random
        cur = head;
        while (cur != null) {
            Node copyNode = map.get(cur);
            copyNode.next = map.get(cur.next);    // 修正：直接取映射的节点
            copyNode.random = map.get(cur.random); // 修正：直接取映射的节点
            cur = cur.next;
        }
        return map.get(head); // 返回新链表的头节点
    }
}

5.3 宝石与石头

（1）LC771.宝石与石头

（2）图解

（3）Java 代码实现

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
    Set<Character> jewelSet = new HashSet<>();
        // 将所有宝石类型存入集合
        for (char c : jewels.toCharArray()) {
            jewelSet.add(c);
        }
        
        int count = 0;
        // 遍历所有石头，统计宝石数量
        for (char c : stones.toCharArray()) {
            if (jewelSet.contains(c)) {
                count++;
            }
        }
        return count;
    }
}

5.4 旧键盘

（1）牛客：旧键盘

（2）图解

（3）Java 代码实现

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str1 = in.nextLine();//从键盘敲得键
            String str2 = in.nextLine();
            func(str1, str2);
        }

        
    }

    private static void func(String str1, String str2) {
            HashSet<Character> set = new HashSet<>();
            HashSet<Character> set1 = new HashSet<>();

            for (char ch : str2.toUpperCase().toCharArray()) {
                set.add(ch);
            }

            for (char ch : str1.toUpperCase().toCharArray()) {
                if (!set.contains(ch) && !set1.contains(ch)) {
                    System.out.print(ch);
                    set1.add(ch);
                }
            }       
    }
}