Java 集合源码

一、ConcurrentLinkedQueue介绍ConcurrentLinkedQueue是线程安全的队列，它适用于“高并发”的场景。它是一个基于链接节点的无界线程安全队列，按照FIFO（先进先出）原则对元素进行排序。队列元素中不可以放置null元素（内部实现的特殊节点除外）。二、ConcurrentLinkedQueue原理和数据结构说明：ConcurrentLinkedQueue继承于AbstractQueue。ConcurrentLinkedQueue内部是通过链表来实现的。它同时包含链表的头节点head和尾节点tail。ConcurrentLinkedQueue按照FIFO（先进先出

一、LinkedBlockingDeque介绍LinkedBlockingDeque是双向链表实现的双向并发阻塞队列。该阻塞队列同时支持FIFO和FILO两种操作方式，即可以从队列的头和尾同时操作(插入/删除)；并且，该阻塞队列是支持线程安全。此外，LinkedBlockingDeque还是可选容量的(防止过度膨胀)，即可以指定队列的容量。如果不指定，默认容量大小等于Integer.MAX_VALUE。二、LinkedBlockingDeque原理和数据结构说明：LinkedBlockingDeque继承于AbstractQueue，它本质上是一个支持FIFO和FILO的双向的队列。Linke

一、LinkedBlockingQueue介绍LinkedBlockingQueue是一个单向链表实现的阻塞队列。该队列按FIFO（先进先出）排序元素，新元素插入到队列的尾部，并且队列获取操作会获得位于队列头部的元素。链接队列的吞吐量通常要高于基于数组的队列，但是在大多数并发应用程序中，其可预知的性能要低。此外，LinkedBlockingQueue还是可选容量的(防止过度膨胀)，即可以指定队列的容量。如果不指定，默认容量大小等于Integer.MAX_VALUE。二、LinkedBlockingQueue原理和数据结构说明：LinkedBlockingQueue继承于AbstractQueu

一、ArrayBlockingQueue介绍ArrayBlockingQueue是数组实现的线程安全的有界的阻塞队列。线程安全:是指，ArrayBlockingQueue内部通过“互斥锁”保护竞争资源，实现了多线程对竞争资源的互斥访问。有界:是指ArrayBlockingQueue对应的数组是有界限的。阻塞队列，是指多线程访问竞争资源时，当竞争资源已被某线程获取时，其它要获取该资源的线程需要阻塞等待；而且，ArrayBlockingQueue是按FIFO（先进先出）原则对元素进行排序，元素都是从尾部插入到队列，从头部开始返回。二、ArrayBlockingQueue原理和数据结构ArrayBl

一、ConcurrentSkipListMap介绍ConcurrentSkipListMap是线程安全的有序的哈希表，适用于高并发的场景。ConcurrentSkipListMap和TreeMap，它们虽然都是有序的哈希表。但是，第一，它们的线程安全机制不同，TreeMap是非线程安全的，而ConcurrentSkipListMap是线程安全的。第二，ConcurrentSkipListMap是通过跳表实现的，而TreeMap是通过红黑树实现的。关于跳表(SkipList)，它是平衡树的一种替代的数据结构，但是和红黑树不相同的是，跳表对于树的平衡的实现是基于一种随机化的算法的，这样也就是说跳表

一、ConcurrentHashMap8简介我们在上一篇文章Java集合类（十六）JUC中的集合–ConcurrentHashMapjdk1.7里已经介绍了ConcurrentHashMap1.7中的源码。我们知道jdk1.7中使用分段锁来保证多线程之间数据的安全，那随着jdk的升级，会有怎样的优化呢，下面来讲一下ConcurrentHashMap在1.8中怎么实现的，做了那些优化来提高性能。jdk1.8的实现已经摒弃了Segment的概念，而是直接用Node数组+链表+红黑树的数据结构来实现，并发控制使用Synchronized和CAS来操作，整个看起来就像是优化过且线程安全的HashMap

一、ConcurrentHashMap介绍ConcurrentHashMap是线程安全的哈希表，它是通过“锁分段”来保证线程安全。ConcurrentHashMap将哈希表分成许多片段(Segment)，每一个片段除了保存哈希表之外，本质上也是一个“可重入的互斥锁”(ReentrantLock)。多线程对同一个片段的访问，是互斥的；但是，对于不同片段的访问，却是可以同步进行的。二、ConcurrentHashMap原理和数据结构如下图为concurrentHashMap的类图ConcurrentHashMap继承于AbstractMap抽象类。Segment是ConcurrentHashMap

