集合学习

集合学习

集合是一定的方式组织和存储数据,在项目中也有很多应用,提高代码可用性。

ArrayList

ArrayList是最常见以及每个Java开发者最熟悉的集合类了,顾名思义,ArrayList就是一个以数组形式实现的集合

ArrayList允许为空,可以重复,并且有序,非线程安全。

ArrayList的底层是基于动态数组来实现的,因而其可以进行扩容。

ArrayList优点在于底层以动态数组实现,因而在寻找特定元素、位置速度快;ArrayList在顺序添加一个元素的时候也很快。缺点在于插入元素、删除元素的时候涉及到元素复制,如果数据量大,那么耗费较多性能。

ArrayList所有操作都不是同步的,所以线程不安全,而Vector则是其线程安全版本。

PS:elementData是用transient修饰的,因为Arraylist是可以被序列化,而elementData不希望被序列化的原因在于其空间有可能没有被全部使用完。

LinkedList

LinkedList是基于链表实现的,它还是个双向链表,因而它在插入与删除操作上优于ArrayList。

LinkedList允许为空,允许重复数据,有序,非线程安全。

LinkedList在查询元素的时候,因为是双向链表,所以其操作时当index小于数组大小的一半的时候(size >> 1表示size / 2,使用移位运算提升代码运行效率),向后查找;否则,向前查找;删除元素的时候指向下一个元素,同时设置原元素为null,让gc回收;插入元素是创建对象,然后设置其指向。

对于LinkedList以及ArrayList的迭代,如果用for循环来进行迭代LinkedList会极慢,而使用foreach能够大大加快其速度。

CopyOnWriteArrayList

 

CopyOnWrite容器即写时复制的容器。通俗的理解是当我们往一个容器添加元素的时候,不直接往当前容器添加,而是先将当前容器进行Copy,复制出一个新的容器,然后新的容器里添加元素,添加完元素之后,再将原容器的引用指向新的容器。这样做的好处是我们可以对CopyOnWrite容器进行并发的读,而不需要加锁,因为当前容器不会添加任何元素。所以CopyOnWrite容器也是一种读写分离的思想,读和写不同的容器。

CopyOnWriteArrayList是为了并发而存在的list,允许为空,允许重复数据, 有序,线程安全。

CopyOnWriteArrayList的增加、删除、查询、插入操作都是类似的操作。其思想就是读写分离、最终一致。按我的理解是,它先对原数组进行加锁,然后创建新的数组,进行操作,然后将地址指向新的数组,解锁。那么会产生一个问题,如果元素很多,那么操作的复杂度就会很高,所以这个适用于读操作远远高于写操作的场景。

随着元素的增加,CopyOnWriteArrayList的修改代价将越来越昂贵,因此,CopyOnWriteArrayList适用于读操作远多于修改操作的并发场景中

Vector

vector不同于ArrayList,它是线程同步,但因此其速度也较慢,需要的系统的开销大。而且它在扩展的时候不像ArrayList在内存不够时默认是扩展50% + 1个,Vector是默认扩展1倍。

Vector允许为空,允许重复,有序,线程安全。

它是古老的集合,是stack的父类,在jdk1.0就有了,而且同步类或方法都有synchronized来修饰,因此其在系统开销方面比较大。

Stack

Stack是栈,遵循后进先出的规律,它除了 push(),剩下的方法都是同步的。其操作都是在栈的入口所作的,因为继承于Vector,实现list,所以它也可以使用list的方法,比如insertElementAt()get等方法。

Stack允许为空,可以重复,线程安全。

PS:List有四个常见的继承类,ArrayList,LinkedList,Vector,Stack。Vector和stack是线程安全的。


HashMap

HashMap实现了map接口,是一种键值对集合,它的底层是依赖数组来存储Key值,因为其Node只有key、hash、value、next,所以它是一个单向链表。

HashMap允许为空,key重复会覆盖,value无所谓,无序,非线程安全。

