什么是集合框架

集合框架是存储数据的容器

集合框架就是为了表示和操作集合的一种标准体系结构，包含三大部分对外的接口，接口的具体实现和算法。

接口即抽象出来的一组集合行为规范，实现则是具体的实现，是重用性很高的数据结构。

算法就是对数据进行操作，比如集合的排序，查找，增添等等算法。?
?

集合与数组的区别

? ?集合是可变长的，数组是定长的，集合存放对象类型，数组可以存放对象类型或者基本类型。

集合可以存放不同数据类型的对象，一个数组只能存储一个数据类型

常用集合类？?

? ? ? ? ?Collection子接口的List，Set，Queue。和Map子接口

?List，Set，Map三者的区别？List、Set、Map 是否继承自 Collection 接口？List、Map、Set 三个接口存取元素时，各有什么特点？

? ? ? ? List是列表，存储的数据是有序，可重复的。使用add，get方法存取

? ? ? ? set是集合，存储的数据是无序且唯一的。使用add，get方法存取

? ? ? ? map是图，存储的是键值对数据，key值唯一但无序，value可以多个，也可以无序。使用put，get方法?

list，set继承collection接口，map并不。?

集合框架底层数据结构（数据结构：就是容器中存储数据的方式）

?List：实现主要是ArrayList，LinkedList，和Queue

①Arraylist底层是数组的方式存储数据，初始化容量是10，当使用add方法向其中添加数据，则首先会判断size+1是否溢出，若没有则直接加入，若有则会调用grow方法扩容，A扩容一般是1.5倍，调用copyof的方法复制原有数组，再在尾部添加进该元素。get，set方法则，先判断index有无越界，没有则直接添加。remove方法则是在删除元素下标后一位开始复制，使用arraycopy的方法，就是使删除元素后边所有元素向前挪一位。

①.2? Vector是使用Synchtronized关键字修饰方法的线程安全的A，因此效率没有A高，他继承A，扩容大小默认为2倍。

①.3? Stack则继承Vector

②LinkedList底层使用双向链表存储数据，默认为0；首尾都能增删元素，add方法是采用addLast，尾插法。remove方法通过unlink方法将节点现有链接删去，然后使用link新建链接完成删除节点的操作。set，get方法则通过index与链表长度进行比较，大的话从尾部开始遍历，小则从头部开始。

③Queue 是队列方式存储数据，一般采用先进先出的方式，队列有阻塞队列和非阻塞队列，阻塞队列中ArrayBlockingQueue和LinkedBlockingQueue以及SynchtronizedQueue比较重要。

ABQ是底层使用数组来实现队列功能的，初始化要写长度，是线程安全的阻塞队列，可以选择采用公平锁，但是默认采用不公平锁，公平锁即依据线程申请锁资源的顺序来获得锁，其他线程取不到锁被阻塞进入阻塞队列也是队首的线程，下一次最先有机会获得锁。但是ABQ在消费者生产者模式中，生产者和消费者实际上使用的是同一把锁，因此生产和消费操作实际上是不能并行的。

LBQ则底层使用双向链表来实现队列功能，也是线程安全的，不初始容量的话，默认为Integer_MAX_Value,默认是不公平锁，生产者和消费者独立拥有锁，所以消费者和生产者操作是可以并行的，但是当生产速度远远大于消费速度时,会产生大量资源，可能使得内存溢出，并且因为使用的链表方式，每次进行生产或消费时新建或销毁一个node对象，这对于gc来说影响较大。

SQ则是线程安全的无容量的队列，即容量为一，只能生产一个，就消费一个，take方法使用lock锁，是线程安全的。

Set：hashSet,LinkedHashSet,TreeSet

①hashset底层采用hashmap底层采用散列表存取键值对的方式，使用add方法时，通过散列函数将对象的哈希值与数组大小-1进行按位与操作，得到存储位置下标，如果该位置已经有数据，则采用hashcode以及equals方法进行比较是否为同一元素，是的话则不添加，这就实现了set集合元素唯一的保证。get则通过下标取得元素，remove则采用equals方法找到元素删除。

②LinkedHashSet 底层是LinkedHashMap 采用双向链表维护元素顺序，顺序为插入顺序或者最近最少使用顺序，继承hashmap。

③TreeSet底层采用红黑树，也是有序的。

Map：hashmap，LinkedHashMap，Treemap，hashTable，currentHashMap