一、CopyOnWriteArraySet介绍它是线程安全的无序的集合，可以将它理解成线程安全的HashSet。有意思的是，CopyOnWriteArraySet和HashSet虽然都继承于共同的父类AbstractSet；但是，HashSet是通过“散列表(HashMap)”实现的，而CopyOnWriteArraySet则是通过“动态数组(CopyOnWriteArrayList)”实现的，并不是散列表。和CopyOnWriteArrayList类似，CopyOnWriteArraySet具有以下特性：它最适合于具有以下特征的应用程序：Set大小通常保持很小，只读操作远多于可变操作，需要在

一、CopyOnWriteArrayList介绍它相当于线程安全的ArrayList。和ArrayList一样，它是个可变数组；但是和ArrayList不同的时，它具有以下特性：它最适合于具有以下特征的应用程序：List大小通常保持很小，只读操作远多于可变操作，需要在遍历期间防止线程间的冲突。它是线程安全的。因为通常需要复制整个基础数组，所以可变操作（add()、set()和remove()等等）的开销很大。迭代器支持hasNext(),next()等不可变操作，但不支持可变remove()等操作。使用迭代器进行遍历的速度很快，并且不会与其他线程发生冲突。在构造迭代器时，迭代器依赖于不变的数组

一、概述我们在Java集合类（一）概览里已经介绍了非线程安全的集合（Vector、List、Set、Map），下面几篇文章将介绍线程安全的集合。可能有人会问hashTable，Vector不是线程安全的类吗？下面看一段代码：packagedemo.com.test.collection;importjava.util.Vector;publicclassVectorTestimplementsRunnable{staticVector<String>v=newVector<String>();publicstaticvoidmain(String[]args){Vect

一、定义publicclassHashSet<E>extendsAbstractSet<E>implementsSet<E>,Cloneable,java.io.SerializableHashSet继承AbstractSet类，实现Set、Cloneable、Serializable接口。其中AbstractSet提供Set接口的骨干实现，从而最大限度地减少了实现此接口所需的工作。Set接口是一种不包括重复元素的Collection，它维持它自己的内部排序，所以随机访问没有任何意义。基本属性//基于HashMap实现，底层使用HashMap保存所有元素pr

一、Map总结二、区别三、面试面试时考官会问，两个使用相近类的异同，比如hashMap，hashTable。那我们总那几方面回答呢？1.继承的类2.底层使用的数据结构3.线程安全性四、Map优化首先我们这样假设，假设哈希映射的内部数组的大小只有1，所有的元素都将映射该位置（0），从而构成一条较长的链表。由于我们更新、访问都要对这条链表进行线性搜索，这样势必会降低效率。我们假设，如果存在一个非常大数组，每个位置链表处都只有一个元素，在进行访问时计算其index值就会获得该对象，这样做虽然会提高我们搜索的效率，但是它浪费了控件。诚然，虽然这两种方式都是极端的，但是它给我们提供了一种优化思路：使用一

TreeMap的实现是红黑树算法的实现，所以要了解TreeMap就必须对红黑树有一定的了解.1、红黑树的基本概念。2、红黑树增加节点、删除节点的实现过程。3、红黑树左旋转、右旋转的复杂过程。4、Java中TreeMap是如何通过put、deleteEntry两个来实现红黑树增加、删除节点的。一、红黑树简介红黑树又称红-黑二叉树，它首先是一颗二叉树，它具体二叉树所有的特性。同时红黑树更是一颗自平衡的排序二叉树。我们知道一颗基本的二叉树他们都需要满足一个基本性质–即树中的任何节点的值大于它的左子节点，且小于它的右子节点。按照这个基本性质使得树的检索效率大大提高。我们知道在生成二叉树的过程是非常容易

一、定义HashTable在Java中的定义如下：publicclassHashtable<K,V>extendsDictionary<K,V>implementsMap<K,V>,Cloneable,java.io.Serializable从中可以看出HashTable继承Dictionary类，实现Map接口。其中Dictionary类是任何可将键映射到相应值的类（如Hashtable）的抽象父类。每个键和每个值都是一个对象。在任何一个Dictionary对象中，每个键至多与一个值相关联。Map是”key-value键值对”接口。Hashtable采用”

一、HashMap存储结构从结构实现来讲，HashMap是数组+链表+红黑树实现的，如下如所示。这里需要讲明白两个问题：数据底层具体存储的是什么？这样的存储方式有什么优点呢？(1)从源码可知，HashMap类中有一个非常重要的内部类，就是Node[]table，即哈希桶数组，明显它是一个Node的数组。我们来看Node是何物。staticclassNode<K,V>implementsMap.Entry<K,V>{finalinthash;//用来定位数组索引位置finalKkey;Vvalue;Node<K,V>next;//链表的下一个nodeNode(

一、定义HashMap实现了Map接口，继承AbstractMap。其中Map接口定义了键映射到值的规则，而AbstractMap类提供Map接口的骨干实现，以最大限度地减少实现此接口所需的工作，其实AbstractMap类已经实现了Map，这里标注MapLZ觉得应该是更加清晰吧！publicclassHashMap<K,V>extendsAbstractMap<K,V>implementsMap<K,V>,Cloneable,Serializable二、构造函数HashMap提供了三个构造函数：HashMap()：构造一个具有默认初始容量(16)和默认加载

摘要HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK（JavaDevelopmetKit）版本的更新，JDK1.8对HashMap底层的实现进行了优化，例如引入红黑树的数据结构和扩容的优化等。本文结合JDK1.7和JDK1.8的区别，深入探讨HashMap的结构实现和功能原理。Map集合简介Java为数据结构中的映射定义了一个接口java.util.Map，此接口主要有四个常用的实现类，分别是HashMap、Hashtable、LinkedHashMap和TreeMap，类继承关系如下图所示：下面针对各个实现类的特点做一些说明：(1)HashMap：它根

一、List接口概述List接口，成为有序的Collection也就是序列。该接口可以对列表中的每一个元素的插入位置进行精确的控制，同时用户可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。下图是List接口的框架图：通过上面的框架图，可以对List的结构了然于心，其各个类、接口如下：Collection：Collection层次结构中的根接口。它表示一组对象，这些对象也称为collection的元素。对于Collection而言，它不提供任何直接的实现，所有的实现全部由它的子类负责。AbstractCollection：提供Collection接口的骨干实现，以最大限度地

一、概述LinkedList与ArrayList一样实现List接口，只是ArrayList是List接口的大小可变数组的实现，LinkedList是List接口链表的实现。基于链表实现的方式使得LinkedList在插入和删除时更优于ArrayList，而随机访问则比ArrayList逊色些。LinkedList实现所有可选的列表操作，并允许所有的元素包括null。除了实现List接口外，LinkedList类还为在列表的开头及结尾get、remove和insert元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。此类实现Deque接口，为add、poll提供先进先出

一、ArrayList概述ArrayList是实现List接口的动态数组，所谓动态就是它的大小是可变的。实现了所有可选列表操作，并允许包括null在内的所有元素。每个ArrayList实例都有一个容量，该容量是指用来存储列表元素的数组的大小。默认初始容量为10。随着ArrayList中元素的增加，它的容量也会不断的自动增长。在每次添加新的元素时，ArrayList都会检查是否需要进行扩容操作，扩容操作带来数据向新数组的重新拷贝，所以如果我们知道具体业务数据量，在构造ArrayList时可以给ArrayList指定一个初始容量，这样就会减少扩容时数据的拷贝问题。注意，ArrayList实现不是线

一、Vector简介Vector可以实现可增长的对象数组。与数组一样，它包含可以使用整数索引进行访问的组件。不过，Vector的大小是可以增加或者减小的，以便适应创建Vector后进行添加或者删除操作。Vector实现List接口，继承AbstractList类，所以我们可以将其看做队列，支持相关的添加、删除、修改、遍历等功能。Vector实现RandmoAccess接口，即提供了随机访问功能，提供提供快速访问功能。在Vector我们可以直接访问元素。Vector实现了Cloneable接口，支持clone()方法，可以被克隆。类定义publicclassVector<E>exte

一、非线程安全的集合java集合的架构。主体内容包括Collection集合和Map类；而Collection集合又可以划分为List(队列)和Set(集合)。上面的图展示了整个集合大家族的成员以及他们之间的关系。下面就上面的各个接口、基类做一些简单的介绍(主要介绍各个集合的特点。区别)，更加详细的介绍会在不久的将来一一讲解。ListList的实现类主要有:LinkedList,ArrayList,Vector,Stack。LinkedList:是双向链表实现的双端队列；它不是线程安全的，只适用于单线程。ArrayList：是数组实现的队列，它是一个动态数组；它也不是线程安全的，只适用于单线程