从根到叶：深度理解哈希表

直接定址法作为一种哈希函数，具有以下优点和缺点：

优点：

• 简单快速：直接定址法的计算过程非常简单，只需将输入数据直接转换为哈希值，没有复杂的计算步骤，因此计算速度非常快。
• 低冲突率：由于每个输入数据都有唯一的哈希值，冲突的概率非常低。在哈希表大小和输入数据范围匹配的情况下，冲突几乎是不会发生的。

缺点：

•  依赖数据范围：直接定址法要求输入数据的范围与哈希表的大小相匹配，如果数据范围过大或过小，可能会导致哈希冲突或者浪费存储空间。
• 分布不均匀：如果输入数据的分布不均匀，某些哈希值可能会被频繁使用，而其他哈希值很少使用，导致哈希表的性能下降。
• 冲突解决困难：直接定址法在处理冲突时比较困难，因为不同的输入可能会映射到相同的哈希值。当出现冲突时，需要采取额外的措施解决，如链地址法或开放定址法。

2.2除留余数法

负载因子（Load Factor）是指哈希表中已存储元素数量与哈希表总容量之间的比率关系。它用来衡量哈希表的填充程度。

负载因子通常用公式表示为：负载因子 = 已存储元素数量 / 哈希表总容量

例如，如果哈希表中已存储了100个元素，而哈希表的总容量为200，那么负载因子为 100/200 = 0.5。

哈希冲突-线性探测法

优点：
1. 减少聚集性问题：相比于线性探测，二次探测能够更均匀地分布元素，减少聚集性问题。这意味着元素在哈希表中的分布更加均匀，减少了长串连续占用的槽位，提高了查找和插入操作的效率。
2. 较简单的实现：相对于其他开放寻址法方法（如双重哈希），二次探测的实现较为简单，不需要额外的哈希函数。

缺点：
1. 探测序列不完整：二次探测可能导致探测序列不完整，即某些槽位永远不会被访问到。这是因为二次探测使用的二次函数只能探测到特定的位置，可能无法遍历整个哈希表，导致某些槽位永远不会被使用。
2. 聚集性问题仍可能存在：尽管相对于线性探测，二次探测能够减少聚集性问题，但在高负载因子下仍可能出现聚集。当哈希表填充程度较高时，依然存在连续的哈希冲突，导致元素聚集在一起，影响操作的效率

package HashBucket;

public class hashBucket {
    static class Node{
        public int key;
        public int val;
        public Node next;
        public Node(int key,int val){
            this.key = key;
            this.val = val;
        }

    }
    public Node[]  array;//哈希链表
    public int usedSize;//存放多少个数据
    public float loadFactor = 0.75f;

    public hashBucket(){
        array = new Node[10];
    }

    public void put(int key,int val){
        int index = key % array.length; // 计算key在数组中的索引位置
        //遍历index下标的链表,是否存在key,存在就更新value,不存在就头插法
        Node cur = array[index];//array[index]是一个结点
        while (cur != null) { // 遍历链表
            if (cur.key == key) { // 如果当前节点的key与目标key相等
                cur.val = val; // 更新节点的value值
                return;
            }
            cur = cur.next; // 继续遍历下一个节点
        }
        // 链表遍历完成，未找到目标key，执行插入操作

        Node node = new Node(key, val); // 创建一个新的节点，存储目标key和value
        node.next = array[index]; // 将新节点的next指向当前索引位置的链表头节点
        array[index] = node; // 将新节点设为当前索引位置的链表头节点
        usedSize++; // 更新已使用的大小
        if(doLoadFactor()> 0.75){
            //进行扩容
            resize();
        }
    }

    private void resize(){
        Node[]  newArray =  new Node[2* array.length];
        //遍历原来的数组
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while(cur!=null){
                Node tmp = cur.next;
                int newIndex = cur.key % newArray.length;
                //采用头插法 插入到新数组的 newIndex下标
                cur.next = newArray[newIndex];
                newArray[newIndex] = cur;
                cur = tmp;
            }
        }
    }
    private float doLoadFactor(){
        return usedSize * 1.0f/ 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;


    }


}

视频展示如下：

补充知识点：当散列表扩容时需要注意的事项

1.为什么要用到tmp存放cur.next
因为党cur结点移动到新的索引址后,cur.next就存放的是在同一个索引值的下标的地址了,导致原来的就丢失了

2,扩容时需要注意什么:
应当对当时的结点进行遍历,然后放到合适的数组下标,比如没扩容之前元素14放在4下标,扩容之后应当放到数组14下标的位置(往后放)

3.5哈希桶<K,V>模型

假设现在定义在hashBucket2类中，通过定义泛型 <K, V>，允许存储任意类型的键（Key）和值（Value）对象。

在put方法中，通过传入键（K key）和值（V val）的参数，可以将键值对存储到散列表中。在创建新的节点时，使用传入的键和值来构造一个Node<K, V>对象，并将其插入到对应桶的链表头部。

