java集合框架源码解析,java集合框架是什么?说出一些集合框架的优点

　　这篇文章给大家带来了一些关于java的知识，主要介绍了集合框架的相关问题。Java collection framework提供了一套性能卓越、易于使用的接口和类。它们位于java.util包中，希望对你有所帮助。

　　如何解决写爬虫IP受阻的问题？立即使用。

一、简介

1、集合框架介绍

　　 Java collection framework提供了一组性能卓越、易于使用的接口和类。它们位于java.util包中。容器主要包括收藏和地图。Collection存储对象的集合，而Map存储键值对(两个对象)的映射表。

2、相关容器介绍

2.1 Set相关

　　TreeSet

　　基于红黑树的实现，支持有序操作，比如按照一个范围搜索元素。但是搜索效率不如HashSet。HashSet的搜索时间复杂度为O(1)，而TreeSet的搜索时间复杂度为O(logN)HashSet。

　　基于哈希表实现，支持快速查找，但不支持有序操作。并且丢失了元素的插入顺序信息，也就是说用迭代器遍历HashSet的结果是不确定的。LinkedHashSet

　　它具有HashSet的搜索效率，通过使用双向链表在内部维护元素的插入顺序。

2.2 List相关

　　ArrayList

　　基于动态数组，支持随机访问。Vector

　　类似于ArrayList，但它是线程安全的。LinkedList

　　基于双链表的实现，只能顺序访问，但可以在链表中间快速插入和删除元素。此外，LinkedList还可以用作堆栈、队列和双向队列。

2.3 Queue相关

　　LinkedList

　　可以实现双向排队。PriorityQueue

　　基于堆结构，可以用来实现优先级队列。

2.4 Map相关

　　TreeMap

　　基于红黑树的实现。HashMap

　　基于哈希表的实现。HashTable

　　类似于HashMap，但它是线程安全的，这意味着多个线程可以同时写入HashTable，而不会导致数据不一致。它是一个旧类，不应使用。现在可以使用ConcurrentHashMap来支持线程安全，它会更高效，因为它引入了分段锁。LinkedHashMap

　　双向链表用于维护元素的顺序。顺序是插入顺序或最近最少使用(LRU)顺序

3、集合重点

　　集合接口存储一组唯一且无序的对象。列表接口存储一组唯一的有序对象。Set接口存储一组唯一的无序对象。Map接口存储一组键-值对象，并提供键到值的映射。ArrayList实现可变长度数组，并在内存中分配连续空间。遍历元素和随机访问元素的效率比较高。LinkedList使用链表存储。插入和删除元素的效率很高。hash算法实现的set HashSet底层用HashMap实现，所以查询效率高。因为元素的内存地址直接由hashCode算法决定，增加效率

二、ArrayList分析

1、ArrayList使用

　　 ken 0 @ 166 . com

2、ArrayList介绍

