JAVA集合

一、集合的概念

① 集合是对象的容器。
② 集合不能直接存储基本数据类型，集合也不能直接存储java对象，集合当中存储的都是java对象的内存地址。（或者说集合中存储的是引用）
③ 集合类和集合接口都在java.util.* 包下。
④ 数组可存储基本类型和引用类型，集合只能存储引用类型。

二、List集合

List是Collection最常用的子接口，其最大的特点是允许保存重复元素的数据

2.1 ArrayList

ArrayList子类是在使用List接口最常用的一个子类，该类利用数组实现List集合操作
ArrayList集合里面保存的对象数组长度不够的时候会进行新的数组开辟，同时将原始的旧数组拷贝到新数组当中。

那新的大小是如何定义的呢？
JDK1.9之后：ArrayList默认的构造方法只会使用默认的空数组，使用的时候才会开辟新的数。
JDK1.9之前：ArrayList默认的构造会默认开辟大小为10的数组。
无参构造创建的ArrayList的初始空间为0，在添加第一个元素的时候空间会默认为10，之后扩容会为当前容量的1.5倍。
0->10->15->22->33->。

ArrayList list = new ArrayList();
会调用无参构造器，新建一个ArrayList。将elementData设置为DEFAULTCAPACITY_EMPTY_ELEMENTDATA

   /**
    * Constructs an empty list with an initial capacity of ten.
    */
   public ArrayList() {
       this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
   }
1
2
3
4
5
6

  /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
1
2
3
4
5
6

list.add(1);

/**
    * Appends the specified element to the end of this list.
    *
    * @param e element to be appended to this list
    * @return true (as specified by {@link Collection#add})
    */
   public boolean add(E e) {
       ensureCapacityInternal(size + 1);  // Increments modCount!!
       elementData[size++] = e;
       return true;
   }
1
2
3
4
5
6
7
8
9
10
11

通过ensureCapacityInternal方法来确保容量足够，此处的Math.max(DEFAULT_CAPACITY, minCapacity);就是确保第一次扩容空间为10。

for (int i = 0; i < list.size(); i ++) {}
for (Object o:list) {}
不同循环时的不同，有增删操作时，采用for array。

2.2、LinkedList

LinkedList子类是基于链表的形式实现的List接口标准。没有初始化大小,也没有扩容的机制,就是一直在前面或者后面新增就好。
面试题：请问ArrayList与LinkedList有什么区别？

ArrayList是数组实现的集合操作，而LinkedList是链表实现的集合操作。

链表与数组最大的区别在于：链表实现不需要频繁的进行新数组的空间开辟，
但是数组在根据索引获取数据时时间复杂度为O(1)，链表的时间复杂度为O(n)。
（List集合中的get()方法）根据索引获取数据时，ArrayList的时间复杂度为O(1),LinkedList的时间复杂度为O(n)。

2.3 Vector

Vector是一个原始的程序类，这个类在JDK1.0时就提供，而到了JDK1.2的时候，很多开发者已经习惯使用Vector，而且许多系统类也是基于Vector来实现的。无参构造默认空间为10，每次扩大一倍。

关于Vector的进一步说明

ArrayList与Vector除了推出时间不同以外，实际上他们内部的实现机制也有所不同，通过源代码的分析可以发现Vector类的操作方法采用的都是synchronize同步处理，而ArrayList并没有进行同步处理，是非线程安全的。所有Vector类中方法在多线程访问的时候属于线程安全的，但是性能不如ArrayList高，所以在考虑到线程并发访问的情况下才会去使用Vector子类。

三、set集合

Set集合的定义如下：
Set接口中定义的方法是Set是无序(无下标),不重复的，当使用（jdk1.9才有这个方法，1.8没有）of() 这个新方法的时候如何发现集合中存在重复的元素则会直接抛出异常，Set集合的常规使用形式一定是依靠子类进行实例化的，Set接口中有两个常用的子类：
HashSet（散列存放） TreeSet（有序存放）

HashSet

HashSet是Set接口较为常见的子类，所有的内容都采用散列（无序）的方式进行存储。该子类的最大特点就是不允许保存重复元素，为啥呢？
HashSet会识别重复的元素，HashSet可以实现去重操作。
所以可以把list转换为set进行去重操作。

TreeSet

TreeSet(内部实现二叉树) 特点:有序 不重复 主要作用:排序。

四、Map集合

在开发当中，Collection集合保存数据的目的是为了输出，Map集合保存数据的目的是为了进行key的查找。

HashMap

