Java数据结构-哈希表

1. 概念

哈希表（Hash table，也叫散列表），是根据关键码值(Key)而直接进行访问的数据结构。通过把关键码值映射到表中一个位置来访问记录，能够加快查找的速度。这个映射函数叫做哈希函数，存放记录的数组叫做哈希表（所以，哈希表的本质其实是数组）。

例如

2. 哈希冲突

不同的关键字，通过同一个哈希函数，计算出相同的结果，这就叫哈希冲突
拿上面这个图举例，如果想插入44，44通过哈希函数，44%10得出结果为4，所以44应该存储在哈希地址为4的地方，可是这个地方已经被4霸占，这个现象就叫哈希冲突

2.1 冲突的避免

两种方法:1、设计合理的哈希函数，2、降低负载因子

2.1.1 设计合理的哈希函数

常见的哈希函数有:

• 直接定值法
• 除留余数法
• 平方取中法
• 折叠法
• 随机数法
• 数学分析法
  比较常用的有除留余数法：Hash(Key) = key%Capacity（Capacity指的是数组的长度）

2.1.2 降低负载因子

负载因子=存入表中的元素个数/哈希表的长度
负载因子越大，冲突率越高，也就是说，想要避免冲突，就需要扩容，当负载因子达到0.75(官方给出的)时，我们就要考虑扩容了

2.2 冲突的解决-闭散列

发生冲突了,我们不能坐视不管，需要解决冲突。解决冲突的一种方法是闭散列，也叫开放地址法。

1. 线性探测
   如
   
   插入14，发现哈希地址为4的位置已有元素，此时就往后找空位，插入到空位即可
   
   缺点：冲突的元素容易聚集在一个地方
2. 二次探测
   按照公式：H = (H0+i^2)%m
   H0表示第一次冲突时的位置(下标),i表示冲突的次数(第几次冲突),m是数组长度,要到插入的位置H

2.3 冲突的解决-开散列

开散列，也叫开放地址法、链地址法、哈希桶。
在Java中，这里的数组不是简单的数字，而是数组+链表，每个元素存储的是链表头结点的地址，冲突的元素都是头插或者尾插在链表中，链表的长度不会太长，当链表长度过长，这个链表则会变成红黑树！！！

3. 哈希桶的实现

public class HushBucket {

    public double LoadFactor = 0.75;//默认的负载因子

    static class Node {
        public int key;
        public int val;
        public Node next;

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

    //计算当前负载因子
    private double getLoadFactor() {
        return size * 1.0 / array.length;
    }

    //扩容
    private void resize() {
        //每个元素都需要重新哈希
        Node[] newArr = new Node[array.length * 2];
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            //遍历链表
            while (cur != null) {
                int newIndex = cur.key % newArr.length;
                Node cN = cur.next;
                cur.next = newArr[newIndex];
                newArr[newIndex] = cur;
                cur = cN;
            }
        }
        array = newArr;
    }

    public int size;//元素个数
    public Node[] array;//数组

    public HushBucket() {
        this.array = new Node[10];
    }

    public void put(int key, int val) {
        int index = key % array.length;
        Node cur = array[index];
        while (cur != null) {
            if (cur.key == key) {
                cur.val = val;
                return;//key不能重复,插入重复的key相当于更新val
            }
            cur = cur.next;
        }
        Node newNode = new Node(key, val);
        newNode.next = array[index];
        array[index] = newNode;
        size++;
        if (getLoadFactor() >= LoadFactor) {
            //当前负载因子大于等于默认负载因子,需要扩容
            resize();
        }
    }

    //获取key值的val
    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;
    }

}

注意事项：
扩容时，所有元素都需要进行重新哈希，因为容量变了，根据哈希函数计算的结果也会不同