Java集合框架

image

ZERO

    持续更新 请关注：https://zorkelvll.cn/blogs/zorkelvll/articles/2018/12/16/1544926812927

背景

    本文主要是记录在学习 Java集合框架过程中的一些知识点备忘！

20181218

1、List VS Set VS Map

• List:核心区别在于有序性，该接口存储一组不唯一（可以有多个元素引用相同的对象）、有序的对象
• Set:核心区别在于唯一性，该接口是不允许元素重复的集合，即不会有多个元素引用相同的对象
• Map:核心趋避在于键值对存储，搜索效率较高；Map会维护与Key有关联的值，两个Key可以引用相同的对象，但Key不能重复，典型的Key是String类型，也可以是任何对象

2、Arraylist VS LinkedList

Arraylist底层使用的是数组（=>存储、读取效率高，插入删除特定位置效率低【时间复杂度浸塑为O（n）】）；LinkedList底层使用的是双向循环链表数据结构（插入删除特定位置侠侣特别高【时间复杂度近似为O（1）】）

3、Arraylist VS Vector

Vector类所有方法均是同步的，多个线程可以安全地访问一个Vector对象，但是相比较而言的一个线程访问Vector时程序代码需要在同步操作室耗费大量的时间；而Arraylist不是同步的！

20181217

1、HashMap为什么是线程不安全的？

在多线程下，进行put操作可能会导致HashMap死循环问题，原因在于HashMap的扩容resize()方法；

这是由于扩容是新建一个数组，复制原数据到数组；又由于数组下标挂有链表，因此也需要复制链表，但是多线程操作可能导致出现环形链表，例如：

若2个线程同时扩容，比如线程1先将A复制到新的hash表中，然后接着复制B到链头,本来B.next = null到此也就结束了（跟线程2过程一样）；但是，由于线程2扩容的原因，将B.next = A,继续复制A，让A.next=B,由此出现B.next=A;A.next=B

（线程2：将0-A->B->NULL =》0-B->A->NULL，则线程1：0->B->A->B）

=》JDK1.8中已经解决了死循环问题(在resize方法中，声明两个引用地址，维护两个链表，依次在末端添加新元素，在多线程操作情况下，无非是第二个线程重复第一个线程一模一样的操作而已)，虽然多线程put操作不会导致死循环问题，但依然有其他的弊端如数据丢失等问题，因此多线程情况下还是应该使用ConcurrentHashMap

2、HashMap VS HashSet

HashSet底层是基于HashMap实现的，HashSet中的方法除了clone\writeObject\readObject方法外，其他方法都是直接调用HashMap中的方法的

• HashMap实现了Map接口，HashSet实现了Set接口
• HashMap存储键值对，HashSet仅存储对象
• HashMap调用put方法向map中添加元素，HashSet调用add方法向Set中添加元素
• HashMap使用键Key计算HashCode；HashSet使用成员对象来计算hashcode值
• HashMap相对于HashSet较快，因为它是使用唯一的键获取对象

3、ConcurrentHashMap VS Hashtable

二者的区别主要体现于线程安全的实现方式上不同

• 底层数据结构：JDK1.7中的ConcurrentHashMap底层采用分段的数组+链表实现，JDK1.8则采用的是跟HashMap1.8的结构一样，即数组+链表/红黑二叉树；Hashtable和JDK1.8之前的HashMap底层数据结构类似也是采用的数组+链表形式，数组是HashMap的主体，链表则主要是为了解决哈希冲突而存在的
• 实现线程安全的方式(重要)：（1）JDK1.7中，ConcurrentHashMap(分段锁)对整个桶数组进行分割分段（Segment），每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率（默认分配16个Segment，笔Hashtable效率提高16倍）；而在JDK1.8中则摒弃了Segment的概念，直接使用Node数组+链表+红黑树的数据结构来实现，并发控制使用synchronized和CAS来操作（JDK1.6以后对synchronized锁做了很多优化），整个看起来就像是优化过且线程安全的HashMap，尽管在DJK1.8中还能够看得到Segment的数据结构，但已经简化了属性只是为了兼容旧版本；（2）Hashtable(同一把锁)：使用synchronized来保证线程安全，效率非常低下；当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用put添加元素，则另一个线程不能使用put添加元素也不能使用get，竞争会越来越激烈效率越低