HashMap是Map接口中常用的子类，该类的主要特点是采用散列的方式存储。
HashMap的数据结构为 数组+(链表或红黑树)

数组的特点：查询效率高，插入，删除效率低。
链表的特点：查询效率低，插入删除效率高。

在HashMap底层使用数组加（链表或红黑树）的结构完美的解决了数组和链表的问题，使得查询和插入，删除的效率都很高。

HashMap中有两个重要的参数：初始容量大小和加载因子，初始容量大小是创建时给数组分配的容量大小，默认值为16，加载因子默认0.75f，用数组容量大小乘以加载因子得到一个值，一旦数组中存储的元素个数超过该值就会调用rehash方法将数组容量增加到原来的两倍，专业术语叫做扩容.
在做扩容的时候，原来的所有数据需要重新计算哈希码值重新分配到新的数组，所以扩容的操作非常消耗性能.
HashMap允许空键值,而HashTable不允许。所以我们在使用HashMap get到的键或者值为null的时候，不能判断该键值不存在！

java 1.7 和 java1.8 HashMap 的区别
jdk1.7中HashMap采用的是位桶+链表的方式，即我们常说的散列链表的方式，而jdk1.8中采用的是位桶+链表/红黑树的方式，也是非线程安全的。当某个位桶的链表的长度达到某个阀值（8）的时候，这个链表就将转换成红黑树。

在jdk1.8中，如果链表长度大于8且节点数组长度大于64的时候，就把链表下所有的节点转为红黑树。

树形化还有一个要求就是数组长度必须大于等于64，否则继续采用扩容策略

总的来说，HashMap默认采用数组+单链表方式存储元素，当元素出现哈希冲突时，会存储到该位置的单链表中。但是单链表不会一直增加元素，当元素个数超过8个时，会尝试将单链表转化为红黑树存储。但是在转化前，会再判断一次当前数组的长度，只有数组长度大于64才处理。否则，进行扩容操作。
我们可以这么来看，当链表长度大于或等于阈值（默认为 8）的时候，如果同时还满足容量大于或等于 MIN_TREEIFY_CAPACITY（默认为 64）的要求，就会把链表转换为红黑树。同样，后续如果由于删除或者其他原因调整了大小，当红黑树的节点小于或等于 6 个以后，又会恢复为链表形态。

每次遍历一个链表，平均查找的时间复杂度是 O(n)，n 是链表的长度。红黑树有和链表不一样的查找性能，由于红黑树有自平衡的特点，可以防止不平衡情况的发生，所以可以始终将查找的时间复杂度控制在 O(log(n))。最初链表还不是很长，所以可能 O(n) 和 O(log(n)) 的区别不大，但是如果链表越来越长，那么这种区别便会有所体现。所以为了提升查找性能，需要把链表转化为红黑树的形式。

put方法

static final int TREEIFY_THRESHOLD = 8;
 
public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
 }
  
  
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab;
    Node<K,V> p;
    int n, i;
    //如果当前map中无数据，执行resize方法。并且返回n
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
     //如果要插入的键值对要存放的这个位置刚好没有元素，那么把他封装成Node对象，放在这个位置上即可
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
    //否则的话，说明这上面有元素
        else {
            Node<K,V> e; K k;
        //如果这个元素的key与要插入的一样，那么就替换一下。
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
        //1.如果当前节点是TreeNode类型的数据，执行putTreeVal方法
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
        //还是遍历这条链子上的数据，跟jdk7没什么区别
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
            //2.完成了操作后多做了一件事情，判断，并且可能执行treeifyBin方法
                        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) //true || --
                    e.value = value;
           //3.
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
    //判断阈值，决定是否扩容
        if (++size > threshold)
            resize();
        //4.
        afterNodeInsertion(evict);
        return null;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

LinkedHashMap

Hash采用的是散列算法进行数据存储，这就造成了无序存放，但是要求严格下需要按照顺序存放，所以提供了链表的形式的Map集合。

LinkedHashMap子类最大的特点是可以基于链表形式实现偶对象的存储，这样就可以保证集合的存储顺序与数据增加的顺序相同

Hashtable

Hashtable是早期的字典实现类，可以方便的实现数据的查询
HashMap与Hashtable的区别：
HashMap中的方法都属于异步操作（非线程安全），HashMap允许保存的数据为空，Hashtable中的方法都属于同步操作（线程安全），Hashtable不允许保存null数据，否则会出现NullPointException异常。

TreeMap

Map集合的主要功能是依据key实现数据的查询需求，为了方便进行key排序操作提供了TreeMap集合