　　 ArrayList是一个可以动态增长和收缩的索引序列。它是一个基于数组实现的列表类。这个类封装了一个动态重分发的Object[]数组，每个类对象都有一个capacity[属性，表示它们封装的Object[]数组的长度。当object []如果要向ArrayList中添加大量元素，可以使用ensurecapacity方法增加一次容量，这样可以减少重新分配的次数，提高性能。ArrayList的用法和Vector类似，但是Vector是比较老的集合，有很多缺点，不建议使用。另外，ArrayList和Vector的区别在于ArrayList是线程不安全的。当多个线程访问同一个ArrayList集合时，程序需要手动保证集合的同步，而Vector是线程安全的。

3、源码分析

3.1 继承结构与层次关系

　　公共类ArrayListE扩展AbstractListE

　　实现ListE、RandomAccess、Cloneable、java.io.Serializable

　　下面简单解释几个接口。

　　RandomAccess接口

　　这是一个有标记的接口，用于通过查看api文档进行快速随机访问。对于效率的问题，如果实现了接口，那么就用常见的For循环来遍历，性能更高，比如ArrayList。如果没有实现接口，就用Iterator来迭代，这样性能更高，比如linkedList。所以这个标记只是为了让我们知道用什么样的方式可以得到性能更好的数据。Cloneable接口

　　一旦实现了接口，对象。可以使用Clone()方法。Serializable接口

　　实现序列化接口，指示该类可以序列化。什么是序列化？简单来说，可以从类变成字节流传输，再从字节流变成原类。这里的继承结构可以通过IDEA中的NavigateType层次结构来查看。

3.2 属性

　　 //版本号

　　private static final long serial version uid=8683452581122892189 l；

　　//默认容量

　　private static final int DEFAULT _ CAPACITY=10；

　　//一个空对象数组

　　私有静态最终对象[]EMPTY _ element data={ }；

　　//默认空对象数组

　　私有静态最终对象[]default capacity _ EMPTY _ element data={ }；

　　//存储的数组元素

　　瞬态对象[]element data；//非私有以简化嵌套类访问

　　//实际的元素大小，默认为0

　　私有int大小；

　　//最大数组容量

　　private static final int MAX _ ARRAY _ SIZE=整数。MAX _ VALUE-8；

3.3 构造方法

　　 /**

　　*用指定的初始容量构造一个空列表

　　*如果指定的初始容量为负，则出现IllegalArgumentException。

　　*/public ArrayList(int initial capacity){

　　if (initialCapacity 0) {

　　this . element data=new Object[initial capacity]；

　　} else if (initialCapacity==0) {

　　this . element data=EMPTY _ element data；

　　}否则{

　　抛出新的IllegalArgumentException(非法容量：

　　初始容量)；

　　}}/**

　　*默认的空数组大小是10。

　　* ArrayList中存储的数据实际上是一个数组，这个数组就是elementData。

　　*/public ArrayList() {

　　this . element data=default capacity _ EMPTY _ element data；}/**

　　*按照集合迭代器返回的元素顺序，构造一个包含指定集合元素的列表。

　　*/public ArrayList(集合？扩展E c) {

　　element data=c . to array()；

　　if ((size=elementData.length)！=0) {

　　//转换为数组

　　//每个集合的toarray()实现方法不一样，需要判断。如果不是对象[]。类类型，使用ArrayList中的方法对其进行转换需要很长时间。

　　if (elementData.getClass()！=对象[]。类)

　　element data=arrays . copy of(element data，size，Object[]。类)；

　　}否则{

　　//否则，请使用空数组

　　this . element data=EMPTY _ element data；

　　}}

3.4 自动扩容

　　每当向数组中添加元素时，检查添加的元素数是否会超过当前数组的长度。如果是这样，阵列将被扩展以满足添加数据的需求。数组扩展是通过一个开放的方法实现的，保证ensureCapacity(int minCapacity)。在实际添加大量元素前，我也可以使用ensureCapacity来手动增加ArrayList实例的容量，以减少增量重分布的次数。

　　当数组扩展时，旧数组中的元素会被复制回新数组，每次数组容量都会增加到原来容量的1.5倍左右。* *这种操作的成本很高，在实际使用中要尽量避免阵列容量的扩大。当我们可以预测需要保存的元素数量时，就应该在构造ArrayList实例时指定它的容量，避免数组膨胀。或者根据实际需求通过调用ensureCapacity方法来手动增加ArrayList实例的容量。

　　私有void ensureCapacityInternal(int minCapacity){

　　ensureExplicitCapacity(calculate capacity(element data，min capacity))；} private static int calculate capacity(Object[]element data，int minCapacity) {

　　//判断初始化后的elementData是否为空数组，即没有长度。

　　if(element data==default capacity _ EMPTY _ element data){

　　//因为如果是空的话，最小容量=大小1；其实就是等于1,空的数组没有长度就存放不了

　　//所以就将最小容量变成10,也就是默认大小，但是在这里，还没有真正的初始化这个元素数据的大小

　　回归数学。max(DEFAULT _ CAPACITY，最小容量)；

　　}

　　//确认实际的容量，上面只是将最小容量=10,这个方法就是真正的判断元素数据是否够用

　　返回minCapacity}私有void ensureExplicitCapacity(int minCapacity){

　　modCount

　　//minCapacity如果大于了实际元素数据的长度，那么就说明元素数据数组的长度不够用

　　/*第一种情况：由于元素数据初始化时是空的数组，那么第一次增加的时候，

　　最小容量=大小1；也就minCapacity=1，在上一个方法（确定内部容量ensurecapacityininternal)

　　就会判断出是空的数组，就会给将最小容量=10,到这一步为止，还没有改变元素数据的大小。

　　第二种情况：元素数据不是空的数组了，那么在增加的时候，最小容量=大小1；也就是

　　最小容量代表着元素数据中增加之后的实际数据个数，拿着它判断元素数据的长度

　　是否够用，如果长度不够用，那么肯定要扩大容量，不然增加的这个元素就会溢出。*/

　　if(最小容量-元素数据。长度0)

　　增长(最小容量)；}//ArrayList核心的方法，能扩展数组大小的真正秘密私有void grow(int minCapacity){

　　//将扩充前的元素数据大小给旧产能

　　旧能力=要素数据。长度；

　　//newCapacity就是1.5倍的旧产能

　　int新产能=旧产能(旧产能1)；

　　/*这句话就是适应于元素数据就空数组的时候，长度=0,那么旧容量=0,新容量=0,

　　所以这个判断成立，在这里就是真正的初始化元素数据的大小了，就是为10.前面的工作都是准备工作。

　　*/

　　if (newCapacity - minCapacity 0)

　　newCapacity=minCapacity

　　//如果新产能超过了最大的容量限制，就调用巨大的容量，也就是将能给的最大值给新产能

　　if (newCapacity - MAX_ARRAY_SIZE 0)

　　新增产能=巨大产能(最小产能)；

　　//新的容量大小已经确定好就复制数组，改变容量大小。

　　元素数据=数组。(元素数据、新容量)的副本；}//用来赋最大值私有静态int大容量(int小容量){

　　if (minCapacity 0) //溢出

　　抛出新的内存不足错误()；

　　//如果最小容量都大于最大数组大小，那么就整数。最大值返回，反之将最大数组大小返回。

　　//相当于给数组列表上了两层防护

　　return(最小容量MAX _ ARRAY _ SIZE)？

　　整数。最大值：

　　最大数组大小；}

3.5 add()方法

　　 /**

　　* 添加一个特定的元素到目录的末尾。

　　* 先尺寸一判断数组容量是否够用，最后加入元素

　　*/公共布尔值添加(英文)