hashBucket2类实现的代码如下：

package HashBucket;

public class hashBucket2<K, V> {
    static class Node<K, V> {
        public K key; // 节点的键
        public V val; // 节点的值
        public Node<K, V> next; // 下一个节点的引用

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

    public Node<K, V>[] array; // 桶数组
    public int usedSize; // 已使用的桶数量
    public static final float DEFAULT_LOAD_FACTOT = 0.75f; // 默认装载因子

    public hashBucket2() {
        array = (Node<K, V>[]) new Node[10]; // 初始化桶数组，初始大小为10
    }

    public void put(K key, V val) {
        int hash = key.hashCode() % array.length; // 计算键的哈希码，并对桶数组长度取模，得到桶的索引
        int index = hash % array.length; // 计算桶的索引
        Node<K, V> cur = array[index]; // 获取桶对应的链表头节点
        while (cur != null) {
            if (cur.key.equals(key)) {
                // 键已存在，更新值
                cur.val = val;
                return;
            }
            cur = cur.next; // 继续遍历下一个节点
        }
        Node<K, V> node = new Node(key, val); // 创建新的节点
        node.next = array[index]; // 将新节点的next指向桶的原头节点
        array[index] = node; // 将新节点设为桶的头节点，实现头插法
        usedSize++; // 更新已使用的桶数量
    }

    public V get(K key) {
        int hash = key.hashCode(); // 计算键的哈希码
        int index = hash % array.length; // 计算桶的索引
        Node<K, V> cur = array[index]; // 获取桶对应的链表头节点
        while (cur != null) {
            if (cur.key.equals(key)) {
                // 找到与键匹配的节点，返回对应的值
                return cur.val;
            }
            cur = cur.next; // 继续遍历下一个节点
        }
        return null; // 未找到匹配的键，返回null
    }
}

提示：Java中的泛型允许在运行时使用任意类型的对象，因此可以存储各种类型的对象

package HashBucket;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

class Student{
    String id;
    public  Student(String id){
        this.id = id;
    }

    //会根据id生产hashcode
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return Objects.equals(id, student.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}
public class Test {
    public static void main(String[] args) {
        Student student1 = new Student("563342523");
        Student student2 = new Student("563342523");
        hashBucket2<Student,Integer> hashbucket2 = new hashBucket2<>();
        hashbucket2.put(student1,20);
        //通过存入student1对象，可以查看student2的val，因为在相同位置
        Integer val = hashbucket2.get(student2);
        System.out.println("Value for student2: " + val);

    }
}

这里主要介绍的是(重点)：当需要自定义相等性比较和哈希码计算时，必须重写equals和hashCode方法，以确保对象在比较和存储时的一致性和正确性。重写这两个方法可以根据对象的内部状态来确定相等性，并为相等的对象生成相同的哈希码，使它们能够正确地在散列表中进行操作。

比如在给定的代码中，Studentb重写了equals和hashCode方法，根据id字段来判断对象的相等性和计算哈希码。由于student1和student2的id字段值相同，根据equals方法的逻辑，它们被认为是相等的对象。

当student1作为键存入散列表时，散列表会根据hashCode方法计算出哈希码，并将键值对存储在相应的桶位置。

接下来，当使用student2作为键调用散列表的get方法时，散列表会根据hashCod方法计算出student2的哈希码，并在相应的桶位置进行查找。由于student1和student2的哈希码相同，根据散列表的逻辑，它们会被认为是相等的键。

运行如下：

如果没有重写equals和hashCode方法：

package HashBucket;

import java.util.HashMap;

class Student {
    String id;

    public Student(String id) {
        this.id = id;
    }
}

public class Test {
    public static void main(String[] args) {
        Student student1 = new Student("563342523");
        Student student2 = new Student("563342523");

        HashMap<Student, Integer> map = new HashMap<>();
        map.put(student1, 20);

        // 由于没有重写 hashCode() 和 equals() 方法，student1 和 student2 被视为不同的对象
        // 所以无法通过 student2 获取相应的值
        Integer val = map.get(student2);
        System.out.println(val);  // 输出: null
    }
}

Student 类未重写 hashCode() 和 equals() 方法。因此，尽管 student1 和 student2 的ID相同，它们被视为不同的对象。当试图使用 student2 作为键来获取值时，由于哈希表中的键不匹配，返回的值为 null。

力扣-只出现一次的数字

力扣-复制带随机指针的链表

1. 创建一个 HashSet（哈希集合）用于存储宝石的字符。
2. 遍历宝石字符串 jewels 的每个字符 ch，将其添加到 hashset 中。
3. 初始化一个计数器 count 为 0。
4. 遍历石头字符串 stones 的每个字符 ch，如果 hashset 包含字符 ch，则增加 count 的值。
5. 返回计数器 count 的值，即宝石字符串在石头字符串中出现的次数。