Java基础复习-容器相关

集合概述

java中的容器,都是实现了Map接口,或者是实现了Collection接口(Collection接口继承自Iterable)。下面这张图很形象说明了各种容器之间的关系:

image-20200719210752757

那么可以聊一下这些橙色的接口了:

  • List:有顺序,且可以是重复的。
  • Queue:一端负责进,一端负责出。
  • Dequeue:两端都可以进,两端都可以出。
  • Set:无序且不可重复。
  • SortedSet:其中的元素都是有顺序的。
  • Map:使用键值对来保存数据的。
  • SortedMap:可以对key进行排序。

List

ArrayList和Vector底层是一个Object数组,其中ArrayList没有使用synchronized修饰,线程不安全,而Vector则是线程安全的。

LinkedList底层是一个双向链表。

Set

HashSet底层用的是hashmap来保存的,TreeSet底层是红黑树,而LinkedHashSet则是HashSet的子类(图中这里有点问题)。

Map

HashMap是通过数组+链表/红黑树实现的,而HashTable则只是数组+链表。TreeMap底层是红黑树。

Iterable

这个接口只有一个方法,能够返回对应的迭代器。JDK1.8之后为其新增了foreach的默认实现,这样我们就可以很方便的遍历这些容器了。

强烈建议使用迭代器来访问,因为在访问过程中一旦当前遍历的元素被修改了就会抛出异常,保证安全性。

线程安全问题

如果要使得线程安全,那么可以使用对应的数据结构(这里不建议自己使用synchronized方法…)

  • ConcurrentHashMap:HashMap的线程安全版
  • CopyOnWriteArrayList:ArrayList的线程安全版
  • ConcurrentLinkedQueue:LinkedList的线程安全版
  • BlockingQueue:数据共享(生产者消费者问题的解决办法)
  • ConcurrentSkipListMap:跳表。

小结

在实际选用的过程中,首先想好自己要保存的数据类型,如果是key-value那就map,否则普通的collection就可以了。

接下来根据自己的需要:是否多线程共享?插入多删除多呢,还是查找比较多呢?需不需要排序呢?

List

List底下主要有三大将:ArrayList、Vector和LinkedList。区别很明显,然后相对应的性能只需要根据其底层结构进行分析即可。

由于ArrayList是数组实现的,所以支持RandomAccess,这样在对其进行二分查找的时候会很有优势。

Set

这个接口的实现类其实日常中用的是比较少的。

Set的无序性和不可重复性

不可重复的意思就是在添加元素的时候,会经过equals判断,如果是true则不能进入Set中。

无序性的意思是不能保证顺序,不是随机的意思。

三个Set实现的区别

HashSet 是 Set 接口的主要实现类 ,HashSet 的底层是 HashMap,线程不安全,由于HashMap的key可以是null,所以HashSet允许null。

LinkedHashSet 是 HashSet 的子类,能够按照添加的顺序遍历。

TreeSet 底层使用红黑树,能够按照添加元素的顺序进行遍历,排序的方式有自然排序和指定的排序。

Map

HashMap和HashTable的区别

HashMap并不是线程安全的,而HashTable的方法都经过了同步修饰,所以是线程安全的。

HashMap可以转变成红黑树,而HashTable则始终是数组+链表的组合。

HashMap可以有null作为key(但是只能有一个)和value,而HashTable均不允许。

HashMap的长度必然是2的幂次,而HashTable则是按照你指定的长度,每次扩容是乘以2加1。

HashMap和TreeMap的区别

TreeMap底层是红黑树,并且可以排序。

HashMap的底层实现

首先,计算出key的hashCode,然后在经过一次hashmap自己的一个函数计算出一个值(相当于做了两遍hash),然后利用(数组长度-1)& hash(注意这里不是取模运算哦)就可以计算出数组的位置了。如果数组位置是空的,那么直接放进去;否则需要去比对有没有重复的,如果有就覆盖掉,没有就加进去。

为什么hashmap的长度必须是2的整数次幂呢?这是因为hash%length==hash&(length-1)只有在length是2的整数次幂的时候才成立,显然取模运算的速度是远远比不上&运算的。

那么hashmap之前的版本中(头插法)是怎么在多线程下出现问题的呢?在进行rehash数据迁移的时候,头插法可能会导致循环的出现,而一旦在链表中出现了循环,就再也出不去了,所以CPU飙升到100%。

更为具体的:当一个线程完成了扩容,这样它的链表会是倒序的;然后又一个线程也进行扩容,此时会将原来的倒序变成正序,这样一个环就形成了。如果此时你再去get一个不存在的元素,这样就永远在这个环里面走不出来了。

如何遍历hashmap?

大体上可以有四类:

  • Iterator
  • foreach
  • stream
  • lambda

具体的可以有七种:

  • map.entrySet().iterator()
  • map.keySet().iterator()
  • for (Map.Entry<Integer, String> entry : map.entrySet())
  • for (Integer key : map.keySet())
  • map.forEach((key, value) -> { do something });
  • map.entrySet().stream().forEach((entry) -> { do something });
  • map.entrySet().parallelStream().forEach((entry) -> { do something });

结论:最后一种方法性能最高,其余都差不多。至于安全性,请使用iterator来保证删除的安全性。

ConcurrentHashMap和HashTable区别

它们俩都是线程安全的map类型。

在JDK1.7之前,ConcurrentHashMap用的是分段锁+链表,在1.8之后是数组+链表/红黑树。HashTable则一直都是数组+链表。

之前的ConcurrentHashMap由于用的是分段锁,所以只要访问数据不在一个段中,就可以有不错的并发性能,而现在则是完全没有了分段的概念,用的是 CAS(如果数组中元素是null) 和 synchronized(如果数组中已经有元素了,那么就需要链表/红黑树操作) ,只锁定链表中的第一个节点或者是红黑树的根节点。

其它

fail-fast

如果一个集合类,它不是fail-safe的,那么就可能会发生fail-fast,即抛出ConcurrentModificationException 异常。可能在多线程的情况下会出现,也可能在单线程但是在删除的时候出现。

具体就是集合类里面有一个属性是modCount,代表目前对这个集合类的修改次数。在遍历的时候,每次找到下一个同时会去检查这个值是不是等于expectedModCount,如果不是就直接抛出异常。而我们如果使用的是迭代器,那么同时也会修改expectedModCount,所以不会出现异常。

fail-safe

如果采用了这个机制,那么在遍历的时候,其实是首先复制一份,然后到复制品上面进行遍历,而操作的还是原来的集合,故不可能发生fail-fast。