　　ensureCapacityInternal(大小为1);//递增modCount！

　　元素数据[大小]=e；

　　返回true}/**

　　*在此中的指定位置插入指定元素

　　*列表。移动当前位于该位置的元素（如果有)

　　*右侧的任何后续元素（将它们的索引加1)。

　　*

　　* @param索引要插入指定元素的索引

　　* @param元素要插入的元素

　　* @ throws IndexOutOfBoundsException { @ inherit doc }

　　*/公共void add(int index，E element) {

　　//检查指数也就是插入的位置是否合理。

　　rangeCheckForAdd(index)；

　　//检查容量是否够用，不够就自动扩容

　　ensureCapacityInternal(大小为1);//递增modCount！

　　//这个方法就是用来在插入元素之后，要将指数之后的元素都往后移一位

　　System.arraycopy(elementData，index，elementData，index 1，

　　尺寸指数);

　　元素数据[索引]=元素；

　　尺寸；}当调用添加()方法时，实际函数调用：

　　addensureCapacityInternalensureExplicitCapacity(growhugeCapacity)

　　例如，如果在初始化一个空数组后添加一个值，它将首先自动展开。

3.6 trimToSize()

　　将基础数组的容量调整为当前列表中存储的实际元素的大小的功能

　　public void trimToSize() {

　　modCount

　　if (size elementData.length) {

　　elementData=(大小==0)

　　？EMPTY _ element data:arrays . copy of(element data，size)；

　　} }

3.7 remove()方法

　　 remove()方法也有两个版本。一个是remove(int index)删除指定位置的元素，另一个是remove(Object o)删除第一个满足o.equals(elementData[index])的元素。删除操作是add()操作的逆过程，删除点之后的元素需要前移一个位置。注意，为了让GC工作，您必须显式地为最后一个位置分配一个null值。

　　public E remove(int index) {

　　rangeCheck(索引)；

　　modCount

　　e old value=element data(index)；

　　int num moved=size-index-1；

　　if (numMoved 0)

　　System.arraycopy(元素数据，索引1，元素数据，索引，

　　num moved)；

　　element data[-size]=null；//清除这个位置的引用，让GC工作

　　返回旧值；

　　}

3.8 其他方法

　　这里简单介绍一下核心方法，其他方法可以通过查源代码快速了解。

3.9 Fail-Fast机制

　　 ArrayList采用快速失效的机制，通过记录modCount参数来实现。面对并发修改，迭代器很快就会彻底失败，抛出一个ConcurrentModificationException异常，而不是在未来一个不确定的时间，冒任何不确定行为的风险。

4、总结

　　 ArrayList可以存储nullArrayList，本质上是一个elementData数组。ArrayList不同于数组，它可以自动扩展大小。关键方法是gorw()方法。ArrayList中removeAll(集合c)和clear()的区别在于，removeAll可以删除batch中指定的元素，而clear是删除集合中的所有元素。ArrayList本质上是一个数组，所以在数据查询时会很快，但是在插入和删除这些元素时，性能下降很多，需要移动很多数据才能达到想要的效果。ArrayList实现了RandomAccess，所以在遍历的时候建议使用for循环

三、LinkedList分析

1、LinkedList使用

　　 ken 1 @ 166 . com

2、LinkedList介绍

　　链表同时实现了List接口和Deque接口，也就是说在堆栈的时候可以把它看成一个顺序容器，一个队列，一个队列。这样看来，LinkedList简直就是全能冠军。当需要使用堆栈或队列时，可以考虑使用LinkedList。一方面，Java官方已经声明不推荐Stack类。更何况Java里根本没有叫Queue_的类(是接口名)。关于堆栈或队列，现在的首选是ArrayDeque，它比LinkedList(当用作堆栈或队列时)有更好的性能。

　　LinkedList的实现决定了所有下标相关的操作都是线性的，而删除开头或结尾的元素只需要一个常数的时间。为了追求效率，LinkedList是不同步的。如果多个线程需要并发访问它，可以用Collections.synchronizedList()的方法包装它。

3、源码分析

3.1 继承结构与层次

　　公共类链接列表

　　扩展AbstractSequentialListE

　　实现ListE、DequeE、Cloneable、java.io.Serializable

　　这里我们可以发现LinkedList多了一层AbstractSequentialList的抽象类，这是为了减少实现LinkedList这类的工作。如果要实现顺序访问的类(也就是链表形式)，就要继承这个抽象类。如果要实现array这样的随机访问类，就要实现抽象类。

　　List接口

　　添加、设置等。操作列表Deque接口的一些方法

　　队列Cloneable接口有各种特征

　　是，使用复制方法Serializable接口。

　　可以连载。没有RandomAccess

　　推荐使用迭代器，里面有一个foreach，增强的for循环，里面的原理是迭代器。我们在使用的时候用foreach或者iterator

3.2 属性与构造方法

　　 transient关键字来修饰，这也意味着序列化的时候不会序列化域。

　　//元素的实际数量transient int size=0；

　　//Head节点transient nodefirst

　　//尾节点transient nodelastpublic linked list(){ } public linked list(集合？扩展E c) {

　　this()；