①hashmap1.8之后底层使用的是哈希表存储键值对来存储数据，以数组+链表+红黑树的方式，默认大小为16，扩容因子为0.75，hashmap数组长度只能是2的次方，当使用put方法添加数据的时候
首先将对象的散列值与数组长度-1按位与之后得到数组下标，如果该位置没有数据则put进去，如果有则代表发送哈希冲突，hashmap使用拉链表的方式，也就是将同一哈希值下标的对象使用链表存储，链表头结点则放在数组中。如果插入时，链表长度超过8且数组长度超过64，则进行链表转红黑树的方式进行扩容。

get方法通过key值进行equals比较获取value的值。remove则一样。

红黑树是什么？底层怎么实现？

红黑树是一种不完美的平衡二叉树，底层是基于2,3,4树概念的实现。它相对平衡二叉树，严格要求左右子树高度差不大于一不同，而只是要求一种弱平衡，只要最长路径比最短路径不超过两倍既可，而且在进行插入，删除时对树平衡的维护也比平衡二叉树Asl好，他做到了在不超过3次旋转就能达到一定平衡，时间复杂度控制在对数级。

红黑树要求有五点必须做到才是红黑树：

1,节点是黑色或者红色

2，根结点是黑色

3，不会出现两个连续的红节点

4，叶子结点的nil节点一定是黑色（nil节点是空对象节点）

5，任意节点到其叶子结点的路径上的黑色结点数目相同

LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。
?

TreeMap 底层是红黑树，实现的接口继承sortedmap接口，可以对key进行自然排序，也可以在构造方法传递Comparator实现map排序。

HashTable 与hashmap相似，底层是数组加链表，链表主要为了解决哈希冲突存在，扩容为2倍+1，默认容量11，是线程安全的，不允许空key空value

hashmap怎么实现扩容的？

①采用resize方法，把当前桶节点的hash值与就容量与，重新分配hash值，当超出数组阀值或者初始化的时候会调用进行扩容

②扩容后元素在原位置或者偏移量为两倍的位置

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;//oldTab指向hash桶数组
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {//如果oldCap不为空的话，就是hash桶数组不为空
        if (oldCap >= MAXIMUM_CAPACITY) {//如果大于最大容量了，就赋值为整数最大的阀值
            threshold = Integer.MAX_VALUE;
            return oldTab;//返回
        }//如果当前hash桶数组的长度在扩容后仍然小于最大容量 并且oldCap大于默认值16
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold 双倍扩容阀值threshold
    }
    // 旧的容量为0，但threshold大于零，代表有参构造有cap传入，threshold已经被初始化成最小2的n次幂
    // 直接将该值赋给新的容量
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // 无参构造创建的map，给出默认容量和threshold 16, 16*0.75
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 新的threshold = 新的cap * 0.75
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    // 计算出新的数组长度后赋给当前成员变量table
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//新建hash桶数组
    table = newTab;//将新数组的值复制给旧的hash桶数组
    // 如果原先的数组没有初始化，那么resize的初始化工作到此结束，否则进入扩容元素重排逻辑，使其均匀的分散
    if (oldTab != null) {
        // 遍历新数组的所有桶下标
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                // 旧数组的桶下标赋给临时变量e，并且解除旧数组中的引用，否则就数组无法被GC回收
                oldTab[j] = null;
                // 如果e.next==null，代表桶中就一个元素，不存在链表或者红黑树
                if (e.next == null)
                    // 用同样的hash映射算法把该元素加入新的数组
                    newTab[e.hash & (newCap - 1)] = e;
                // 如果e是TreeNode并且e.next!=null，那么处理树中元素的重排
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // e是链表的头并且e.next!=null，那么处理链表中元素重排
                else { // preserve order
                    // loHead,loTail 代表扩容后不用变换下标，见注1
                    Node<K,V> loHead = null, loTail = null;
                    // hiHead,hiTail 代表扩容后变换下标，见注1
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // 遍历链表
                    do {             
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                // 初始化head指向链表当前元素e，e不一定是链表的第一个元素，初始化后loHead
                                // 代表下标保持不变的链表的头元素
                                loHead = e;
                            else                                
                                // loTail.next指向当前e
                                loTail.next = e;
                            // loTail指向当前的元素e
                            // 初始化后，loTail和loHead指向相同的内存，所以当loTail.next指向下一个元素时，
                            // 底层数组中的元素的next引用也相应发生变化，造成lowHead.next.next.....
                            // 跟随loTail同步，使得lowHead可以链接到所有属于该链表的元素。
                            loTail = e;                           
                        }
                        else {
                            if (hiTail == null)
                                // 初始化head指向链表当前元素e, 初始化后hiHead代表下标更改的链表头元素
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 遍历结束, 将tail指向null，并把链表头放入新数组的相应下标，形成新的映射。
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}