4、ConcurrentHashMap线程安全的具体实现方式/底层实现原理

• JDK1.7：将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问；

ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成；Segment实现了ReentrantLock,是一种可重入锁，扮演锁的角色；HashEntry用于存储键值对数据

一个ConcurrentHashMap中包含一个Segment数组，Segment的结构与HashMap类似，是一种数组和链表结构，一个Segment包含一个HashEntry数组，每个HashEntry是一个链表结构的元素，每个Segment守护着一个HashEntry数组里的元素，当对HashEntry数组的数据进行修改时，必须首先获得对应的Segment的锁

• JDK1.8:ConcurrentHashMap取消了Segment分段锁，采用CAS和synchronized来保证并发安全，数据结构跟HashMap1.8类似，数组+链表/红黑二叉树

synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率又提升N倍

5、集合框架底层数据结构总结

• Collection

List:

(1)Arraylist:Object数组
(2)Vector:Object数组
(3)LinkedList:双向链表（JDK1.6之前为循环链表，JDK1.7取消了循环）

Set:

(1)HashSet（无序，唯一）：基于HashMap实现，底层采用HashMap来保存元素
(2)LinkedHashSet:继承于HashSet，且其内部是通过LinkedHashMap实现的
(3)TreeSet(有序，唯一)：红黑树（自平衡的排序二叉树）

• Map

  (1)HashMap:JDK1.8之前是由数组+链表组成，数组是其主体，链表主要是为了解决哈希冲突而存在的（拉链法解决冲突）；JDK1.8之后在解决哈希冲突时，增加了红黑树数据结构即当链表长度大于阈值（默认8）时，则会将链表转化为红黑树以减少搜索时间
  (2)LinkedHashMap:继承于HashMap，底层仍然是基于拉链式散列结构即数组+链表/红黑树，在此基础之上增加了一条双向链表，使得该结构可以保持键值对的插入顺序，同时通过链表进行相应的操作，实现了访问顺序相关逻辑
  (3)Hashtable:数据+链表组成，数组是其主体，链表则主要是为了解决哈希冲突而存在的
  (4)TreeMap:红黑树（自平衡的排序二叉树）

20181216

1、ArrayList VS LinkedList

• 是否线程安全：二者均是不同步的，即不保证线程安全；
• 底层数据结构：ArrayList - Object数组，LinkedList - 双向链表数据结构（JDK1.6之前为循环链表，JDK1.7取消了循环，注意双向链表和双向循环链表的区别）
• 插入和删除是否受元素位置的影响：（1）数组，因此插入和删除元素的时间复杂度受元素位置的影响，近似为O(n);(2)链表，因此插入和删除元素的时间复杂度不受元素位置的影响，近似为O(1)
• 是否支持快速随机访问：LinkedList不支持高效的随机元素访问，而ArrayList支持，直接通过元素的序号快速获取元素对象
• 内存空间占用：ArrayList的空间浪费主要是list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）

=>

• RandomAccess接口：该接口中无任何定义，因此只是一个标识，即标识实现这个接口的类具有随机访问功能！
• binarySearch()方法：该方法会判断传参List是否是RandomAccess的实例，若是则调用indexedBinarySearch方法，否则调用iteratorBinarySearch方法

=>

• ArrayList实现了RandomAccess接口，LinkedList没有实现；
• 数组天然支持随机访问，时间复杂度O(1),因此称为快速随机访问；链表需要遍历到特定位置才能访问特定位置的元素，时间复杂度为O(n)，所以不支持快速随机访问
• ArrayList是实现了RandomAccess接口，是表明了其具有快速随机访问功能，该接口仅是标识，并不是说ArrayList实现了该接口才具有快速随机访问功能的

=>

• 实现了RandomAccess接口的List，优先使用普通for循环，其次是foreach

• 未实现RandomAccess接口的List，优先选择iterator遍历(foreach遍历底层也是通过iterator实现的)，大size的List数据不要使用普通for循环

• 双向链表：也即双链表，是链表的一种，它的每个数据节点均有两个指针，分别指向直接后继和直接前驱；因此，从双向链表中的任意一个节点开始，均可以很方便地访问它的前驱节点和后继节点，一般都是构造双向循环链表，JDK1.6之前的LinkedList底层使用的就是双向循环链表