　　//将集合C中的每个元素构建到一个LinkedList中

　　addAll(c)；}

3.3 内部类Node

　　 //根据前面介绍的double linkedList，你就知道这代表什么了。链表的秘密在这里是私有静态类NodeE {

　　//数据字段(当前节点的值)

　　e项；

　　//继任者

　　NodeE next

　　//前驱

　　NodeE prev

　　//构造函数，将前任赋值给继任者。

　　节点(上一个节点，元素，下一个节点){

　　this.item=element

　　this.next=next

　　this.prev=prev

　　}}

3.4 核心方法add()和addAll()

　　公共布尔加法(E e) {

　　link last(e)；

　　返回true}void linkLast(E e) {

　　//临时节点L(L的小写)保存最后一个，即L指向最后一个节点

　　final NodeE l=last

　　//将e封装成一个节点，e.prev指向最后一个节点

　　final NodeE newNode=新节点(l，e，null)；

　　//newNode成为最后一个节点，所以last指向它

　　last=newNode

　　if (l==null)

　　//确定链表开头是否什么都没有。如果不是，新节点成为第一个节点，第一个和最后一个都指向它。

　　first=newNode

　　其他

　　//正常追加在最后一个节点之后，那么原来最后一个节点的next就会指向现在真正的最后一个节点，原来的最后一个节点就会变成倒数第二个节点。

　　l.next=newNode

　　//添加一个节点，大小会增加。

　　尺寸；

　　modCount}addAll()有两个重载函数，addAll(集合？扩展E) type和addAll(int，Collection？扩展E)类型，我们习惯于调用addAll(集合？Extends E)类型将被转换为addAll(int，Collection？扩展)类型

　　public boolean addAll(集合？扩展E c) {

　　返回addAll(大小，c)；}公共布尔addAll(int index，Collection？扩展E c) {

　　//检查索引是否合理。

　　checkPositionIndex(索引)；

　　//将集合C转换为对象数组

　　object[]a=c . to array()；

　　//数组A的长度numNew，即由多少个元素组成

　　int numNew=a.length

　　if (numNew==0)

　　//如果为空，则不执行任何操作

　　返回false

　　NodeE pred，succ

　　//构造函数中传递的是index==size

　　//情况一：构造一个方法创建的空链表，那么size=0，并且last，first都为null。linkedList为空。

　　//没有节点。succ=null、pred=last=null

　　//情况二：如果链表中有节点，大小不为0。first和last分别指向第一个节点和最后一个节点，

　　//如果在最后一个节点后面追加一个元素，就要记录最后一个节点是什么，所以把最后一个保存到pred临时节点。

　　//案例3索引！=size，说明不是前两种情况，而是在链表中间插入元素，那么你得知道index上的节点是谁，

　　//保存到succ的临时节点，然后将succ的前一个节点保存到pred，这样两个节点就可以准确插入了。

　　if (index==size) {

　　succ=null

　　pred=last

　　}否则{

　　succ=节点(索引)；

　　pred=succ.prev

　　}

　　对于(对象o : a) {

　　@SuppressWarnings(未检查)E E=(E)o；

　　NodeE newNode=新节点(pred，e，null)；

　　if (pred==null)

　　first=newNode

　　其他

　　pred.next=newNode

　　pred=newNode

　　}

　　if (succ==null) {

　　/*如果succ==null，说明是情况一或者情况二，

　　第一，构造方法，也就是刚创建的空链表，pred已经是newNode了，

　　Last=newNode，所以linkedList的第一个和最后一个指向第一个节点。

　　第二，在最后一个节之后添加节点，那么原来的last应该指向现在的最后一个节点，

　　是newNode。*/

　　last=pred

　　}否则{

　　pred.next=succ

　　succ.prev=pred

　　}

　　size=numNew

　　modCount

　　返回true}//根据索引找到节点，返回nodeNode (int index) {

　　//确定插入的位置是在链表的前半部分还是后半部分。

　　if(索引(大小1)) {

　　NodeE x=first

　　//从头节点向前遍历

　　for(int I=0；I指数；我)

　　x=x . next；

　　返回x；

　　}否则{

　　NodeE x=last

　　//从尾节点向后遍历

　　for(int I=size-1；I指数；我-)

　　x=x . prev；

　　返回x；

　　}}

3.5 remove()

　　 /*如果我们要移除的值在链表中有多个相同的值，那么我们

　　具有最小索引的值，即第一个找到的值，将被删除。如果该值不存在，将不会执行任何操作。

　　*/public boolean remove(Object o){

　　if (o==null) {

　　for(NodeE x=first；x！=nullx=x.next) {

　　if (x.item==null) {

　　unlink(x)；

　　返回true

　　}

　　}

　　}否则{

　　for(NodeE x=first；x！=nullx=x.next) {

　　if (o.equals(x.item)) {

　　unlink(x)；

　　返回true

　　}

　　}

　　}

　　返回false}不能传递空值E unlink(NodeE x) {

　　//断言x！=null

　　最终E元素=x . item；

　　final NodeE next=x.next

　　最终NodeE prev=x.prev

　　if (prev==null) {

　　第一个=下一个；

　　}否则{

　　prev.next=next

　　x.prev=null

　　}

　　if (next==null) {

　　last=prev

　　}否则{

　　next.prev=prev

　　x.next=null

　　}

　　//x的前后点都是null，项也是null，让gc回收。

　　x.item=null

　　尺寸-；

　　modCount

　　返回元素；}

