Java基础之集合

从这篇开始，我将把我所学的java体系的知识点总结并分享出来，并放在GitHub上，希望你能有所收获。

这是Java的集合体系，我们需要重点关注的大概就是其中的ArrayList、HashMap，这也是面试经常问到的内容，包括对应的替代及衍生。

文章目录：

List

List的特点是插入有序的，元素是可重复的 ArrayList和LinkedList的区别在于前者底层是数组，后者底层是链表，数组遍历快，队列增删快。但是ArrayList的增删底层调用的copyOf方法优化过，所以也不慢。而ArrayList尾插元素的时间复杂度只有O(1)。 特点：ArrayList是List接口的大小可变数组的实现；ArrayList允许null元素；ArrayList的容量可以自动增长；ArrayList不是同步的；ArrayList的iterator和listIterator方法返回的迭代器是fail-fast的 所以一般无脑使用ArrayList。LinkedList在刷题中用，当做一个先进先出的队列。

HashMap

底层结构

在jdk1. 7里是数组+链表的结构，而在jdk1.8里是一个数组+链表+红黑树的形式。 数组中的每个节点叫做node（1.7里叫做entry），每个node节点有4个属性，分别是hash值、key、value、next节点。node是hashmap的一个内部类，实现了Map.Entry接口，本质上就是一个键值对。 那因为存在哈希冲突，不同的key值可能计算出相同的哈希值，所以就要去解决这个问题，一般有四种方法：开放定址法（找下一块没被占用的存储地址）、再哈希（耗时）、链地址法（耗性能，但是确保一定能找到地址，适合哈希冲突多）、公共溢出区（把冲突的记录放溢出区里，先查基本表，不行就查溢出区，适合冲突少）。jdk1.7就用了链地址法，1.8则会在一定的条件下（冲突的链表长度大于8,并且数组长度大于64），将链表转化为红黑树。 因为红黑树的时间复杂度是O(logn)，冲突发生的次数越多，时间消耗越趋于稳定。 还有HashMap的默认构造函数，其实就是对threshold、loadFactor、modCount、size四个字段进行初始化，threshold就是叫阈值，是允许的最大的 键值对的个数，它的值为数组的容量length（默认16，即1<<4, 2的次幂保证length-1的所有二进制位的值全为1，这种情况下计算出的数组索引等同于hashCode后几位的值，这样hash算法的结果就会比较均匀的分布）乘以负载因子loadfacter（默认0.75）=12，超过了这个阈值就需要resize扩容，扩容后的容量是之前的2倍。0.75是对时间和空间的平衡，一般不修改。size就是实际存在的键值对的个数，modeCount是用来记录HashMap结构变化的次数的，主要用于迭代的快速失败。

如何通过key计算存储位置

