Java中的集合：数组、Collection、Map

一、 数组

1. 数组的特点

通常不把数组归为集合的一种，暂且不管数组是否属于集合的争论。

数组是一种数据结构，它存储的所有的元素类型必须是一样的。数组一旦创建后大小就不可以再改变了，但是各个元素值可以改变。

数组和List、Set、Map集合有什么不一样的地方呢？一是数组效率更高，数组Java中存储和随机存取效率最高的；二是数组可以存储基本类型的数据，这是其他集合无法直接做到的。
数组强调的是性能而不是灵活性。但是绝大部分情况下集合并没有明显的性能问题，牺牲微不足道的性能还是牺牲经过底层优化的List、Set的灵活性就看程序员的选择了。《Java编程思想》上建议“优先选择集合而不是数组”，甚至说Java的设计者如果重新设计Java，可能会抛弃数组。

2. 数组在内存是怎样存储的

声明一个数组是在内存中申请一块连续的空间，并且大小固定，这虽然不能扩展，但是存储和随机访问非常的快。

在Java中，数组本身就是引用类型，数组对象是存储在堆上的，在堆上占用一块连续的空间。如果数组声明在方法里那么就在栈的栈帧上存储一个指向堆上数组对象的地址；如果数组是个成员变量声明在类中，就是在方法区存储一个地址指向数组对象。

如果数组定义的类型是基本类型，那么数组元素值就是元素实际值；如果数组定义的类型是引用类型，那么元素值就是指向对象在堆上的地址。

3. 多维数组

一般来讲，各个语言中的的多维数组都可以看作是一维数组嵌套数组，也就是数组元素的类型还是数组。

比如二维数组:
int[][] a={{1,2,3},{4,5,6}}；
可以看作是一个一维数组，有两个元素，元素类型为int[]型的一维数组，里面的一维数组长度为3。

在Java中有个特殊的地方就是，数组可以不规则，也就是说最外层的一维数组中的各个元素的长度可以不同。比如：

public static void main(String[] args) {
        int[][] aa = {{1, 2}, {3, 4, 5, 6}};
        for (int[] row : aa) {
            for (int e : row) {
                System.out.print(e);
                System.out.print("\t");
            }
            System.out.print("\n");
        }
}        

这个例子中，最外层的一维数组有两个数组元素，第一个数组元素的长度是2，第二个数组元素的长度为4。

4. Arrays工具

java.util.Arrays类是用于数组的工具类，主要的方法有：

方法	描述
asList()	将数组转换为List集合
equals	对比两个数组是否相等
sort()	对数组进行排序
copyOf()	拷贝数组的值，并不是只拷贝数组的引用

二、Collection

1、Collection类图

Java的基本接口就是Collection，Collection接口下有两种最常使用的集合类型：List和Set。List是有序列表，可以重复；Set是无序列表，不可以重复。

2、ArrayList

顾名思义，ArrayList是用数组实现的List集合，LinkedList是用链表实现的List集合。

数组这种数据结构的特点是长度固定，可以通过下标随机读写指定位置的元素，下标不能超过元素的长度，否则会发生数组越界的异常。

数组在内存中是占用了连续的一块空间，变量的指针指向了这个连续空间的头部，可以通过偏移量随机访问数组的任何一个元素，所以不管数组多长，访问任何一个元素所用时间都是固定的，时间复杂度为O(1)。

ArrayList是对数组的封装，但是数组要要求指定长度，ArrayList之所以可以一直向里面添加元素是因为使用了动态再分配数组实现的。具体来说就是ArrayList有一个初始化的长度(Java8里是10)，当add元素时候判断是否超出了数组的长度，如果超出了长度，那么就定义另外一个数组，新数据长度是原来的1.5倍，然后将数据拷贝到新的数组中去，最后将要add的元素追加到新数据后面；当remove指定index的元素时候，是将index后面的所有元素复制到index位置，也就是后面的元素整体向前移一个位置。

ArrayList的构造函数还有一个重载，是初始化的时候就指定ArrayList的长度。比如事先知道ArrayList里元素有100个，就可以使用这个重载实例化，可以避免多次扩容造成的性能下降问题。

List<String> list2=new ArrayList<>(100);

因为ArrayList是用数组实现的，所以随机访问比较快，添加元素当要扩容时比较慢、删除元素比较慢。

关于ArrayList的初始化、add方法过程可以参考这个文章：ArrayList初始化

3、LinkedList

链表不会预先分配一块连续的内存空间，而是在添加一个元素的时候在内存中随机找一个空间，那么怎么能找到链表中每一个元素在哪个位置呢，这就要求链表中每个元素除了保存数据本身以外还有下一个元素的地址，这样所有元素就相互链接起来形成了一个链。

Java中的LinkedList是一个双向链表，每个元素都保存着下个元素的地址和上个元素的地址。