3.6 其他方法

　　 **get(index)，indexOf(Object o)**等等，只需查看源代码即可。

3.7 LinkedList的迭代器

　　在LinkedList中，除了Node的一个内部类，应该还能看到另外两个内部类，就是ListItr，另外一个就是DescendingIterator的内部类。

　　/*这个类也叫ListItr，用来封装Itr中的几个方法，让用户用正常的思维写代码，

　　比如从后向前遍历时，和从前向后遍历一样，使用next等操作，而不是使用特殊的previous。

　　*/私有类派生迭代器实现迭代器{

　　private final ListItr itr=new ListItr(size())；

　　public boolean hasNext() {

　　返回itr . has previous()；

　　}

　　public E next() {

　　返回itr . previous()；

　　}

　　公共void remove() {

　　itr . remove()；

　　}}

4、总结

　　 linkedList本质上是一个双向链表，由Node的内部类实现。LinkedList可以存储空值。对比ArrayList，我们才真正知道linkedList在删除和添加操作上有着不错的性能，而ArrayList的查询性能也不错。从源码来看，并不缺乏容量。LinkedList不仅可以向前迭代，还可以像后迭代一样迭代，并且在迭代的过程中，可以修改、添加和删除值。linkedList不仅可以用作链表，也可以用作队列。这是因为Deque接口的实现

四、List总结

1、ArrayList和LinkedList区别

　　 ArrayList。最下面是随机访问类型，可以自动扩展。初始化时，数组的长度为0，只有添加元素时长度才会增加。默认值为10，不能无限扩展。有上限，查询操作时性能更好。LinkedList的底层是通过链表实现的，是一个双向链表。注意这不是双向循环链表，是顺序访问类型。在源代码中，元素的数量似乎没有限制。应该是无限增加，直到内存满了再删除，加操作的时候性能会更好。两者都是线程不安全的。使用迭代器时，会出现fail-fast：快速失效。

2、ArrayList和Vector区别

　　 ArrayList线程不安全。使用迭代器时，会发生fail-fastVector的线程安全问题。因为Synchronized关键字是在方法之前添加的，所以fail-fast

3、fail-fast和fail-safe区别与情况说明

　　fail-fast也会发生。

　　快速失败，比如用迭代器遍历arrayList时，另一个线程改变了arrayList的存储数组，使其在结构上不同于add和delete，所以迭代器会快速报告一个java.util.concurrency异常(并发修改异常)，这是快速失败fail-safe。

　　安全失败，java.util.concurrent下的类是线程安全类。在迭代过程中，如果任何一个线程改变了它的结构，它都不会报告异常，而是正常遍历。这是安全故障为什么在java.util.concurrent包下对集合有结构的改变却不会报异常？。

　　在concurrent下向集合类添加元素时，使用Arrays.copyOf()复制副本，并向副本添加元素。如果其他线程改变了这里集合的结构，那也是对副本的改变，而不是影响原来的集合。迭代器仍然照常遍历。遍历完之后，把原来的引用改成指向副本，这样一句话，如果这个包下的类被添加或者删除，就会出现一个副本。所以fail-fast是可以预防的，这个机制不会出错，所以我们把这种现象叫做fail-safevector也是线程安全的，为什么是fail-fast呢？。

　　出现故障保护是因为它们添加和删除的底层机制不同。如上所述，会有副本，而它们的底层机制如arrayList、linekdList、verctor等。都是在实引用上操作，所以出现异常

4、为什么现在都不提倡使用Vector

　　 vector实现线程安全的方法是锁定每个操作方法，这些锁并不是必须的。在实际开发中，线程安全一般是通过锁定一系列操作来实现的，也就是说，将需要同步的资源锁定在一起，以保证线程安全。如果多个线程并发执行一个锁定的方法，但是在这个方法中，存在Vector，Vector

　　实现本身已经被锁定，所以相当于加锁加锁，会造成额外的开销。Vector也有fail-fast的问题，也就是说不能保证遍历安全性。当遍历时，它必须被锁定，这是额外的开销。不如直接用arrayList，然后再锁一次。总结：Vector也会在你不需要线程安全的时候锁定你，导致额外的开销。所以在jdk1.5之后就废弃了，现在如果你想使用线程安全的集合，总是从java.util.concurrent包中获取相应的类。

五、HashMap分析

1、HashMap介绍

1.1 Java8以前的HashMap

　　 HashMap实现了Map接口，允许你放入空键的元素，插入空值的元素；除了这个类没有实现同步，其余和Hashtable大致相同；与TreeMap不同，该容器不保证元素的顺序。容器可能会根据需要对元素进行重新散列，元素的顺序也会重新分散，所以不同时间迭代同一个HashMap的顺序可能会有所不同。根据处理冲突的方式不同，哈希表有两种实现方式，一种是开放寻址，另一种是用链表单独链接。Java7 HashMap采用的是冲突链表方式。

1.2 Java8后的HashMap