2、ArrayList VS Vector

• Vector类的所有方法均是同步的，两个线程可以安全地访问同一个Vector对象，但是一个线程访问Vector需要在同步操作上耗费大量的时间
• ArrayList不是同步的，不需要保证线程安全时建议使用ArrayList

3、HashMap的底层实现

• JDK1.8之前：

底层是“数组+链表”数据结构，即链表散列；

HashMap通过key的hashCode经过扰动函数处理过后得到hash值，然后通过(n-1)&hash判断当前元素存放的位置（n即数组的长度），如果当前位置存在元素的话则判断该元素与要存入的h元素的ash值以及key是否相同，如果相同的话则直接覆盖，否则不相同则通过拉链法解决冲突

扰动函数：也就是HashMap的hash方法，该方法即扰动函数主要是为了防止一些实现比较差的hashCode方法，以减少碰撞

hash方法源码：

//jdk1.8方法相较于jdk1.7更加简化，但是原理不变
static final int hash(Object key) {
      int h;
      // key.hashCode()：返回散列值也就是hashcode
      // ^ ：按位异或
      // >>>:无符号右移，忽略符号位，空位都以0补齐
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

//jdk1.7，该方法性能会稍差一点点，因为毕竟扰动了4次
static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

拉链法：将链表和数组相结合，即创建一个链表数组，数组中每一格都是一个链表，若遇到hash冲突则将冲突的值加到链表中即可

• JDK1.8之后

在JDK1.8中，对于解决哈希冲突有了较大的变化，当链表长度大于阈值（默认8），则会将链表转化为红黑树，以减少搜索时间

TreeMap、TreeSet以及JDK1.8之后的HashMap底层均用到红黑树，红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构

• 《Java 8系列之重新认识HashMap》 ：https://zhuanlan.zhihu.com/p/21673805

4、HashMap VS HashTable

• 线程安全：HashMap非线程安全，HashTable线程安全；HashTable内部的方法基本都是经过synchronized修饰的（若需要保证线程安全的话，可以使用ConcurrentHashMap）
• 效率：由于线程安全的问题，HashTable的效率比HashMap低一点，且HashTable已经基本被淘汰，不要在代码中使用它
• 对Null key 和Null value的支持：HashMap中，null可以作为主键，这样的键只有一个，可以有一个或多个键所对应的值为null；但是在HashTable中put进的键值只要有一个null，则直接抛出NullPointerException
• 初始容量大小&每次扩充容量大小的不同：（1）创建时若未指定初始容量值，HashTable默认初始大小为11，每次扩充容量变为原来的2n+1;HashMap默认初始大小为16，每次扩充容量变为原来的2倍；（2）创建时若指定初始容量值，则HashTable会直接使用给定的大小，而HashMap会将其扩充为2的幂次方大小（HashMap中的tableSizeFor方法保证）
• 底层数据结构：JDK1.8以后的HashMap在解决哈希冲突时，当链表长度大于阈值（默认8），则会将链表转化为红黑树以减少搜索时间，而HashTable则没有这样的机制

5、HashMap的长度为什么是2的幂次方

为了能够让HashMap存取高效，尽量减少碰撞，也即要尽量把数据分配均匀！Hash值范围是-2147483648~2147483648，共约40亿映射空间，只要hash函数映射的比较均匀松散，一般很难出现碰撞，但是40亿长度的数组在内存中存放不下的，因此这个散列值是不能直接使用的

=>考虑先对数组的长度进行取模运算，计算的余数用来作为存放的位置也即数组下标，即数组下标的计算方法是“(n-1) & hash”，其中n为数组长度,这也就是为什么HashMap的长度是2的幂次方

=>为什么是2的幂次方？：：取模运算，首先就是采用%操作进行实现，=>"取余%操作中，在除数是2的幂次方时，等价于与其除数减一的与&操作，也即hash%length == hash&(length-1),,这个等价的前提就是length是2的n次方"

=>并且，在采用二进制位操作&，相对于%能够提高运算效率，这也是为什么HashMap的长度要是2的幂次方！

说明：本JavaGuide系列博客为来源于https://github.com/Snailclimb/JavaGuide
等学习网站或项目中的知识点，均为自己手打键盘系列且内容会根据继续学习情况而不断地调整和完善！