数据结构——哈希表

f(x) = 2x + 1
//输入 x = 2
//输出 f(x) = 5

哈希函数：
key % array.length == index //数组下标
例如：
arr.length = 10，那么：
4 % 10 = 4;
14 % 10 = 4;
24 % 10 = 4;
以上的 4，14，24 这三个元素都放入数组下标为 4 的数组中，通过单链表串起来

import java.util.Objects;
class Person{
    public String ID;
    public Person(String ID){
        this.ID = ID;
    }
    @Override
    public String toString() {
        return "Person{" +
                "ID='" + ID + '\'' +
                '}';
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return Objects.equals(ID, person.ID);
    }
    @Override
    public int hashCode() {
        return Objects.hash(ID);
    }
}
public class Test {
    public static void main(String[] args) {
        Person person1 = new Person("123abc");
        Person person2 = new Person("123abc");
        System.out.println(person1.hashCode());
        System.out.println(person2.hashCode());
    }
}

import java.util.Objects;
class Person{
    public String ID;
    public Person(String ID){
        this.ID = ID;
    }
    @Override
    public String toString() {
        return "Person{" +
                "ID='" + ID + '\'' +
                '}';
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return Objects.equals(ID, person.ID);
    }
    @Override
    public int hashCode() {
        return Objects.hash(ID);
    }
}
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 double DEFAULT_LOAD_FACTOR = 0.75;//默认的负载因子
    public HashBucket2() {
        this.array = (Node<K,V>[])new Node[10];
    }
    /**
     * 向哈希表中添加 key 和 val
     */
    public void put(K key, V val){
        //1. 通过哈希函数, 找到对应的 index
        //key 这个引用要通过 hashcode()方法转换成整数
        int index = key.hashCode() % array.length;
        //2. 查找 key 对应的节点
        Node<K,V> cur = array[index];
        while (cur != null){
            if(key.equals(cur.key)){ //引用类型比较使用 equals
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        //3. 程序走到这里，说明我们没有找到重复的 key, 那我们可以利用单链表的头插法进行操作
        Node<K,V> node = new Node<K,V>(key,val);
        node.next = array[index];
        array[index] = node; //更新头节点
        usedSize++; //添加一个不重复的 key, 需要将哈希表的元素个数 +1
        double loadFactor = 1.0 * usedSize / array.length;
        //负载因子越大，产生的哈希冲突的可能性就越大，
        //那么我们需要增大哈希表长度来减小哈希冲突
        if(loadFactor >= DEFAULT_LOAD_FACTOR){
            resize();
        }
    }
    /**
     * 将旧数组的每个元素，往新数组中放，并按照哈希函数重新调整
     */
    private void resize() {
        Node<K,V>[] newArray = (Node<K,V>[])new Node[array.length*2];
        for (int i = 0; i < array.length; i++) {
            Node<K,V> cur = array[i];
            while (cur != null){
                Node<K,V> curNext = cur.next; //先记录一下旧数组 i 下标的某节点的后继节点
                //1. 通过重新哈希, 找到新数组对应的 index
                int index = cur.key.hashCode() % newArray.length;
                //2. 开始往新的数组调整
                cur.next = newArray[index];
                newArray[index] = cur;
                cur = curNext;
            }
        }
        array = newArray; //让旧数组引用新数组，那么旧数组最终将被回收
    }
    /**
     * 通过 key, 找出对应的 val
     */
    public V get(K key){
        //1. 通过哈希函数, 找到对应的 index
        int index = key.hashCode() % array.length;
        //2. 查找 key 对应的 val 并返回
        Node<K,V> cur = array[index];
        while (cur != null){
            if(key.equals(cur.key)){
                return cur.val; //找到了
            }
            cur = cur.next;
        }
        return null;
    }
    public static void main(String[] args) {
        Person person1 = new Person("123abc");
        Person person2 = new Person("123abc");
        //Person 是我们自定义的类
        HashBucket2<Person,String> hashBucket2 = new HashBucket2<>();
        hashBucket2.put(person1,"hello world");
        System.out.println(hashBucket2.get(person2));
    }
}