　　 Java8对HashMap做了一些修改。最大的区别是使用了红黑树，所以由数组+链表+红黑树组成。根据Java7 HashMap的介绍，我们知道在搜索的时候，可以根据哈希值快速定位到数组的具体下标，但是之后就需要按照链表一个一个的查找我们需要的东西了。时间复杂度取决于链表的长度为O(n)。为了减少这部分的开销，在Java8中，当链表中有八个元素时，链表将被转换为红黑树，在这些位置进行搜索时，时间复杂度可以降低到O(logN)。

　　在Java7中使用Entry来表示HashMap中的每个数据节点，在Java8中使用Node。基本没有区别。它们都是四个属性：键、值、散列和下一个。但是Node只能用在链表中，红黑树需要TreeNode。

2、Java8 HashMap源码分析

2.1 继承结构与层次

　　公共类HashMapK，V扩展AbstractMapK，V

　　实现MapK，V，可克隆，可序列化

2.2 属性

　　 //序列号private static final long serialVersionUID=362498820763181265 l；

　　//默认的初始容量static final int DEFAULT _ INITIAL _ CAPACITY=1 4；

　　//又名16

　　//最大容量静态最终int MAXIMUM _ CAPACITY=1 30

　　//默认加载因子静态最终浮动默认负载系数=0.75f

　　//当桶（桶)上的结点数大于这个值时会转成红黑树静态最终int tree ify _ THRESHOLD=8；

　　//当桶（桶)上的结点数小于这个值时树转链表静态最终int un tre ify _ THRESHOLD=6；

　　//桶中结构转化为红黑树对应的桌子的最小大小静态最终int MIN _ TREEIFY _ CAPACITY=64

　　//存储元素的数组，总是2的幂次倍瞬态NodeK，V[]表；

　　//存放具体元素的集瞬态设置地图.EntryK，V entrySet

　　//存放元素的个数，注意这个不等于数组的长度瞬态（同Internationalorganizations）国际组织大小；

　　//每次扩容和更改地图结构的计数器瞬态int modCount

　　//临界值，当实际大小（容量*填充因子)超过临界值时，会进行扩容（同Internationalorganizations）国际组织阈值；

　　//填充因子，计算模拟的实时装载因子的方法为：大小/容量最终浮动负载系数；

2.3 构造方法

　　 public HashMap(int初始容量，float loadFactor) {

　　//初始容量不能小于0,否则报错

　　if (initialCapacity 0)

　　抛出新的IllegalArgumentException(非法初始容量：

　　初始容量);

　　//初始容量不能大于最大值，否则为最大值

　　如果(初始容量最大容量)

　　初始容量=max _ CAPACITY

　　//填充因子不能小于或等于0,不能为非数字

　　if(加载因子=0 float。负载系数)

　　抛出新的IllegalArgumentException(非法加载因子：

　　负载系数);

　　//初始化填充因子

　　this.loadFactor=负载系数；

　　//初始化阈值大小

　　这个。threshold=tablesize for(初始容量)；}//这个方法将传进来的参数转变为2的n次方的数值静态船方不负担装货费用

　　nal int tableSizeFor(int cap) {

　　 int n = cap - 1;

　　 n = n >>> 1;

　　 n = n >>> 2;

　　 n = n >>> 4;

　　 n = n >>> 8;

　　 n = n >>> 16;

　　 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}/**

　　 * 自定义初始容量，加载因子为默认

　　 */public HashMap(int initialCapacity) {

　　 this(initialCapacity, DEFAULT_LOAD_FACTOR);}/**

　　 * 使用默认的加载因子等字段

　　 */public HashMap() {

　　 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}public HashMap(Map<? extends K, ? extends V> m) {

　　 //初始化填充因子

　　 this.loadFactor = DEFAULT_LOAD_FACTOR;

　　 //将m中的所有元素添加至HashMap中

　　 putMapEntries(m, false);}//将m的所有元素存入该实例final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {

　　 int s = m.size();

　　 if (s > 0) {

　　 //判断table是否已经初始化

　　 if (table == null) { // pre-size

　　 //未初始化，s为m的实际元素个数

　　 float ft = ((float)s / loadFactor) + 1.0F;

　　 int t = ((ft < (float)MAXIMUM_CAPACITY) ?

　　 (int)ft : MAXIMUM_CAPACITY);

　　 //计算得到的t大于阈值，则初始化阈值

　　 if (t > threshold)

　　 threshold = tableSizeFor(t);

　　 }

　　 else if (s > threshold)

　　 resize();

　　 //将m中的所有元素添加至HashMap中

　　 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {

　　 K key = e.getKey();

　　 V value = e.getValue();

　　 putVal(hash(key), key, value, false, evict);

　　 }

　　 }}

2.4 核心方法

　　先计算key的hash值，然后根据hash值搜索在table数组中的索引位置，如果table数组在该位置处有元素，则查找是否存在相同的key，若存在则覆盖原来key的value，否则将该元素保存在链表尾部，注意JDK1.7中采用的是头插法，即每次都将冲突的键值对放置在链表头，这样最初的那个键值对最终就会成为链尾，而JDK1.8中使用的是尾插法。此外，若table在该处没有元素，则直接保存。