static final int hash(Object key) {   //jdk1.8 & jdk1.7
     int h;
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

主要过程是3步，取HashCode值、高位运算、取模运算。 先将key进行hashCode计算得到哈希值。 高位就是通过将原来计算出来的哈希值进行无符号右移16位（>>>）再将结果与原来的哈希值进行一个异或运算（同0异1），返回了一个hash值的结果。 因为相同的key得到的hash值肯定是相同的，为了保证元素在数组中分布的尽量均匀，这样就不用遍历链表，然后就可以将这个返回的hash值对数组的长度length进行一个取模运算mod，但是mod操作比较消耗性能，HashMap就很巧妙的将hash值与length-1进行了一个按位与&运算，因为当length是2的n次方时，这个运算他就等价于mod运算，但是效率更高。

return h & (length-1); 

插入元素

也就是put方法，调用了putVal方法，里面维护了一个Node<k,v>[]数组。 1、首先会判断键值对数组是不是空null的，如果是空的就进行resize扩容。 2、然后根据key计算出hash值，得到插入的数组的索引index，然后判断这个位置是不是空的null，是的话就直接新建一个node节点添加； 3、如果不是空的那就判断这个位置上的首个元素的key是不是和我们的相等，相等的话就将value覆盖掉。 4、不一样的话就判断是不是treeNode红黑树，如果是红黑树那就执行插入操作putTreeVal()，如果不是红黑树那就是链表，先判断长度有没有大于8，大于8就转化为红黑树再插入，否则就遍历链表进行插入操作，如果遍历的时候发现key已经存在了那就将对应的value覆盖掉。 5、插入完后，判断键值对个数size有没有超过阈值threshold，超过了就进行resize扩容。

扩容机制

1.8中，数组有两种情况会发生扩容： 一是超过阈值，二是链表转为红黑树且数组元素小于64时 扩容分为两步，一步是创建一个新的entry数组，容量为之前的两倍，然后是一次rehash(因为length发生了变化，所以hash规则改变)，遍历原数组，把所有的entry重新Hash到新数组 扩容其实就是调用resize方法，当size大于阈值就会扩容，resize方法内先对旧数组oldCapacity的长度length进行判断，如果大于最大值2的30次方的话就将阈值改为2的31次方-1，也就是int的最大值，这样以后就不会扩容了。 没超过最大值那就扩容为原来的2倍（左移1位）。接着计算新的阈值。然后是一个for循环，将元素拷贝到新数组里。 resize的赋值方式在1.7中是头插，新的元素总会被放在链表的头部位置，使得链表顺序会倒置过来，而且旧数组中的一条entry链上的元素rehash后可能被放在新数组的不同位置上，这就可能导致环形链表的发生： a->b->c 变成c, b->a，因为a本来就有指向b的指针，就导致了环形链表，出现死循环Infinite Loop。在1.8中改成了尾插法，扩容前后链表元素顺序不变。 但是因为无锁，多线程环境下非线程安全。

重写方法

为什么使用HashMap需要重写hashcode和equals方法？

如果k1和k2的id相同，即代表这两把钥匙相同，可以用第二把钥匙打开用第一把钥匙锁的门。

假如有个自定义的类key，类里有个成员变量id，我们new两个key对象，传入的id都是1，分别是k1，k2；

当向HashMap中存入k1的时候，首先会调用Key这个类的hashcode方法，计算它的hash值，随后把k1放入hash值所指引的内存位置；如果在Key这个类中没有定义hashcode方法，就会调用Object类的hashcode方法，而Object类的hashcode方法返回的hash值是对象的地址。这时用k2去拿也会计算k2的hash值到相应的位置去拿，由于k1和k2的内存地址是不一样的，所以用k2拿不到k1的值

重写hashcode方法仅仅能够k1和k2计算得到的hash值相同，调用get方法的时候会到正确的位置去找，但当出现哈希冲突时，在同一个位置有可能用链表的形式存放冲突元素，这时候就需要用到equals方法去对比了，由于没有重写equals方法，它会调用Object类的equals方法，Object的equals方法判断的是两个对象的内存地址是不是一样，由于k1和k2都是new出来的，k1和k2的内存地址不相同，所以这时候用k2还是找不到k1的值

什么时候需要重写hashcode和equals方法？

在HashMap中存放自定义的键时，就需要重写自定义对象的hashcode和equals方法

怎么重写？

 @Override
 public int hashCode() {
     return id.hashCode();
 }

 @Override
 public boolean equals(Object obj) {
     if (obj == null || !(obj instanceof Key)) {
         return false;
     } else {
         return this.getId().equals(((Key) obj).getId());
     }
 }

线程安全

https://blog.csdn.net/swpu_ocean/article/details/88917958

hashmap线程不安全，追求线程安全的话通常使用concurrentHashMap，不用hashtable是因为前者并发度更好。

ConcurrentHashMap

HashTable线程安全，但是是直接在put和get方法上加了synchronized锁，效率比较低下，不允许键或值为null，hashmap可以。 不允许的原因是HashTable用了一个安全失败的机制fail-safe，他会使你获取的数据不一定是最新的，如果允许null值存在的话，就无法判断对应的key是不存在还是为空。所以会抛空指针异常，但是HashMap不会，因为hash方法对key是不是null进行了判断，是null的话直接return 0终止方法了。 另外hashtable的迭代器是安全失败的，hashmap是快速失败的，后者在遍历集合时会检测元素有没有发生变化，通过modcount变量，监测它的值，如果不符合预期说明元素被增加、删除或修改了就抛出异常，并终止遍历。 util包下的集合类都是快速失败的，不能再多线程下修改；util.concurrent下的容器都是安全失败的，可以用于并发修改。

底层结构

ConcurrentHashMap在1.7中是使用了数组+segment段+分段锁，segment通过继承ReentrantLock来进行加锁，每次锁住一个segment来降低粒度，通过局部加锁实现全局线程安全。segment是ConcurrentHashMap的一个内部类，主要组成是HashEntry数组，和HashMap不同的是他是被volatile关键字修饰的，保证了内存可见性、有序性。但是这样的设计就有个问题：每次hash确认位置都需要2次才能定位key应该在哪个槽，第一次将hash值与length-1进行位运算得到key在哪个段及索引index，第二次再通过hash值与table数组（ConcurrentHashMap底层存数据的数组）的length-1进行位运算才能确认在哪个桶。 1.8进行了优化，取消了分段锁的设计，没有了ReentrantLock，而是通过cas和synchronized关键字来优化，ConcurrentHashMap和HashMap的结构基本一致，数组+链表+红黑树 把HashEntry换成了node，同样的将value和next用volatile用修饰，保证了可见性。

添加元素

根据key计算出hashCode，然后判断是否需要进行初始化。如果已经初始化就找出当前key所在的桶，判断是不是空的，是的话就通过cas操作将新节点添加进此位置。 如果不是空的就判断节点的hash值是否是moved，也就是-1，是-1的话表示数组正在扩容，则需要当前的线程帮忙迁移数据，调用了一个helpTransfer方法；不是-1的话就利用synchronized锁写入数据，最后判断下节点个数，大于8的话转化成红黑树。 cas就是拿现在的值和原来的值进行比较，不同说明被修改了，一样说明没修改，可以去操作，但是有ABA问题。这里的synchronized获取锁的方式，不是上来就是重量级锁，而是先试用偏向锁，如果失败就使用cas，如果再失败就会短暂自旋，防止线程被挂起，然后升级为重量级锁

查询元素get

根据计算的hashCode直接寻址，如果在table上就直接返回值，如果是红黑树的结构的话那就按照树的方式获取值，不是红黑树的话就按照链表的方式遍历取值。 时间复杂度的话，加入没有发生hash碰撞，每个链表都只有1个节点，时间复杂度为O（1），发生了碰撞的话就需要遍历查找，n个元素的情况下链表为O（n），红黑树是logn。

ArrayList、LinkedList、Vector

ArrayList底层是Object数组，查找效率比较快，增删效率低，线程不安全。如果我们装载的是基本类型的数据的话我们只能装载他们的包装类。如果涉及频繁的增删就用linkedlist，需要线程安全就用Vector。 构造方法不传参数时就是默认容量10，注意，创建的时候传容量是制定了

ArrayList扩容

如果容量满了再新增元素的话，就会新建一个数量为之前1.5倍的数组，然后将原来数组的数据复制过去，再把指向原数的地址换到新数组

为什么默认是10

据说是因为sun的程序员对一系列广泛使用的程序代码进行了调研，结果就是10这个长度的数组是最常用的最有效率的。也有说就是随便起的一个数字，8个12个都没什么区别，只是因为10这个数组比较的圆满而已。 注意，创建的时候不要指定初始容量，指定的话只是数组的长度length，而不是数组大小length，此时如果在指定位置插入元素会报越界异常

为什么ArrayList增删慢?

新增元素的原理：比如说在index为5的位置新增一个元素，先校验一下长度够不够，不够就扩容，然后会复制一个数组，然后将5以及5之后的元素从新数组的6的位置放上去，给5的位置腾出空间。这也是他慢的原因，要是元素几千几万的话新增一个元素需要复制后面这么多元素，效率就很差。

添加元素

直接添加会将元素从集合的0开始添加 指定位置添加则要求在此位置之前的元素是存在的，否则将会报错。

删除元素

和新增差不多，从6号为开始复制放到原来的5号位置上开始。也是复制大量的元素。

ArrayList线程安全

线程不安全，Vector是线程安全的，但是只是粗暴的给所有的方法加上了synchronized锁。 有两种线程安全的替代，一种是Collections.synchronizedList(new ArrayList)。它能把所有 List 接口的实现类转换成线程安全的List，比 Vector 有更好的扩展性和兼容性，很可惜，它所有方法都是带同步对象锁的，和 Vector 一样，它不是性能最优的，在读多写少的情况，SynchronizedList这种集合性能非常差。和vector不同的是，他的内部迭代器方法没有加锁，如果要用的话需要手动加个synchronized同步代码块，而vector不用。 另一种是CopyOnWriteArrayList，即复制再写入，就是在添加元素的时候，先把原 List 列表复制一份，再添加新的元素。添加元素时，先加锁，再进行复制替换操作，最后再释放锁。获取元素并没有加锁。这样做的好处是，在高并发情况下，读取元素时就不用加锁，写数据时才加锁，大大提升了读取性能。 CopyOnWriteArraySet：CopyOnWriteArraySet逻辑就更简单了，就是使用 CopyOnWriteArrayList 的 addIfAbsent 方法来去重的，添加元素的时候判断对象是否已经存在，不存在才添加进集合。 这两种并发集合，虽然牛逼，但只适合于读多写少的情况，如果写多读少，使用这个就没意义了，因为每次写操作都要进行集合内存复制，性能开销很大，如果集合较大，很容易造成内存溢出。

遍历

论遍历ArrayList要比LinkedList快得多，ArrayList遍历最大的优势在于内存的连续性，CPU的内部缓存结构会缓存连续的内存片段，可以大幅降低读取内存的性能开销。