HashCode和底层实现相关,不同的虚拟机可能有不同的HashCode算法。所以整个table是transient,不能被序列化的,这是为了跨平台设计的,但是java也提供了自己编写的序列化TABLE的方法帮助其序列化。

hashtable是线程安全的,而且不允许为空,两者的rehash方法也不相同。

AtomicInteger,一个提供原子操作的Integer的类。在Java语言中,++i和i++操作并不是线程安全的,在使用的时候,不可避免的会用到synchronized关键字。而AtomicInteger则通过一种线程安全的加减操作接口。

PS:1 可以使用jps+jstack查看堆栈信息来定位问题

2 因为多线程环境下,使用Hashmap进行put操作会引起死循环,导致CPU利用率接近100%,所以在并发情况下不能使用HashMap。

3.HashMap在jdk1.8之后增加了红黑树优化元素百分百均匀分布。

LinkedHashMap

LinkedHashMap是一种链表结构的map,所以它是有序得。它继承于HashMap,两者的区别在于其数据结构不同,后者为数组存储key,前者则可以说是散列表+循环双向链表。

LinkedHashMap允许键值为空,key重复会覆盖,value无所谓,有序,非线程安全。

LinkedHashMap的方法与HashMap相似,重写了其方法,使用了自己的数据结构来完成操作。它是有序得,而且它在使用get()、put()方法之后会把数据放到最后,那么就可以用这种特性来做LRU算法(最近最少用算法)。

HashTable

HashTable是一种线程安全的Map,因为其整体使用synchronization来进行加锁,当然在并发高的情况下,会因为抢占资源而表现不佳。Hashtable的速度也会慢于HashMap。

Hashtable补允许键值为空,键值可重复,无序,线程安全。

作为一个老集合,它在线程同步可以用ConcurrentHashMap来代表,在非并发情况下可以使用HashMap来代替。嗯,出现最多的就是题目中拿来跟这两个进行比较。

ConcurrentHashMap

ConcurrentHashMap是一种为实现高并发而设计的集合,它不同于hashtable将整个表锁定的,而是采用了分段锁的方式来形成线程安全。主要是使用final和voliate关键字来实现的。这个在并发情况下使用优势很大,同时因为其在并发的良好表现经常出现在面试当中。

ConcurrentHashMap不允许为空,可重复,无序,线程安全。

ConcurrentHashMap主要操作过程在于其有个Segment锁可以帮助实现线程安全,很多操作都需要先算出hash值确定Segment,然后再计算hash值来确定元素。相当于将一个MAP分割成很多hashtable,然后每段独立加锁。

TreeMap

TreeMap的实现是基于红黑树来完成的,因此它在统计性能时间复杂度上是优于其他map的,它的时间复杂度为log(n),而其他的则是o(n)。因而它常常用于统计方面。

TreeMap的Key不允许为空,Value允许为空,允许重复,按照Key的自然顺序排序或者Comparator接口指定的排序算法进行排序,非线程安全。

TreeMap实现了NavigableMap接口,它支持一系列的导航方法,TreeMap实现了Cloneable接口,它可以被克隆

TreeMap主要是用于分类以及统计使用的。


HashSet、LinkedHashSet、TreeSet

Set不允许有重复元素,但允许为空。HashSet依靠HashMap,需要有hashcode来完成写入,而LinkedHashSet则因为有链表做支撑,所以是有序得,而TreeSet则依靠TreeMap来实现的,具有TreeMap的一些特点。

HashSet不允许重复,允许为空,无序,线程不安全;

LinkedHashSet不允许重复,允许为空,有序,线程不安全;

TreeSet不允许重复,允许为空,有序,线程不安全;

ps:Collections.synchronizedSet可以使其为线程安全。

  • 既然不能成为屠龙的勇士,那么就好好成为一名优秀的管家,为公主建设一个温馨美好的家。
    Since it can not become a dragon warrior, then it is a good housekeeper, for the princess to build a warm and beautiful home.

  • 【推广】 免费学中医,健康全家人
    原文地址:https://www.cnblogs.com/ITflying/p/7261637.html