集合Collection

集合Collection

集合的长度是可变的，而数组的长度是不可变的，固定的 。

数组可以存储基本数据类型，也可以存储引用数据类型，而集合只可以存储引用数据类型

数组只能存放一种类型，而数组可以存放不同类型的，但是我们一般只存放一种类型 。

collection是集合的接口，它的子接口是list和set，他们都必须通过实现类来实现。

list接口的实现类主要又三种，ArrayList，LinkedList和Vector,而List下面的存储，可以存放可重复的元素，也是有序的，依次存储，Set下面的 则不可以。

collection：

接口的接口，对象的集合,单列集合，默认类型为object类型，使用前尽量知名类型，以免后期转换出现问题。

List接口

ArrayList： 它的底层是由数组来进行存储的，存储区域是连续的一块空间，默认大小是10，它可以自动扩容，每次扩容后都是原来的1.5倍。可以存放重复元素，扩容时采用的时Arrays.copyOf（）方法进行拷贝，拷贝之后原来的数组没有指向，很快就会倍垃圾回收期回收掉

private static final int DEFAULT_CAPACITY = 10;//数组默认初始容量
 
private static final Object[] EMPTY_ELEMENTDATA = {};// 传零的时候定义的
 
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//定义一个空数组，跟前面的区别就是这个空数组是用来判断ArrayList第一添加数据的时候要扩容多少。默认的构造器情况下返回这个空数组 无参构造出来的
 
transient Object[] elementData;//数据存的地方它的容量就是这个数组的长度，同时只要是使用默认构造器（DEFAULTCAPACITY_EMPTY_ELEMENTDATA ）第一次添加数据的时候容量扩容为DEFAULT_CAPACITY = 10 ，当前arraylist对象底层的数组地址。
 
private int size;//当前数组的长度

默认使用的是第二种

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

在创建时不指定容量的情况下，会返回一个长度为零的空数组，在调用add方法时，才触发扩容机制

当数组的大小大于原来的容量时，会触发扩容机制。

扩容机制

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

1.如果链表是由默认的方法来创建的，那么它最开始返回的是一个长度为零的空数组，此时数组的容量才会从零扩容成10，而后的容量才是按当前的1.5倍进行扩容的。

为啥扩容的是1.5倍呢？

int newCapacity = oldCapacity + (oldCapacity >> 1);

由扩容中的此行代码可以看出，它的新容量=旧容量+就容量右移一位（底层是二进制，右移一位相当于原来的大小除以2）因此可以看出它扩容后大容量是原来的1.5倍。（底层实现都是二进制位运算），因此啊（23除2的值为11）

而addAll的方法中，扩容机制有一些变化：