　　public V put(K key, V value) {

　　 return putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

　　 boolean evict) {

　　 Node<K,V>[] tab; Node<K,V> p; int n, i;

　　 //第一次put元素时，table数组为空，先调用resize生成一个指定容量的数组

　　 if ((tab = table) == null (n = tab.length) == 0)

　　 n = (tab = resize()).length;

　　 //hash值和n-1的与运算结果为桶的位置，如果该位置空就直接放置一个Node

　　 if ((p = tab[i = (n - 1) & hash]) == null)

　　 tab[i] = newNode(hash, key, value, null);

　　 //如果计算出的bucket不空，即发生哈希冲突，就要进一步判断

　　 else {

　　 Node<K,V> e; K k;

　　 //判断当前Node的key与要put的key是否相等

　　 if (p.hash == hash &&

　　 ((k = p.key) == key (key != null && key.equals(k))))

　　 e = p;

　　 //判断当前Node是否是红黑树的节点

　　 else if (p instanceof TreeNode)

　　 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

　　 //以上都不是，说明要new一个Node，加入到链表中

　　 else {

　　 for (int binCount = 0; ; ++binCount) {

　　 //在链表尾部插入新节点，注意jdk1.8是在链表尾部插入新节点

　　 if ((e = p.next) == null) {

　　 p.next = newNode(hash, key, value, null);

　　 // 如果当前链表中的元素大于树化的阈值，进行链表转树的操作

　　 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

　　 treeifyBin(tab, hash);

　　 break;

　　 }

　　 //在链表中继续判断是否已经存在完全相同的key

　　 if (e.hash == hash &&

　　 ((k = e.key) == key (key != null && key.equals(k))))

　　 break;

　　 p = e;

　　 }

　　 }

　　 //走到这里，说明本次put是更新一个已存在的键值对的value

　　 if (e != null) { // existing mapping for key

　　 V oldValue = e.value;

　　 if (!onlyIfAbsent oldValue == null)

　　 e.value = value;

　　 //在hashMap中，afterNodeAccess方法体为空，交给子类去实现

　　 afterNodeAccess(e);

　　 return oldValue;

　　 }

　　 }

　　 ++modCount;

　　 //如果当前size超过临界值，就扩容。注意是先插入节点再扩容

　　 if (++size > threshold)

　　 resize();

　　 //在hashMap中，afterNodeInsertion方法体为空，交给子类去实现

　　 afterNodeInsertion(evict);

　　 return null;}resize() 数组扩容

　　用于初始化数组或数组扩容，每次扩容后，容量为原来的 2 倍，并进行数据迁移

　　final Node<K,V>[] resize() {

　　 Node<K,V>[] oldTab = table;

　　 int oldCap = (oldTab == null) ? 0 : oldTab.length;

　　 int oldThr = threshold;

　　 int newCap, newThr = 0;

　　 if (oldCap > 0) { // 对应数组扩容

　　 if (oldCap >= MAXIMUM_CAPACITY) {

　　 threshold = Integer.MAX_VALUE;

　　 return oldTab;

　　 }

　　 // 将数组大小扩大一倍

　　 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

　　 oldCap >= DEFAULT_INITIAL_CAPACITY)

　　 // 将阈值扩大一倍

　　 newThr = oldThr << 1; // double threshold

　　 }

　　 else if (oldThr > 0) // 对应使用 new HashMap(int initialCapacity) 初始化后，第一次 put 的时候

　　 newCap = oldThr;

　　 else {// 对应使用 new HashMap() 初始化后，第一次 put 的时候

　　 newCap = DEFAULT_INITIAL_CAPACITY;

　　 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

　　 }

　　 if (newThr == 0) {

　　 float ft = (float)newCap * loadFactor;

　　 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?

　　 (int)ft : Integer.MAX_VALUE);

　　 }

　　 threshold = newThr;

　　 // 用新的数组大小初始化新的数组

　　 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

　　 table = newTab; // 如果是初始化数组，到这里就结束了，返回 newTab 即可

　　 if (oldTab != null) {

　　 // 开始遍历原数组，进行数据迁移。

　　 for (int j = 0; j < oldCap; ++j) {

　　 Node<K,V> e;

　　 if ((e = oldTab[j]) != null) {

　　 oldTab[j] = null;

　　 // 如果该数组位置上只有单个元素，那就简单了，简单迁移这个元素就可以了

　　 if (e.next == null)

　　 newTab[e.hash & (newCap - 1)] = e;

　　 // 如果是红黑树，具体我们就不展开了

　　 else if (e instanceof TreeNode)

　　 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

　　 else {

　　 // 这块是处理链表的情况，

　　 // 需要将此链表拆成两个链表，放到新的数组中，并且保留原来的先后顺序

　　 // loHead、loTail 对应一条链表，hiHead、hiTail 对应另一条链表，代码还是比较简单的

　　 Node<K,V> loHead = null, loTail = null;

　　 Node<K,V> hiHead = null, hiTail = null;

　　 Node<K,V> next;

　　 do {

　　 next = e.next;

　　 if ((e.hash & oldCap) == 0) {

　　 if (loTail == null)

　　 loHead = e;

　　 else

　　 loTail.next = e;

　　 loTail = e;

　　 }

　　 else {

　　 if (hiTail == null)

　　 hiHead = e;

　　 else

　　 hiTail.next = e;

　　 hiTail = e;

　　 }

　　 } while ((e = next) != null);

　　 if (loTail != null) {

　　 loTail.next = null;

　　 // 第一条链表

　　 newTab[j] = loHead;

　　 }

　　 if (hiTail != null) {

　　 hiTail.next = null;

　　 // 第二条链表的新的位置是 j + oldCap，这个很好理解

　　 newTab[j + oldCap] = hiHead;

　　 }

　　 }

　　 }

　　 }

　　 }