查找某一个元素时，需要从头开始一个接一个地查找，直到找到位置，并不能随机访问，所以时间复杂度为O(n)，n为链的长度。

在链中间add元素时，就申请一个随机内存地址，并将前面元素的next和后面元素的prev链接到新元素，新元素的prev链接到前面的元素，新元素的next链接到后面的元素。所以这个add元素的操作是低成本的。

从链中remove元素时，需要拆链，将指定元素删除并将前后元素再关联起来，这个操作也是轻量级的。

所以LinkedList添加和删除元素比较快，随机访问比较慢。

4、Vector

Vector也是基于数据实现的List接口，很ArrayList很像，区别在于Vector支持线程同步，某一时刻只能有一个线程写Vector，避免了多线程写入数据不一致的情况，但是线程同步需要花费时间，所以比ArrayList要慢。

另外，看Vector的源码可以看到，Vector的扩容大小和ArrayList不一样，ArrayList是每次扩容到原来的1.5倍，Vector是扩容到原来的2倍，Vector也可以指定每次扩容的大小。

5、HashSet

Set的最重要的特点就是不重复。HashSet是使用HashMap实现的不重复，所以HashSet的顺序也是跟插入数据不一致的。

三、 Map

HashMap是经常使用的一个类型，它有一些特点：
(1) 键值允许为null。
(2) 是非同步、线程不安全的类
(3) 不能保证按照插入顺序排序，也不能保证不同的时间，顺序不变。
(4) 按照key读写速度比较快。

1、HashMap类图

(1) HashMap：HashMap是根据key的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但是遍历顺序但是不确定的。HashMap最多只允许一条记录的键为null，HashMap也是非线程安全的，如果在多线程场景下使用，可以用Collections的synchronizedMap方法保证线程安全。

(2) LinkedHashMap：LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在遍历时先插入的值肯定是先被读取到的。

(3) TreeMap：TreeMap是根据键的顺序排好序的，默认是根据键升序排序，也可以指定降序排序。因为要根据键进行排序，所以键必须要实现Comparable接口或者在构造TreeMap时候传入自定义的Comparator。

2、HashMap 的数据结构

HashMap实际存储时，是哈希桶数组和链表的结合体，整体上来说是一个数组，每个数据元素又是一个链表，当链表长度大于8时，这个链表就变为红黑树形式。

存储结构如上图所示，HashMap初始化的时候就会创建一个哈希桶数组，哈希桶数组的长度是capacity（容量）定义的大小，数组的每一项是一个Entry，Entry 是一个键值对，它还有一个指向下一个元素的引用，就构成了链表，如果链表长度大于8时，Java8开始，为了提高效率，链表转换为红黑树形式。（红黑树参考）

当向HashMap中插入数据时，先根据数据key的hashCode计算index确定放入哪个哈希桶数组中，如果多个key的hashCode发生碰撞，就以链表的形式放入数组的后面，当链表大于8时，转换为红黑树。

哈希桶数组的容量capacity默认是16，当哈希桶数组中数据个数已经占用的比例已经达到负载因子时候(默认是0.75)，哈希桶数组的容量就会变为原来的2倍。负载因子是对空间和时间的一个权衡。

3、put操作

put函数大致的思路为：

• 对key的hashCode()做hash，然后再计算index;
• 如果没碰撞直接放到bucket里；
• 如果碰撞了，以链表的形式存在buckets后；
• 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树；
• 如果节点已经存在就替换old value(保证key的唯一性)
• 如果bucket满了(超过load factor*current capacity)，就要resize。

4、get操作

• 根据Key的hashCode值，在bucket里找到第一个节点，直接命中；
• 如果有冲突，则通过key.equals(k)去查找对应的entry。
  若为树，则在树中通过key.equals(k)查找，时间复杂度为O(logn)；
  若为链表，则在链表中通过key.equals(k)查找，时间复杂度为O(n)。

put和get归纳起来就是：

简单地说，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据 hash 算法来决定其在数组中的存储位置，在根据 equals 方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry 时，也会根据 hash 算法找到其在数组中的存储位置，再根据 equals 方法从该位置上的链表中取出该Entry。

5、扩容机制

当 HashMap 中的元素越来越多的时候，hash 冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对 HashMap 的数组进行扩容。当 HashMap 中的元素个数超过数组大小乘以负载因子时，就会进行数组扩容，负载因子的默认值为 0.75，这是一个折中的取值。也就是说，默认情况下，哈希桶数组大小为 16，那么当 HashMap 中元素个数超过 16乘以0.75=12 的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，扩容时，要将原来的数据复制到一个新创建的大数组中，然后重新计算每个元素在新数组中的位置。而这是一个非常消耗性能的操作，所以如果我们已经预知 HashMap 中元素的个数，那么预设元素的个数能够有效的提高 HashMap 的性能。

6、线程安全性

在多线程使用场景中，应该尽量避免使用线程不安全的HashMap，而使用线程安全的ConcurrentHashMap。