JAVA集合之ArrayList、 LinkList、 Hash

ArrayList

看ArrayList先看一下他的名字，Array和List拼成的

• Array
  Array就是数组的意思，是基于索引(index)的数据结构，底层是一块连续的内存空间，它使用索引在数组中搜索和读取数据是很快的。Array获取数据的时间复杂度是O(1),但是要删除数据却是开销很大，因为这需要重排数组中的所有数据, (因为删除数据以后, 需要把后面所有的数据前移)，这也是ArrayList的问题
• List
  List—是一个有序的集合，可以包含重复的元素，提供了按索引访问的方式，它继承自Collection。List有两个重要的实现类：ArrayList和LinkedList
  image.png
• ArrayList
  可以看出ArrayList底层是基于数组Array的方式实现的，他和数组不同之处是大小动态增加，这就决定了他查找起来很快，但是增删就比较慢，除非直接追加到队尾，否则就要把数据重排（通过arraycopy实现的重排）。需要注意的是ArrayList是线程不安全的
  QQ20210115-111127@2x.png
  QQ20210115-111215@2x.png
  QQ20210115-111246@2x.png

LinkList

LinkList看一下他的名字，Link和List拼成的，List上边说了是JAVA中的集合，我们看下Link

• Link
  链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针连接次序实现的。每一个链表都包含多个节点，节点又包含两个部分，一个是数据域（储存节点含有的信息），一个是引用域（储存下一个节点或者上一个节点的地址）。
  一个节点类，其中节点类包含两个部分，第一个是数据域（你到时候要往节点里面储存的信息），第二个是引用域（相当于指针，单向链表有一个指针，指向下一个节点；双向链表有两个指针，分别指向下一个和上一个节点）。
  链表的特性就是查询慢一些（比较数组），但是增删会特别快，指定节点断开，插入重连即可完成增加。

  //单向链表
public class Node {
    public Object data;
    public Node next;

    public Node(Object e){
        this.data = e;
    }
}
//双向链表
public class Node {
    public Object e;
    public Node next;
    public Node pre;
    public Node(){

    }
    public Node(Object e){
        this.e = e;
        next = null;
        pre = null;
    }
}

image.png

看下数组和链表的对比

image.png

• LinkList
  LinkList以双向链表实现，链表无容量限制，但双向链表本身使用了更多空间，每插入一个元素都要构造一个额外的Node对象，也需要额外的链表指针操作。在添加和删除元素时具有比ArrayList更好的性能.但在get与set方面弱于ArrayList.当然,这些对比都是指数据量很大或者操作很频繁。允许元素为null，线程不安全。

HashMap

HashMap是结合了数组和链表的一种实现方式,new的时候会初始化一个数组，table = new Entry[capacity]（这个容量capacity需要注意，根据源码里的roundUpToPowerOf2方法，最好为2的次幂）; 创建一个Entry数组，也就是下面的table ,这个Entry结构就是static的包含key value 还有一个next的指针，指向下一个元素的引用，也就构成了链表。线程不安全，HashTable线程安全性能低(全锁)，ConcurrentHashMap性能安全比前者高效（分段锁，链表或红黑树）

QQ20210115-123508@2x.png

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);

    // Find a power of 2 >= initialCapacity
    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;

    this.loadFactor = loadFactor;
    threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    useAltHashing = sun.misc.VM.isBooted() &&
            (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    init();
}

数组中存储的每个元素Entry是key-value模式的

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

看下put方法，会根据元素对应key的hash值(主要看后四位)去计算下标，然后根据不同下标放入数组中，需要注意的是当hash值计算的下标相同的时候,如果key相同，则替换当前位置的值，如果key不同，则追加到当前角标元素对应的头部，此时这两个元素以链表形式存储。为了避免hash冲突，HashMap的默认长度为16(length-1二进制为1111)，其作用是相当于以16取模，能均匀分散到每个bucket中，避免出现单链表(即所有远程都追加到一个角标上)情况。解决hash冲突的方式一般分为链地址法，再Hash法，开放地址发，建立公共溢出区（hashmap 的解决方式为链地址法或拉链法）
装载因子0.75，当超过（默认长度）16*0.75这个阈值后会出发扩容

public V put(K key, V value) {
    //其允许存放null的key和null的value，当其key为null时，调用putForNullKey方法，放入到table[0]的这个位置
    if (key == null)
        return putForNullKey(value);
    //通过调用hash方法对key进行哈希，得到哈希之后的数值。该方法实现可以通过看源码，其目的是为了尽可能的让键值对可以分不到不同的桶中
    int hash = hash(key);
    //根据上一步骤中求出的hash得到在数组中是索引i
    int i = indexFor(hash, table.length);
    //如果i处的Entry不为null，则通过其next指针不断遍历e元素的下一个元素。
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

Java8中的Hashmap底层结构有一定的变化，还是使用的数组，但是数组的对象以前是Entry对，现在换成了Node对象（可以理解是Entry对，结构一样，存储时也会存key/value键值对、前一个和后一个Node的地址），以前所有的Entry向下延伸都是链表，Java8变成链表和红黑树的组合，数据少量存入的时候优先还是链表，当链表长度大于8，且总数据量大于64的时候，链表就会转化成红黑树，所以你会看到Java8的Hashmap的数据存储是链表+红黑树的组合，如果数据量小于64则只有链表(此时如果某一下标链表超过8，会触发扩容，不会树化)，如果数据量大于64，且某一个数组下标数据量大于8，那么该处即为红黑树。所以触发树化条件是两个：大于64且某一个数组下标链表数据量大于8。
链表转红黑树是链表长度达到阈值是8，红黑树转链表阈值为6(反树化)。因为经过计算，在hash函数设计合理的情况下，发生hash碰撞8次的几率为百万分之6，用概率证明。因为8够用了，至于为什么转回来是6，中间有个差值7可以防止链表和树之间频繁的转换，因为如果hash碰撞次数在8附近徘徊，会一直发生链表和红黑树的互相转化，为了预防这种情况的发生，设置为6

image.png

红黑树的节点查找的优先级从O(n)变成了O(logn)，如下图寻找48，只需要4此即可查到，比链表高效。

image.png