【Java se】简述哈希表（主要描述新增过程）

目录

数组与链表

数组

    在学习Java的初期，我们认识了一种能够存储多个数据的数据结构——数组，其中数据在空间中是连续的，因其具有索引值的原因，它在根据索引值查询数据时拥有着很大的优势，但是在对内容进行增、删操作的时候却是很复杂的。

    我们简单创建一个长度为5的数组：

    删除索引值为2元素时，数组的变化过程。

     数组新增过程与删除过程类似，比如要在索引值为2的位置新增元素，索引值>=2的所有元素都要后移一个，十分复杂，效率低。

链表

    而链表是每个值的空间可以不连续的一种数据结构。

    链表有着增删快的特点。

    增加元素时：①更改上一个元素的指向地址值（更改为新增元素的地址值）

                          ②更改增加元素的指向地址值（更改为上一个元素原本指向的地址值）

    删除同理。

    但是链表在查询数据时没有优势，只能通过逐个遍历的方式来进行查询。

    为提高效率有双向链表的存在，指从两个方向来遍历查找元素，但是速度不会比数组快。 

哈希表

    现在我们引入这样一个数据结构，它是由数组和链表/红黑树结构组合而成的。

    当我们学习到集合时，会学到Set接口的一个实现类：HashSet，它的底层就是使用了哈希表（HashMap）的数据结构，它的特点是：无索引值，元素不重复。

哈希表的新增过程

public static void main(String[] args) {
        HashSet<Integer> list = new HashSet<>();
        list.add(10);
        list.add(10);
        list.add(20);
        list.add(30);
        System.out.println(list);  //输出结果为：[20, 10, 30]
    }

    我们来创建一个HashSet类型的集合，根据关键性原码来简述一下元素的新增过程。

//此时进行增加操作，e为我们新增的元素值，E为元素的泛型：Integer
public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

//此时add相当于进行了HashMap中的put方法，key为我们新增的元素值
public V put(K key, ...) {
        return putVal(hash(key), ...);
    }

//此时key为我们新增的元素值
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    ①hash方法对新增的值进行了一定的操作，我们新增的元素不为null，则通过(h = key.hashCode()) ^ (h >>> 16)计算元素的哈希值，返回给put方法。

final V putVal(int hash, ...) {}

    计算完hash值将结果传入 putVal方法。

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;  //OldCap为0
        int oldThr = threshold;  //oldThr为0
        int newCap, newThr = 0;
        if (oldCap > 0) {
            ...
        }
        else if (oldThr > 0) 
            ...
        else {        //执行此代码块中操作       
            newCap = DEFAULT_INITIAL_CAPACITY;  //数组的初始长度为16
        }
        ...
}

    ②添加第一个值时数组还未创建，则第一次添加后，将数组长度初始化为16，数组类型为java.util.HashMap$Node。

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        ...
}

    Node类型中有个成员变量next，并且类型也是Node，可知这是一个单向链表结构，next表示指向的下一个元素。

final V putVal(int hash, ...) {
        if ((p = tab[i = (n - 1) & hash]) == null)  
        //通过某操作计算出元素索引值i（伪索引）
        ...
}

    ③数组已经创建，数组长度为16。上述计算出元素伪索引的操作课简单描述为hash%数组长度。因此可得出0~15之间的某一个值。

final V putVal(int hash,...) {
        ...
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        ...
}

    因为是添加的第一个元素，索引值位置的值一定为null，此时会new一个Node类型的对象。

    

     进行操作后得出索引值位置：

     ④如果新增的位置为null，则直接新增。

final V putVal(int hash, ...) {
        ...
       
            else {
                ...
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        ...
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                         //p为此索引值下已存在的值
                         //k为新增的值
                        break;
                    p = e;
                    ...
                }
            ...
}

    ⑤如果新增位置不为null时，因为Set接口中规定元素是不能重复的，则通过p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))进行元素是否重复的判断。

    因为Node中存的都是引用数据类型，因此==比较的是地址值。

    简单来说就是将（哈希值相同 &&（地址值相同 ||  equals值相同)) 值作为判定条件。

    我们认为两个值地址相同或者值相同，如String中，两个对象的地址值不同，但是当他们是指向同一个字符串常量池的位置时，通过equals比较时值相同，我们便可以说这两个值是相等的。

    因此，如果我们自定义一个类，将他作为HashSet的泛型时，如果想达到存入的值是不重复的效果，需在类中重写HashCode（）和 equals（）方法。

• 当元素不重复时。将元素新增在该索引值位置链表的最后面。
• 当元素重复时，放弃新增。

    可以看出当索引值位置有值时会添加到该索引值位置链表的最后面。（即next为null的地方）

    我们也可以看出来链表在空间上的位置时不连续的。

总结新增过程：

1.计算元素的哈希值

2.当数组已创建，通过哈希值%数组长度确定元素索引值位置。

3.当该索引值位置为null时，直接新增。

4.当该索引值位置不为null时，判定元素是否重复

判断是否重复的方法：比较两个对象的哈希值 && (地址值相同 || equals相同)

• 重复，则新增到该索引值位置链表的最后面
• 重复，则不新增

哈希表是如何进行扩容的（简述）

什么时候扩容：

①当同一索引值下元素个数>8，且数组长度<64（未达到树化条件）

    新容量 = 旧容量 << 1（新容量是旧容量的2倍）

②当同一索引值下元素个数>8，且数组长度>=64（未达到树化条件）

    将链表结构转换为红黑树

③当索引值的占用率超过75%进行扩容。

• 如果同一索引值下的元素个数过多，则会增加查询的时间，扩容后元素排列会有变化
• 如0索引值下元素超过8个，进行第一次扩容，扩容后会将本来放在0索引下的元素逐一分配给0索引和16索引
• 当进行第二次扩容，0索引值的元素分配给0和32,16索引值的元素分配给16和48
• 索引值占用率的默认值为0.75（如数组长度为16,13个索引值有元素就扩容），此为加载因子，也可以通过有参构造设置加载因子
• 我们也可以指定容量（哈希表数组长度），但实际创建的数组长度为最近此值的2次方值（如指定100会实际创建长度为128的数组）

构造方法参数含义public HashSet() public HashSet(int capacity)capacity为容量public HashSet(int capacity, float loadFactor)loadFactor为加载因子

关于哈希表的一些其他问题

1.为什么HashSet是无序的

    因为先新增的元素可能算出的索引值靠后，后新增的元素值算出来可能在前，而获取元素的值是从前向后的（先获取索引值为0的）。

    从我们举的例子可以看出来，存入的顺序为10,20,30。而输出（获取）的结果为：[20, 10, 30]。

2.为什么哈希表没有索引值

    我们在上面说的都是伪索引，是Node类型数组的索引值，哈希表底层是Node类型的数组，而Node是链表结构，每个索引值下面可能会有多个元素，因此获取哈希表中的元素不能像数组一样通过下标获取。