public boolean addAll(Collection c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

此时传进去的是整合后的总长度

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

它总是选择扩容后的容量与扩容前加上添加后的旧容量之中取一个最大的值作为一个新的容量，比如原来有10个，现在添加6个，它先进行扩容，扩容之后为15个，而此时需要十六个进行存储，此时他会选择较大的16作为新的容量。

它不存在缩容机制：

ArrayList没有自动缩容机制。无论是remove方法还是clear方法，它们都不会改变现有数组elementData的长度。但是它们都会把相应位置的元素设置为null，以便垃圾收集器回收掉不使用的元素，节省内存。ArrayList的缩容，需要我们自己手动去调用trimToSize()方法，达到缩容的目的。

查询块，增删慢----原因：查询时，直接可通过索引找到元素的位置，读出元素，速度快，而增删时，则是增加（删除）一个元素时，此元素后面的元素依次向后（向前）推移一个，速度慢。

LinkedList ： 它是由链表来实现存储的（双链表），存储区域不是连续的，它对容量没有要求，不需要扩容。可以存放重复元素。它的底层存储单元分为三部分。前驱 存储区域 后驱，前驱存放指针，指向上一个数组，后驱也存放指针，指向下一个数组。

增删快，查询慢----原因 虽然是链表，但是链表的节点也有编号，像索引但不是索引，而在查询时，是将链表一分为二，离哪一块近，第一块从头到尾，第二块是从尾向头查询，依次查询，速度慢。也是从第一个往后面找，找到与之匹配的索引值，然后读出元素。添加时是在某个地方直接加入，前驱指针指向上一个，后驱指针指向下一个，速度快。

Vector： 也是由数组来实现存储的，默认初始容量为10，存满之后，可自动扩容，扩容后就变为原来的2倍。它是线程安全的。但是效率低，可以存放重复元素

stack是Vector类的实现类

线程安全：vector所有的方法都是线程同步的，都带有synchronized关键字，是线程安全的，效率比较低，

public synchronized int capacity() {
        return elementData.length;
    }

set集合

不可重复，无序的一个集合，并且做了内部排序

HashSet：使用hash表（数组）存储元素，hashset是基于散列表结构实现的（数组加链表（可转红黑树））。线程不安全

 

允许有null值（因为hashmap中也支持null值和null键），无序的。底层是由hashmap实现的。可以用迭代器，foreach遍历

封装了一个hashMap对象来存储集合元素，（初始容量为16，负载因子为0.75，每次扩容为原来的2倍），它的元素存储实际是放在map中的key，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象。

HashSet下面有LinkedHsahSet链表维护元素的插入次序

保证元素的唯一性的两个方法，一个是hashCode，一个是equals（），hashset在存储过程中首先会调用元素的hashcode值，看hash值是否与已存入的hashset的元素的hash值是否相同，如果不同，直接添加到集合中，如果相同，再去调用equals方法和hash值相同的这些元素去比较，如果有相同的（返回true）那就不添加，反之添加。

TreeSet：底层实现为二叉树，元素排好序，线程不安全

有序，不能重复，key值不能为空，value值可以为空，

排序：实现comparable方法，重写compareTo方法

底层也使用了treeMap

 

Map

接口，键值对的集合（双链集合）

Hashtable接口实现类，同步，线程安全

HashMap 没有同步，线程不安全

hashmap的存储结构：

在jdk1.7及以前，采用的是数组加链表的方式存储数据，但是当链表特别长时，查询效率直线下降，时间复杂度为O（n），而jdk1.8之后，设计成了它到达某个特定的阈值时，就将链表转化为红黑树了

红黑树的特点：1.每个节点只有两种颜色，红或者黑

2.根节点必须时黑色

3.每个叶子节点都是黑色的空节点

4.从根节点到叶子节点，不能出现两个连续的红色节点

5.从任一节点出发，到它下边的子节点的路径包含的黑色节点数目都相同

红黑树是一个自平衡的二叉搜索树，因此可以使查询的时间复杂度将为O（logn）

它的存储是以key——value的方式存储的，首先会拿key计算出它的hash值，看是否已经存在相同hash值的键，若不存在将它的key-value保存进去，若存在，再通过equels方法去比较，如果key不同，则可以存进去，若相同，则覆盖掉原来的值

无参构造时，只传回来地址，容量无，put时才会开辟空间，

有参构造时，已经开辟空间了。

put方法

 public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
​
​
 /**
     *
     * @param hash  由key计算出来的 hash值
     * @param key   要存储的key
     * @param value  要存储的value
     * @param onlyIfAbsent  如果当前位置已存在一个值，是否替换，false是替换，true是不替换
     * @param evict  表是否在创建模式，如果为false，则表是在创建模式。
     */
​
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict)
​

put调的方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)//判断当前容量是否为空。
            n = (tab = resize()).length;//为空则去进行扩容
        if ((p = tab[i = (n - 1) & hash]) == null)//
            tab[i] = newNode(hash, key, value, null);
        else {
            Node e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

hash

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
equels

 public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry e = (Map.Entry)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }

hashmap的扩容机制：