　　 return newTab;}get()过程

　　public V get(Object key) {

　　 Node<K,V> e;

　　 return (e = getNode(hash(key), key)) == null ? null : e.value;}final Node<K,V> getNode(int hash, Object key) {

　　 Node<K,V>[] tab; Node<K,V> first, e; int n; K k;

　　 if ((tab = table) != null && (n = tab.length) > 0 &&

　　 (first = tab[(n - 1) & hash]) != null) {

　　 // 判断第一个节点是不是就是需要的

　　 if (first.hash == hash && // always check first node

　　 ((k = first.key) == key (key != null && key.equals(k))))

　　 return first;

　　 if ((e = first.next) != null) {

　　 // 判断是否是红黑树

　　 if (first instanceof TreeNode)

　　 return ((TreeNode<K,V>)first).getTreeNode(hash, key);

　　 // 链表遍历

　　 do {

　　 if (e.hash == hash &&

　　 ((k = e.key) == key (key != null && key.equals(k))))

　　 return e;

　　 } while ((e = e.next) != null);

　　 }

　　 }

　　 return null;}

2.5 其他方法

3、总结

　　HashMap在JDK1.8以前是一个链表散列这样一个数据结构，而在JDK1.8以后是一个数组加链表加红黑树的数据结构通过源码的学习，HashMap是一个能快速通过key获取到value值得一个集合，原因是内部使用的是hash查找值得方法另外LinkedHashMap是HashMap的直接子类，二者唯一的区别是LinkedHashMap在HashMap的基础上，采用双向链表(doubly-linked list)的形式将所有**entry**连接起来，这样是为保证元素的迭代顺序跟插入顺序相同

六、Collections工具类

1、概述

2、排序常用方法

　　static void reverse(List<?> list)

　　//对List集合元素进行随机排序

　　static void shuffle(List<?> list)

　　//根据元素的自然顺序 对指定列表按升序进行排序

　　static void sort(List<T> list)

　　//根据指定比较器产生的顺序对指定列表进行排序

　　static <T> void sort(List<T> list, Comparator<? super T> c)

　　//在指定List的指定位置i,j处交换元素

　　static void swap(List<?> list, int i, int j)

　　//当distance为正数时，将List集合的后distance个元素“整体”移到前面；当distance为负数时，将list集合的前distance个元素“整体”移到后边。该方法不会改变集合的长度

　　static void rotate(List<?> list, int distance)

3、查找、替换操作

　　//注意：此前必须保证List集合中的元素已经处于有序状态

　　static <T> int binarySearch(List<? extends Comparable<? super T>>list, T key)

　　//根据元素的自然顺序，返回给定collection 的最大元素

　　static Object max(Collection coll)

　　//根据指定比较器产生的顺序，返回给定 collection 的最大元素

　　static Object max(Collection coll,Comparator comp):

　　//根据元素的自然顺序，返回给定collection 的最小元素

　　static Object min(Collection coll):

　　//根据指定比较器产生的顺序，返回给定 collection 的最小元素

　　static Object min(Collection coll,Comparator comp):

　　//使用指定元素替换指定列表中的所有元素

　　static <T> void fill(List<? super T> list,T obj)

　　//返回指定co1lection中等于指定对象的出现次数

　　static int frequency(collection<?>c,object o)

　　//返回指定源列表中第一次出现指定目标列表的起始位置；如果没有出现这样的列表，则返回-1

　　static int indexofsubList(List<?>source, List<?>target)

　　//返回指定源列表中最后一次出现指定目标列表的起始位置；如果没有出现这样的列表，则返回-1

　　static int lastIndexofsubList(List<?>source,List<?>target)

　　//使用一个新值替换List对象的所有旧值o1dval

　　static <T> boolean replaceA1l(list<T> list,T oldval,T newval)

4、同步控制

　　//返回指定 Collection 支持的同步（线程安全的）collection

　　static <T> Collection<T> synchronizedCollection(Collection<T> c)

　　//返回指定列表支持的同步（线程安全的）列表

　　static <T> List<T> synchronizedList(List<T> list)

　　//返回由指定映射支持的同步（线程安全的）映射

　　static <K,V> Map<K,V> synchronizedMap(Map<K,V> m)

　　//返回指定 set 支持的同步（线程安全的）set

　　static <T> Set<T> synchronizedSet(Set<T> s)

5、Collection设置不可变集合

　　emptyXxx()

　　//返回一个只包含指定对象（只有一个或一个元素）的不可变的集合对象，此处的集合可以是：List，Set，Map。

　　singletonXxx():

　　//返回指定集合对象的不可变视图，此处的集合可以是：List，Set，Map

　　unmodifiableXxx()推荐学习：《java教程》

　　以上就是详细解析Java集合框架的详细内容，更多请关注我们其它相关文章！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。