if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node e;
                if ((e = oldTab[j]) != null) {//判断老链表是否为空，并且让e指向老链表头
                    oldTab[j] = null;//让老链表头为空
                    if (e.next == null)//判单链表e是否只有一个头链表。如果只有一个，
                        newTab[e.hash & (newCap - 1)] = e;//直接重新哈希，查找位置进行存储。
                    else if (e instanceof TreeNode)//判断是否为树
                        ((TreeNode)e).split(this, newTab, j, oldCap);
                    else { // preserve order  //此时说明链表下面有好几个数据
                        Node loHead = null, loTail = null;//定义头和尾
                        Node hiHead = null, hiTail = null;
                        Node next;
                        do {
                            next = e.next;//遍历节点
                            if ((e.hash & oldCap) == 0) {//如果值为零，以后放在新数组索引等于旧索引的地方，计为低位区链表，向将他们串起来
                                if (loTail == null)
                                    loHead = e;//前面没东西，直接放
                                else
                                    loTail.next = e;
                                loTail = e;//指针后移
                            }
                            else {//值不为零的情况，都将串到高位区，形成链表，这些将来的位置都是（旧数组当前索引+旧数组容量）
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;//将低位的最后一个位置的下一位改位空
                            newTab[j] = loHead;//将低位链表放进去
                        }
                        if (hiTail != null) {
                            hiTail.next = null;//将高位链表的最后一个元素的下一个指向空
                            newTab[j + oldCap] = hiHead;//将高位链表放进去
                        }
                    }
                }
            }
        }

每次扩容都将数组容量扩大为当前容量的2倍，为什么是二倍呢？

它的负载因子是0.75，容量达到当前容量*0.75时，就会触发扩容，为什么时0.75呢？简单来说是时间和空间的权衡，若小于0.75，例如是0.5的时候，则数组长度达到一半的时候就需要扩容，空间使用率大大降低，若大于0.75，则会增大hash冲突，影响查询效率。

它的转为为红黑树的条件是除了达到阈值8，数组长度也至少达到64，才能进行转化，为啥是64，是为了避免数组扩容和阈值树化之间的冲突。当树上的元素减少退化为6个时，就会退化为链表。

hashmap也可以自己顶以大小和负载因子，但是不减一自己定义负载因子，这里有一个问题，当我们定义的大小为14时，这里实际容量并不是14，而是我一个最接近14的2的n次幂，底层为了提高运算效率，底层都是二进制的

实现把一个数变为最接近二的n次方的方法。
static final int tableSizeFor(int cap) {
        int n = cap - 1;// 如果不减一, 当我们初始容器大小是2的幂次方时, 实际容器初始化大小是2的幂次方+1, 所以这里要对我们输入的初始化容器大小减一.造成空间浪费.
        n |= n >>> 1;//无符号右移
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

为啥扩容之后要把原来的值重新遍历出来，再重新hash到新的map中去呢？

因为长度扩大后，hash的规则也随之改变了，以前可能hash16的位运算，现在成32了，明显不一样了。

put时为啥之前用头插法，java8之后改成尾插了呢？

插入时，只是将元素添加进去，不会改变元素里面的结构。单向链表，包含hash值，key，value，next。

 

jdk8之前，它才用的是头插法，就是新添加进来，永远都在当前key的第一位，再扩容时，重新计算，重新加入的过程中可能差生环形链表的。（扩容转移前后，链表顺序倒置，在转移过程中，修改了原来链表中节点的引用关系）

jik8之后的改为尾插法，尾插法就是向链表的最后添加元素，避免生成环形链表。（原因是扩容转移后前后链表顺序不变，保持之前节点的引用关系）

哈希碰撞：

两个put的键算出来的hash值一样，这把这称为一次hash碰撞。

hash算法，将任意长度的字符串转化为固定长度的字符串，所以必存在一个输出串对应多个输入串的情况。碰撞是必然存在的。

TreeMap**红黑树对所有的key进行排序