首页  思维导图  详情

002 - Java集合

2022-02-03 22:46:57   0  举报





AI智能生成

绝对高质量

Java集合

List

Set

Map

JUC

作者其他创作

大纲/内容

图解Java集合

继承关系

知识点汇总

集合是什么？基本概念

集合类存放于Java.util包中，主要有3种：set(集）、list(列表包含Queue）和map(映射)。

在jdk1.2之后，Java提供了实现常见数据结构的类，这些实现数据结构的类通称为Java集合框架

集合在我们的日常开发中所使用的次数简直太多了，你已经把它们都用的熟透了，

集合在我们日常开发使用的次数数不胜数

ArrayList/LinkedList/HashMap/HashSet…信手拈来，抬手就拿来用，在IDE上龙飞凤舞

日常开发中，不仅要了解Java中的Collection及其子类的用法，还要了解Collections 用法。可以提升很多处理集合类的效率。

合格的程序员

了解它的基本用法

了解怎么使用API

了解它的源码

了解它是如何设计和实现的

知道它内部发生了什么事情，就像开了透视外挂一样

洞穿一切，这种感觉才真的爽，

而且这样就不是集合提供什么功能给我们使用，而是我们选择使用它的什么功能了。

了解它的衍生过程

图解庞大集合框架Collection的家族体系和成员

Collection这个庞大集合框架的家族体系和成员

图解

集合框架总览

上图堪称集合框架的上帝视角

列表爷爷辈儿的接口/集合框架提供了遍历接口

Iterator接口（1.8之前）

在早期，遍历集合的方式只有一种，通过Iterator迭代器操作

代码案例

什么是迭代器（Iterator）

Iterator接口提供了很多对集合元素进行迭代的方法。

每一个集合类都包含了可以返回迭代器实例的

迭代方法。迭代器可以在迭代的过程中删除底层集合的元素。

迭代器，可以通过迭代器遍历集合中的数据

Iterator（迭代器）

API接口含义

hasNext ()：判断集合中是否存在下一个对象

next()：返回集合中的下一个对象，并将访问指针移动一位

remove ()：删除集合中调用next()方法返回的对象

图解Iterator接口

Enumeration接口和Iterator接口的区别有哪些？

速度不同

Enumeration速度是Iterator的2倍，同时占用更少的内存。

函数接口数量不同

Enumeration 只有2 个函数接口。通过Enumeration，只能读取集合的数据，而不能对数据进行修改。

Iterator 只有3 个函数接口。Iterator 除了能读取集合的数据之外，也能数据进行删除操作。

是否支持fail-fast 机制

Enumeration 是JDK 1.0 添加的接口。使用到它的函数包括Vector、Hashtable 等类，这
些类都是JDK 1.0 中加入的，Enumeration 存在的目的就是为它们提供遍历接口。Enumeration
本身并没有支持同步，而在Vector、Hashtable 实现Enumeration 时，添加了同步。

而Iterator 是JDK 1.2 才添加的接口，它也是为了HashMap、ArrayList 等集合提供遍历接
口。Iterator 是支持fail-fast 机制的：当多个线程对同一个集合的内容进行操作时，就可能会产
生fail-fast 事件。

Iterator 支持fail-fast 机制，而Enumeration 不支持。

使用场景

注意：Enumeration 迭代器只能遍历Vector、Hashtable 这种古老的集合，因此通
常不要使用它，除非在某些极端情况下，不得不使用Enumeration，否则都应该选择
Iterator 迭代器。

Iterable 接口（for-each）

实现此接口允许对象成为for-each循环的目标

增强for循环

案例代码

举例1

举例2

它是Java中的一种语法糖

步骤：通过命令：javap -c反编译上面的这段代码后

结论：发现它只是Java中的一个语法糖，

总结：本质上还是调用Iterator去遍历。

说明：翻译成代码，就和一开始的Iterator迭代器遍历方式基本相同了.

子主题

语法糖

也译为糖衣语法

（Syntactic sugar）

指计算机语言中添加的某种语法，这种语法对语言的功能并没有影响，但是更方便程序员使用。

通常来说使用语法糖能够增加程序的可读性，从而减少程序代码出错的机会。

Iterable接口源码

Iterable接口里面提供了Iterator接口

Iterable接口里面提供了Iterator接口，所以实现了Iterable接口的集合，依旧可以使用迭代器追历和操作集合中的对象：

在JDK 1.8之前，Iterable只有iterator —个方法，就是Iterator<T> iterator();

实现此接口的方法能够创建一个轻量级的迭代器，用于安全的遍历元素，移除元素，添加元素。

能创建迭代器进行元素的添加和删除，就尽量使用迭代器进行添加和删除。

fail-fast机制

也可以使用迭代器的方式进行遍历

样例

在JDK 1.8之后， Iterable提供了一个新的方法for Each()，

它允许使用增强for循环遍历对象。

除了实现此接口的对象外，数组也可以用for-each循环遍历

数组也可以用for-each循环遍历

为什么要设计两个接口，而不是保留其中一个即可？

Iterator

Iterator的保留可以让子类去实现自己的迭代器

Iterator是提供集合操作内部对象的一个迭代器，它可以遍历、移除对象，且只能够单向移动

Iterable

Iterable接口更加关注于for-each的增强语法

对Iterator的封装，在JDK 1.8时，实现了Iterable接口的集合可以使用增强for循环遮历集合对象

通过反编译后发现，底层还是使用Iterator迭代器进行遍历

ListIterator接口（双向遍历）

是什么？

ListIterator是Iterator的优化版，

ListIterator它继承Iterator接口，

有什么？

支持在任意一个位置进行前后双向遍历。

在遍历List集合时，可以从任意索引下标开始遍历，而且支持双向遍历。

Listiterator存在于List集合之中，通过调用方法可以返回起始下标为index的迭代器

返回起始下标为index的迭代器

图解ListIterator源码

有几个重要方法，大多数方法与Iterator中定义的含义相同

比Iterator强大的地方是

在任意一个下标位置，返回该迭代器

可以实现双向遍历

Iterator和ListIterator的区别是什么？

【遍历内容】Iterator可用来遍历Set和List集合，但是ListIterator只能用来遍历List。

【遍历方向】Iterator对集合只能是前向遍历，ListIterator既可以前向也可以后向。

ListIterator实现了Iterator接口，并包含其他的功能

增加元素

替换元素

获取前一个和后一个元素的索引

Collection如何迭代，四种方式迭代Collection

1、通过普通for 循环迭代
2、通过增强for 循环迭代
3、使用Iterator 迭代
4、使用Stream 迭代

四种方式迭代Collection

整个集合框架分为两个门派/四种抽象集合类型

Collection（顶层接口Collection）

Collection接口是什么？

集合类的顶层接口

一个顶层接口

Collection 是一个集合接口。

Collection是集合类的上级接口，

是集合List、Set、Queue的父接口

继承它的主要有Set、List、Queue

集合List、Set、Queue的最基本的接口

是List，Set 、Queue等的父接口。

List，Set 、Queue都是继承自Collection 接口。

(注意：这里不包括Map)

提供了所有集合（不包括Map）的通用方法

添加方法

add (Ee)

addAll(Collection <?extends E> var1)

删除方法

remove(Object var1)

remove All(Collection<?>var1)

查找方法

contains(Object var1)

contains All(Collection<?> var1)

查询集合自身信息

size（）

isEmpty（）

它提供了对集合对象进行基本操作的通用接口方法。

定义集合的约定

Collection 接口在Java 类库中有很多具体的实现。

都是用来存储一组相同类型的元素的。

一个容器，存储一系列的对象

图解Collection接口包含什么？

Collection接口包含什么？

Collection接口各集合总结： (以JDK 1.8为例）

Collection的三大接口

List接口

什么是List接口

List接口直接继承Collection接口

一个顶层接口

它继承了 Collection接口

Java的List是非常常用的数据类型。

List接口和Set接口齐头并进，是日常开发中接触的很多的一种集合类型了

同时也是ArrayList、LinkedList等集合元素的父类

可重复且有序集合

List是有序的Collection

List内部存储一系列可重复的对象，是一个有序集合，对象按插入顺序排列

它定义为可以存储重复元素的集合，并且元素按照插入顺序有序排列，且可以通过索引访问指定位置的元素。

一个可存储重复元素的有序集合

List 特点：元素有放入顺序，元素可重复。有顺序，即先放入的元素排在前面。

Java中List一共三个实现类：（常见的实现）

ArrayList

Vector和Stack

LinkedList

List 主要有ArrayList、LinkedList 与Vector 几种实现。

整个List集合的组成如下图

List集合的组成

List的继承关系

两个顶级抽象类

AbstractList抽象类

Abstract List抽象类实现了List接口

其内部实现了所有的List都需具备的功能

举例

子类可以专注于实现自己具体的操作逻辑。

AbstractSequentialList抽象类

继承了Abstract List，在原基础上限制了访问元素的顺序只能够按照顺序访问，而不支持随机访问

如果需要满足随机访问的特性，则继承Abstract List

子类LinkedList使用链表实现，所以仅能支持顺序访问，顾继承了AbstractSequentialList，而不是AbstractList

ArrayList（动态数组+查询快+增删慢）

ArrayList是最常用的List实现类

底层实现

数组

动态数组

基于数组实现的

内部是通过数组实现的

一个可改变大小的数组

它的内部是基于数组实现的

ArrayList以数组作为存储结构

ArrayList是实现了 List接口的可扩容数组(动态数组)

当更多的元素加入到ArrayList 中时,其大小将会动态地增长

ArrayList的容量，这个数组的容量就是List用来存储元素的容量。

适合随机查找和遍历，不适合插入和删除

查询快、增删慢

ArrayList可以实现所有可选择的列表操作，允许所有的元素，包括空值。

ArrayList还提供了内部存储list的方法

具有查询快、在数组中间或头部增删慢的特点

它允许对元素进行快速随机访问

内部的元素可以直接通过get 与set 方法进行访问，因为ArrayList 本质上就是一个数组。

能够实现随机存取

实现了RandomAccess接口

查找访问速度快增删效率低线程不安全

数组的缺点是每个元素之间不能有间隔，

当数组大小不满足时需要增加存储能力，就要将已经有数组的数据复制到新的存储空间中。

当从ArrayList的中间位置插入或者删除元素时，需要对数组进行复制、移动、代价比较高。

因此，它适合随机查找和遍历，不适合插入和删除。

图解ArrayList

线程不安全的集合/容器

它除了线程不安全这一点，其余可以替代Vector，而且线程安全的ArrayList，可以使用CopyOnWrite ArrayList代替Vector。

ArrayList能够完全替代Vector，只有一点例外，ArrayList不是线程安全的容器。

ArrayList不是线程安全的容器

如果多个线程中至少有两个线程修改了 ArrayList的结构的话就会导致线程安全问题

作为替代条件可以使用线程安全的List，应使用Collections.synchronizedList

List list = Collections.synchronizedList(new ArrayList(...))

fail-fast快速失败机制

ArrayList具有fail-fast快速失败机制，能够对ArrayList作出失败检测。

在使用迭代器遍历list时，如果modCount和expectedCount不匹配，就会直接抛出异常

即抛出ConcurrentModificationException 异常。

modCount在AbstractList中定义

使用迭代器自带的remove()函数时，如果删除了list中元素，不会出现fail-fast，因为迭代器会调整modCount和expectedCount值

当在迭代集合的过程中，该集合在结构上发生改变时，就有可能会发生fail-fast

具体定义如下

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {...}

自定义了序列化方法

因为arrayList的底层数组中，可能存在值为null的元素，序列化这些元素是没有意义的，因此自定义了序列化方法，只序列化数组中非null的元素

通过readObject()和writeObject()方法实现

关于ArrayList的扩容（源码实现）

关于ArrayList的扩容的注意事项

注意: 默认情况下ArrayList 的初始容量非常小,

所以如果可以预估数据量的话，分配一个较大的初始值属于最佳实践，这样可以减少调整大小的开销。

ArrayList 自动扩大容量为原来的1.5 倍

ArrayList扩容后的数组长度会增加50%

ArrayList首次扩容后的长度为10

ArrayList首次扩容后的长度为10，

调用add() 时需要计算容器的最小容量，可以看到如果数组element Data为空数组，会将最小容量设置为10，之后会将数组长度完成首次扩容到10。

集合从第二次扩容开始，数组长度将扩容为原来的1.5倍

即：new Length-old Length*1.5

集合从第二次扩容开始，数组长度将扩容为原来的1.5倍

扩容：capacity=1.5*capacity

通过Arrays.copyOf()

System.copyOf()

每次扩容的时候，都会传入一个minCapacity,即扩容之后的数组长度，对于add方法，是原size+1,对于addAll方法，是size+newSize,如果原数组长度*1.5仍不能存放所需的元素，那么就会直接令数组长度为minCapacity

ArrayList是插入前扩容,扩容逻辑为 ensureCapacityInternal()--->ensureExplicitCapacity()---->grow()

ArrayList 是１.5 倍.

ArrayList: int newCapacity = oldCapacity +(oldCapacity >> 1);

（实现时，方法会传入一个期望的最小容量，若扩容后容量仍然小于最小容量，那么容量就为传入的最小容量。

扩容时，使用的Arrays.copyOf 方法最终调用native 方法进行新数组创建和数据拷贝）。

Vector 缺省情况下增长原来一倍的数组长度，

Vector的扩容长度后数组会增加一倍。

Vector: int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);

Vector 指定了initialCapacity，capacityIncrement 来初始化时，每次增长capacityIncrement

ArrayList 使用了transient 关键字进行存储优化，而Vector 没有，为什么？

ArrayList 使用了transient 关键字进行存储优化，而Vector 没有这样做，为什么？

ArrayList 实现了writeObject 方法

ArrayList 实现了writeObject 方法，可以看到只保存了非null 的数组位置上的数据。即list 的size 个数的elementData。

需要额外注意的一点是，ArrayList 的实现，提供了fast-fail 机制，可以提供弱一致性。

Vector 也实现了writeObject 方法，但方法并没有进行优化存储

Vector 也实现了writeObject 方法，但方法并没有像ArrayList 一样进行优化存储，

实现语句是：

data = elementData.clone();

clone()的时候会把null 值也拷贝。所以保存相同内容的Vector 与ArrayList，Vector 的占用的字节比ArrayList 要多。

可以测试一下，序列化存储相同内容的Vector 与ArrayList，分别到一个文本文件中去。* Vector 需要243 字节* ArrayList 需要135 字节分析：

ArrayList

ArrayList 是非同步实现的一个单线程下较为高效的数据结构（相比Vector 来说）。

ArrayList 只通过一个修改记录字段提供弱一致性，主要用在迭代器里。

没有同步方法。即上面提到的Fast-fail 机制.

ArrayList 的存储结构定义为transient，重写writeObject来实现自定义的序列化，优化了存储。

Vector

Vector 是多线程环境下更为可靠的数据结构，所有方法都实现了同步。

区别

同步处理

Vector 同步，ArrayList 非同步

如何在遍历的同时删除ArrayList 中的元素

1、直接使用普通for 循环进行操作

不能在foreach 中进行，但是使用普通的for 循环还是可以的，

因为普通for循环并没有用到Iterator 的遍历，所以压根就没有进行fail-fast 的检验。

这种方案其实存在一个问题，那就是remove 操作会改变List 中元素的下标，可能存在漏删的情况。

2、直接使用Iterator 进行remove操作

直接使用Iterator 提供的remove 方法。

如果直接使用Iterator 提供的remove 方法，那么就可以修改到expectedModCount 的值。那么就不会再抛出异常了。

3、使用Java 8 中提供的filter 过滤

Java 8 中可以把集合转换成流，

对于流有一种filter 操作，可以对原始Stream 进行某项测试，通过测试的元素被留下来生成一个新Stream。

使用Java 8 中提供的filter 过滤

4、使用增强for 循环其实也可以删除ArrayList的元素

非常确定在一个集合中，某个即将删除的元素只包含一个的话

比如对Set 进行操作，那么其实也是可以使用增强for 循环的，

只要在删除之后，立刻结束循环体，不要再继续进行遍历就可以了

也就是说，不让代码执行到下一次的next 方法。

子主题

5、直接使用fail-safe 的集合类

在Java 中，除了一些普通的集合类以外，还有一些采用了fail-safe 机制的集合类。

这样的集合容器在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。

由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发CME。

直接使用fail-safe 的集合类

基于拷贝内容的优点是避免了CME，但同样地，迭代器并不能访问到修改后的内容，

即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。

JUC包下的容器都是安全失败，可以在多线程下并发使用，并发修改。

ArrayList和数组（Array）的区别是什么？

ArrayList

不用定长度，会自动扩容。

只能包含对象类型的数据。

数组Array

需要定长，超过定下的长度会报数组越界。

可以包含基本类型和对象类型的数据

请说明ArrayList是否会越界？

ArrayList并发add()可能出现数组下标越界异常。

总结

具备随机访问特点，访问元素的效率较高

在频繁插入、删除集合元素的场景下，效率较低。

底层数据结构：使用数组作为存储结构，具备查找快、增删慢的特点

线程不安全的集合

LinkedList（链表+双向链表+增删快）

图解LinkedList

存储的每个节点称为一个Node,下图可以看到Node中保存了next和prev指针

item是该节点的值。在插入和删除时，时间复杂度都保持为0(1)

底层数据结构、底层实现

双端队列

使用双端链表实现，并且实现了Deque接口，使得LinkedList可以用作双端队列。

下图可以看到Node是集合中的元素，提供了前驱指针和后继指针，还提供了一系列操作头结点和尾结点的方法，具有双端队列的特性。

具有双端队列的特性

链表

链表是什么？

由若干个称作节点的对象组成的一种数据结构，

每个节点含有一个数据和下一个节点的引用。

双链表示意图

链表

LinkedList是用链表结构存储数据的

双向链表

LinkedList是一个双向链表，允许存储任何元素(包括null )。

LinkedList所有的操作都可以表现为双向性的

索引到链表的操作将遍历从头到尾，视哪个距离近为遍历顺序。

底层采用双向链表数据结构存储元素

它是以链表实现的集合

双向链表

提供了List接口中没有定义的方法，专门用于操作表头和表尾元素

可以当作堆栈、队列和双向队列使用。

双向链表

关于LinkedList一些特殊的特性

优势

增删快、查询慢

它不具备随机访问的特点

由于链表的内存地址非连续，所以它不具备随机访问的特点

增删快

它利用指针连接各个元素，所以插入、删除元素只需要操作指针，不需要移动元素

是一个双链表，在添加和删除元素时具有比ArrayList 更好的性能

当然,这些对比都是指数据量很大或者操作很频繁的情况下的对比

如果数据和运算量很小,那么对比将失去意义。

很适合数据的动态插入和删除

随机访问和遍历速度比较慢。

适合插入删除频繁的情况内部维护了链表的长度

适合插入删除多的场合

查找优化

LinkedList查找某个下标index的元素时做了优化，若index>(size/2) ，则从head往后查找，否则从tail开始往前查找

案例代码

LinkedList底层没有扩容机制，使用双向链表存储元素，所以插入和删除元素效率较高，适用于频繁操作元素的场景

LinkedList 还实现了Queue 接口,该接口比List 提供了更多的方法,包括offer(),peek(),poll()等。

劣势

LinkedList不具备随机访间的特点，查找某个元素只能从head或tail指针一个一个比较，所以查找中间的元素时效率很低

LinkedList在get 与set 方面弱于ArrayList。

当然,这些对比都是指数据量很大或者操作很频繁的情况下的对比

,如果数据和运算量很小,那么对比将失去意义。

非线程安全的集合

由于以双向链表作为数据结构，它是线程不安全的集合

注意这个实现也不是线程安全的

如果多个线程并发访问链表，并且至少其中的一个线程修改了链表的结构，那么这个链表必须进行外部加锁。

如果多个线程中至少有两个线程修改了 ArrayList的结构的话就会导致线程安全问题

作为替代条件可以使用线程安全的List，应使用Collections.synchronizedList

或者使用 List list = Collections.synchronizedList(new LinkedList(...))

常用api

add

offer

remove

JDK1.5之前，LinkedList类

JDK1.5之前没有泛型的LinkedList<E>类，可以用普通的LinkedList创建一个链表对象

如：LinkedList mylist=new LinkedList();

如果使用旧版本的LinkedList类，JDK1.5后续版本的编译器会给出警告信息，但程序仍能正确运行。

JDK1.5之后，LinkedList<E>泛型类

LinkedList<E>泛型类创建的对象以链表结构存储数据，

习惯上，称LinkedList类创建的对象为链表对象

例如

LinkedList<String> mylist=new LinkedList<String>();

创建一个空双链表。

实现List<E>泛型接口中的一些常用方法

public boolean add(E element)

向链表依次增加节点

向链表末尾添加一个新的节点，

该节点中的数据是参数elememt指定的数据。

add(E obj)

例如：
  list.add("你好");
    list.add("十一快乐");
    list.add("注意休息");

public void add(int index ,E element)

向链表的指定位置添加一个新的节点，

该节点中的数据是参数elememt指定的数据。

public void clear()

删除链表的所有节点，使当前链表成为空链表。

public E remove(int index)

删除指定位置上的节点。

public boolean remove(E element)

删除首次出现含有数据element的节点

public E get(int index)

得到链表中指定位置处节点中的数据。

本身新增加的一些常用方法

public void addFirst(E element)

向链表的头添加新节点，该节点中的数据是参数elememt指定的数据。

public void addLast(E element)

向链表的末尾添加新节点，该节点中的数据是参数elememt指定的数据。

public E getFirst()

得到链表中第一个节点中的数据。

public E getLast()

得到链表中最后一个节点中的数据。

public E removeFirst()

删除第一个节点，并返回这个节点中的数据。

使用Iterator对象遍历链表

当用户需要遍历集合中的对象时，应当使用该集合提供的迭代器，而不是让集合本身来遍历其中的对象。

由于迭代器遍历集合的方法在找到集合中的一个对象的同时，也得到待遍历的后继对象的引用，因此迭代器可以快速地遍历集合。

链表对象可以使用iterator()方法获取一个Iterator对象，

该对象就是针对当前链表的迭代器。

LinkedList和ArrayList的区别

数据结构不同

ArrayList是Array(动态数组)的数据结构
LinkedList是Link(链表)的数据结构。

效率不同

当随机访问List（get和set操作）时，ArrayList比LinkedList的效率更高，因为LinkedList是线性的数据存储方式，所以需要移动指针从前往后依次查找。
当对数据进行增加和删除的操作(add和remove操作)时，LinkedList比ArrayList的效率更高，因为ArrayList是数组，所以在其中进行增删操作时，会对操作点之后所有数据的下标索引造成影响，需要进行数据的移动。

自由性不同

rrayList自由性较低，因为它需要手动的设置固定大小的容量，但是它的使用比较方便，只需要创建，然后添加数据，通过调用下标进行使用；
而LinkedList自由性较高，能够动态的随数据量的变化而变化，但是它不便于使用。

主要控件开销不同

ArrayList主要控件开销在于需要在List列表预留一定空间；
而LinkedList主要控件开销在于需要存储结点信息以及结点指针信息。

Vector（数组实现、线程同步、性能低下的过气集合）

Vector集合的诞生

JDK 1.0时代， ArrayList还没诞生，大家都是使用Vector集合，

性能低下的过气集合

Vector在现在已经是一种过时的集合了，包括继承它的Stack集合也如此

它们被淘汰的原因都是因为性能低下。

在JDK 1.2时， Collection家族出现了，它提供了大量高性能、适用于不同场合的集合，

而Vector也是其中一员，但由于Vector在每个方法上都加了锁，

由于需要兼容许多老的项目，很难在此基础上优化Vector了，所以渐渐地也就被历史淘汰了。

Vector 和ArrayList 类似，但属于强同步类

为什么它的性能低下？

由于Vector的每个操作都被synchronized关键字修饰，它对内部的每个方法都简单粗暴的上锁，避免多线程引起的安全性问题

即使在线程安全的情况下，仍然进行无意义的加锁与释放锁，造成额外的性能开销，做了无用功，

直接造成的结果

访问元素的效率要远远低于ArrayList。低效

通常这种同步方式需要的开销比较大

线程安全的容器

ArrayList能够完全替代Vector，只有一点例外，ArrayList不是线程安全的容器。

访问Vector比访问ArrayList慢

它支持线程的同步，即某一时刻只有一个线程能够写Vector

避免多线程同时写而引起的不一致性，但实现同步需要很高的花费

Vector是一个线程安全的容器

现在，在线程安全的情况下，不需要选用Vector集合，取而代之的是ArrayList集合：

如果程序本身是线程安全的(thread-safe,没有在多个线程之间共享同一个集合/对象),那么使用ArrayList 会更好

在并发环境下，出现了CopyOnWriteArrayList， Vector完全被弃用了。

基于数组实现的

Vector与ArrayList一样，也是通过数组实现的

同ArrayList 一样，都是基于数组实现的

图解Vector

常用方法

关于Vector的扩容

还有一点在于扩容上，ArrayList扩容后的数组长度会增加50%

Vector的扩容长度后数组会增加一倍。

Vector 和ArrayList 在更多元素添加进来时会请求更大的空间。

Vector 每次请求其大小的双倍空间，而ArrayList 每次对size 增长50%。

SynchronizedList 和Vector 的区别

在多线程的场景中可以直接使用Vector类，也可使Collections .synchronizedList(List list)方法来返回一个线程安全的List。

Vector 是java.util 包中的一个类

SynchronizedList 是java.util.Collections 中的一个静态内部类。

那么，到底SynchronizedList 和Vector 有没有区别，为什么java api 要提供这两种线程安全的List 的实现方式呢？

首先，我们知道Vector 和Arraylist 都是List 的子类，他们底层的实现都是一样的。

所以这里比较如下两个list1 和list2 的区别：

List<String> list = new ArrayList<String>();
List list2 = Collections.synchronizedList(list);
Vector<String> list1 = new Vector<String>();

一、比较两个重要的方法add 以及remove 方法

add 方法

Vector add方法的实现：

synchronizedList add方法的实现：

这里，使用同步代码块的方式调用ArrayList 的add()方法

ArrayList 的add 方法内容如下：

从上面两段代码中发现有两处不同

1.Vector 使用同步方法实现，synchronizedList使用同步代码块实现。

2.两者的扩充数组容量方式不一样（两者的add 方法在扩容方面的差别，也就是ArrayList 和Vector 的差别。）

remove 方法

synchronizedList 的remove方法实现：

ArrayList 类的remove 方法内容如下：

Vector 的remove方法实现：

从remove 方法中发现，除了一个使用同步方法，一个使用同步代码块之外几乎无任何区别。

通过比较其他方法发现，

SynchronizedList 里面实现的方法几乎都是使用同步代码块包上List 的方法。

如果该List 是ArrayList，那么SynchronizedList 和Vector的一个比较明显区别就是一个使用了同步代码块，一个使用了同步方法。

二、区别分析：SynchronizedList 和Vector 的区别目前为止有两点

数据增长（扩容机制）区别

1.如果使用add 方法，那么他们的扩容机制不一样。

从内部实现机制来讲，ArrayList 和Vector 都是使用数组(Array)来控制集合中的对象。

当向这两种类型中增加元素时，如果元素的数目超出了内部数组目前的长度它们都需要扩展内部数组的长度

Vector 缺省情况下自动增长原来一倍的数组长度

ArrayList 是原来的50%，所以最后获得的这个集合所占的空间总是比你实际需要的要大

所以如果要在集合中保存大量的数据，那么使用Vector有一些优势，因为通过设置集合的初始化大小来避免不必要的资源开销。

同步代码块和同步方法的区别

锁的范围

同步代码块在锁定的范围上，可能比同步方法要小

一般来说，锁的范围大小和性能是成反比的

锁的作用域

同步代码块可以更加精确的控制锁的作用域

同步方法的锁的作用域就是整个方法

（锁的作用域就是从锁被获取到其被释放的时间）

在锁定范围和锁的作用域上两者并无却别。

因为SynchronizedList 只是使用同步代码块包裹了ArrayList 的方法

而ArrayList和Vector 中同名方法的方法体内容并无太大差异

对象加锁

静态代码块可以选择对哪个对象加锁

但是静态方法只能给this 对象加锁。

在锁定的对象区别上

SynchronizedList 可以指定锁定的对象。

SynchronizedList 的同步代码块锁定的是mutex 对象，

那么mutex 对象又是什么呢？

其实SynchronizedList 有一个构造函数，可以传入一个Object,

如果在调用时，显示的传入一个对象，那么锁定的就是用户传入的对象。

如果没有指定，那么锁定的也是this 对象。

Vector 锁定的是this 对象。

使用SynchronizedList遍历时，要手动加锁

SynchronizedList 中实现的类，并没有都使用synchronized同步代码块。

其中有listIterator 和listIterator(int index)并没有做同步处理。

但是Vector 却对该方法加了方法锁。

将已有的LinkedList 直接转成SynchronizedList

之前的比较都是基于我们将ArrayList 转成SynchronizedList。

那么如果想把LinkedList 变成线程安全的，或者说想要方便在中间插入和删除的同步的链表，

那么可以将已有的LinkedList 直接转成SynchronizedList，而不用改变他的底层数据结构。

而这一点是Vector 无法做到的，因为他的底层结构就是使用数组实现的，这个是无法更改的。

总结，SynchronizedList 和Vector 最主要的区别：

SynchronizedList 有很好的扩展和兼容功能。它可以将所有的List 的子类转成线程安全的类。

使用SynchronizedList时，进行遍历时，要手动进行同步处理。

SynchronizedList 可以指定锁定的对象。

Stack堆栈

Stack

后入先出(吃了吐)的容器。

Stack是一种后入先出(LIFO) 型的集合容器，

第一次创建栈，不包含任何元素。

Stack<E>泛型类创建一个堆栈对象

堆栈

堆栈是一种“后进先出”的数据结构，

只能在一端进行输入或输出数据的操作。

堆栈对象常用方法

public E push(E item);实现压栈操作

public E pop();实现弹栈操作。

public boolean empty();判断堆栈是否还有数据。

public E peek();获取堆栈顶端的数据，但不删除该数据。

public int search(Object data);获取数据在堆栈中的位置。

Stack继承了Vector类

由于继承了Vector，正所谓跟错老大没福报， Stack也渐渐被淘汰了。

它继承了 Vector类，提供了以下方法

通常用的栈顶的压入元素操作(push) 和弹出元素操作(pop)

在栈顶的peek方法，测试stack是否为空的empty方法（查看栈顶元素的方法）

寻找与栈顶距离的search 方法

图解Stack堆栈

图解Stack堆栈，如图中所示，大雄是最后一个进入容器的， top指针指向大雄，那么弹出元素时，大雄也是第一个被弹出去的。

应该优先选择使用ArrayDeque实现栈

Deque<Integer> stack = new ArrayDeque<Integer>()

Set接口

什么是Set接口

学习Set前，最好最好要先学习Map，因为Set的操作本质上是对Map的操作

Set接口继承了Collection接口

位于与List接口同级的层次上

同时也继承了 Collection接口

一个不包括重复元素的集合

Set中任意两个元素不会出现o1.equals(o2)

Set注重独一无二的性质，该体系集合用于存储无序(存入和取出的顺序不一定相同)元素，值不能重复。

一个不允许存储重复元素的无序集合

最大作用就是判重，在项目中最大的作用也是别重!

Set至多只能存储一个NULL值元素

Set内部存储一系列不可重复的对象

存入可变元素时，必须非常小心，

因为任意时候元素状态的改变都有可能使得Set内部出现两个相等的元素，即o1.equals(o2) =true

一般不要更改存入Set中的元素，否则将会破坏了equals()的作用!

Set 特点：元素不可重复。

不可重复，即相同元素在set 中只会保留一份。

有些场景下，set 可以用来去重。

set 在元素插入时是要有一定的方法来判断元素是否重复的。

这个方法很重要，决定了set 中可以保存哪些元素。

一个无序集合

Set 特点：元素无放入顺序

无顺序，即先放入的元素不一定排在前面。

一个无序集合，对象排列顺序不一

一个不允许存储重复元素的无序集合

Set接口提供了额外的规定

它对add、equals, hashCode方法提供了额外的标准。

对象的相等性本质是对象hashCode值判断的，（java是依据对象的内存地址计算出的此序号hashCode值）

如果想要让两个不同的对象视为相等的，就必须覆盖Object的hashCode方法和equals方法。

图解Set接口

图解Set的继承关系

它的实现类和子类

AbstractSet抽象类

一个实现Set的一个抽象类

定义在这里，可以将所有具体Set集合的相同行为在这里实现，避免子类包含大量的重复代码

所有的Set也应该要有相同的hashCode()和equals() 方法，所以使用抽象类把该方法重写后，子类无需关心这两个方法。

源码

使用抽象类把该方法重写后，子类无需关心这两个方法

SortedSet接口

SortedSet是一个接口

直接继承于Set接口

它在Set的基础上扩展了排序的行为，所以所有实现它的子类都会拥有排序功能。

使用Comparable对元素进行自然排序或者使用Comparator在创建时对元素提供定制的排序规则。

set的迭代器将按升序元素顺序遍历集合。

SortedSet接口源码

HashSet类（HashMap+哈希表）

Set接口的实现类

底层实现、底层数据结构

基于HashMap实现

哈希表（Hash表）

HashSet（Hash表）

由哈希表支持

哈希表边存放的是哈希值

HashMap

底层借助HashMap实现

观察它的多个构造方法，本质上都是new一个HashMap

实际上，HashSet是HashMap的一个实例

这也是这篇文章为什么先讲解Map再讲解Set的原因

先学习Map，有助于理解Set

HashSet在HashMap基础上实现，所以很多地方可以联系到HashMap：

数组+链表+红黑树

HashSet也是采用数组+链表+红黑树实现

底层是数组+链表+红黑树

源码讲解

源码

可以观察add() 方法和remove() 方法是如何将HashSet的操作嫁接到HashMap的。

PRESENT

看到PRESENT就是一个静态常量：使用PRESENT作为HashMap的value值

使用HashSet的开发者只需关注于需要插入的key，屏蔽了HashMap的value

图解HashSet源码

上图可以观察到每个Entry的value都是PRESENT空对象，我们就不用再理会它了。

HashSet如何保证元素不重复?

是哈希表实现的

数据是无序的，可以放入null，但只能放入一个null

两者中的值都不能重复，就如数据库中唯一约束。

在HashSet 中，基本的操作都是有HashMap 底层实现的，

因为HashSet 底层是用HashMap 存储数据的。

HashSet依靠什么方法来区分重复元素？

hashCode() 和equals()方法

HashSet内部，使用Map保存数据，即将HashSet的数据作为Map的key值保存，这也是HashSet中元素不能重复的原因。

而Map中保存key值前，会去判断当前Map中是否含有该key对象，

内部是先通过key的hashCode，确定有相同的hashCode之后，再通过equals方法判断是否相同。

如果之类的hashCode()值相等，equals()也相等，就确定为相等，即重复元素。

HashSet的存储是无序的

哈希表（Hash表）

HashSet是由一个Hash表来实现的，因此，它的元素是无序的。

它不能保证集合的迭代顺序。这个类允许null元素。

存储元素顺序

并不是按照存入时的顺序（和List显然不同）

而是按照哈希值来存的，所以取数据也是按照哈希值取得。

先计算hashCode后存储

因为HashSet是根据对象的hashCode，进行计算后存储的

HashSet通过hashCode值，来确定元素在内存中的位置。

一个hashCode位置上，可以存放多个元素。

所有元素的value值都是一个static final Object

元素的哈希值是通过元素的hashcode方法来获取的

首先判断两个元素的哈希值，如果哈希值一样，接着会比较equals方法

如果 equls结果为true ，HashSet就视为同一个元素。如果equals 为false就不是同一个元素。

哈希值相同equals为false的元素是怎么存储呢？

就是在同样的哈希值下顺延（可以认为哈希值相同的元素放在一个哈希桶中）

也就是哈希一样的存一列。

图1表示hashCode值不相同的情况；

图2表示hashCode值相同，但equals不相同的情况。

图解HashSet

不是线程安全的集合

注意这个实现不是线程安全的

由于采用HashMap实现，而HashMap本身线程不安全

在HashSet中没有添加额外的同步策略，所以HashSet也线程不安全

如何保证线程安全

如果多线程并发访问HashSet，并且至少一个线程修改了set，必须进行外部加锁。

使用Collections.synchronizedSet()方法重写。

存入HashSet的对象的状态，最好不要发生变化

因为有可能改变状态后，在集合内部出现两个元索ol.equals(o2) ，破坏了equals()的语义

add()，remove()，contains()方法的时间复杂度是O(1)。

最后一个构造函数，为包访问权限是不对外公开，主要是为了支持LinkedHashSet

HashSet(int initialCapacity, float loadFactor, boolean dummy)

多了一个dummy变量

支持fail-fast机制

LinkedHashSet 类（LinkedHashMap+HashSet）

LinkedHashSet的继承体系

底层实现、底层数据结构

图解LinkedHashMap底层结构

LinkedHashSet（LinkedHashMap+HashSet）

LinkedHashSet 的实现上非常简单

LinkedHashSet的代码很少

对于LinkedHashSet而言，它继承与HashSet、又基于LinkedHashMap来实现的。

LinkedHashSet ->LinkedHashMap->HashMap+双向链表

LinkedHashSet是Set接口的Hash表和LinkedList的实现。

只提供了四个构造方法，并通过传递一个标识参数，调用父类的构造器

底层构造一个LinkedHashMap来实现，

LinkedHashMap

采用LinkedHashMap（双向链表的底层结构）

底层构造一个LinkedHashMap来实现，

底层使用LinkedHashMap来保存所有元素

发现父类中map的实现，采用LinkedHashMap

基于LinkHashMap实现（LinkedHashSet ->LinkedHashMap->HashMap+双向链表）

注意，不是HashMap，而是LinkedHashMap

采用HashMap+双向链表实现的

本质上，LinkedHashSet还是使用HashMap实现的

LinkedHashMap是采用HashMap和双向链表实现的

如果熟悉LinkedHashMap，那LinkedHashSet也就更不在话下了

HashSet

LinkedHashSet继承于HashSet，实现了Set接口

继承于HashSet，其所有的方法操作上又与HashSet相同

在相关操作上与父类HashSet的操作相同，直接调用父类HashSet的方法即可。

LinkedHashSet继承了HashSet，跟随到父类HashSet的构造方法看看

与HashSet的区别

双向链表的底层结构，按照元素的插入顺序遍历元素

所以LinkedHashSet可以按照元素的插入顺序遍历元素

注意：如果元素重新插入，则插入顺序不会受到影响。

这个实现不同于HashSet的是

LinkedHashMap是采用HashMap和双向链表实现的

这条双向链表中保存了元素的插入顺序。

此链表定义了元素插入集合的顺序。

LinkedHashSet ->LinkedHashMap->HashMap+双向链表

不是线程安全的

注意：LinkedHashSet也不是线程安全的

如果多线程同时访问LinkedHashSet，必须加锁

或者通过使用Collections.synchronizedSet

由于Linked HashMap不是线程安全的，且在Linked HashSet中没有添加额外的同步策略，所以
Linked HashSet集合也不是线程安全的

有两个影响其构成的参数

初始容量

选择过高的初始容量值的开销要比HashSet小

因为 LinkedHashSet的迭代次数不受容量影响。

加载因子

支持fail-fast机制

总结

它继承了HashSet，而HashSet默认是采用HashMap存储数据的

【额外注意】但是，LinkedHashSet调用父类构造方法初始化map时，是LinkedHashMap而不是HashMap

LinkedHashSet也不是线程安全的

TreeSet 类（TreeMap+数组+红黑树）

树集

TreeSet<E>泛型类

TreeSet<E>类创建的对象称作树集

例如：TreeSet<String> mytree=new TreeSet<String>();

基于TreeMap实现

TreeSet如何保证元素不重复?

是二叉树实现的

数据是自动排好序的，不允许放入null 值

TreeSet 的底层是TreeMap 的keySet()，

而TreeMap 是基于红黑树实现的

红黑树是一种平衡二叉查找树，它能保证任何一个节点的左右子树的高度差不会超过较矮的那棵的一倍。

TreeMap 是按key 排序的，元素在插入TreeSet 时compareTo()方法要被调用，所以TreeSet 中的元素要实现Comparable 接口。

TreeSet 作为一种Set，它不允许出现重复元素。

TreeSet 是用compareTo()来判断重复元素的。

add()时，value值都是一个static final Object对象,因此当key相等时就会覆盖，也实现了没有重复元素的问题

另一方面，TreeSet是由一个树形的结构来实现的，它里面的元素是有序的。因此，。

TreeSet()是使用二叉树的原理

TreeSet（二叉树）

对新add()的对象按照指定的顺序排序（升序、降序）

每增加一个对象都会进行排序，将对象插入的二叉树指定的位置。

Integer和String对象都可以进行默认的TreeSet排序，

而自定义类的对象是不可以的，自己定义的类必须实现Comparable接口，并且覆写相应的compareTo()函数，才可以正常使用。

在覆写compare()函数时，要返回相应的值才能使TreeSet按照一定的规则来排序

比较此对象与指定对象的顺序。如果该对象小于、等于或大于指定对象，则分别返回负整数、零或正整数。

节点的大小关系

树集用add方法添加节点，

节点会按其存放的数据的“大小”顺序，一层一层地依次排列，

在同一层中的节点，从左到右按“大小”顺序，递增排列，下一层的都比上一层的小。

树集

底层实现：数组+红黑树

基于TreeMap的NavigableSet实现。

基于TreeMap的实现，所以存储的元素是有序的，底层的数据结构是数组+红黑树。

底层的数据结构是数组+红黑树

元素的排列顺序有2种，和TreeMap相同

自然排序

常用的构造方法

自然排序的构造方法

这些元素使用他们的自然排序，或者在创建时提供的Comparator进行排序，具体取决于使用的构造函数。

定制排序

常用的构造方法

定制排序的构造函数

这些元素使用他们的自然排序，或者在创建时提供的Comparator进行排序，具体取决于使用的构造函数。

TreeSet应用场景

游戏里的玩家战斗力排行榜

代码示例

TreeSet类的常用方法

public boolean add(E o)

使用add方法为树集添加节点，

向树集添加加节点。

例如：mytree.add("boy");

public boolean remove(Object o)

删除树集中的存储参数指定的对象的最小节点

public void contains(Object o)

如果树集中有包含参数指定的对象

该方法返回true，否则返回false 。

public void clear()

删除树集中的所有节点。

public isEmpty()

判断是否是空树集

如果树集不含任何节点，该方法返回true

public int size()

返回树集中节点的数目

public E first()

返回树集中的第一个节点中的数据

（最小的节点）

public E last()

返回最后一个节点中的数据

（最大的节点）

提供了 log(n)的时间成本

此实现为基本操作add,remove和contains提供了 O(logn)的时间成本。

add()，remove()，contains()方法的时间复杂度是O(logn)

TreeSet的所有操作都会转换为对TreeMap的操作， TreeMap采用红黑树实现，任意操作的平均时间复杂度为0ClogN)

不是线程安全的

如果多线程并发访问TreeSet，并且至少一个线程修改了 set，必须进行外部加锁。

或者使用 SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...))

判断元素是否重复的方法

TreeSet判断元素是否重复的方法是判断compareTo()方法是否返回0

而不是调用hashcode() 和equals() 方法

如果返回0，则认为集合内已经存在相同的元素，不会再加入到集合当中。

支持fail-fast机制

总结

TreeSet的所有操作都会转换为对TreeMap的操作， TreeMap采用红黑树实现，任意操作的平均时间复杂度为0ClogN)

TreeSet是一个线程不安全的集合

TreeSet常应用于对不重复的元素定制排序，例如玩家战力排行榜

Queue接口

什么是Queue接口

Queue是一个队列容器，其特性与List相同，但只能从队头和队尾操作元素

Queue的设计用来在处理之前保持元素的访问次序。

一个可存储重复元素的队列

图解Queue

两种不同类型的集合实现

单向队列(AbstractQueue抽象类)

提供了各个API的基本实现，主要针对各个不同的处理策略给出基本的方法实现，

定义在这里的作用是让子类根据其方法规范(操作失败时抛出异常还是返回默认值)实现具体的业务逻辑。

API

AbstractQueue抽象类API

双端队列(Deque接口)：后起之秀Deque接口

取而代之的是后起之秀Deque接口

Deque接口的实现非常好理解：从单向队列演变为双向队列，内部额外提供双向队列的操作方法即可：

图解Deque的方法

Deque接口，额外提供了针对队列的头结点和尾结点操作的方法

而插入、删除方法，同样也提供了两套不同的失败策略

两种不同的失败处理策略

其实现有

ArrayDeque

LinkedList

LinkedList在上面已经详细解释了，

它实现了Deque接口，

提供了针对头结点和尾结点的操作，

并且每个结点都有前驱和后继指针，

具备了双向队列的所有特性。

提供了两套增加、删除元素的API

除了 Collection基础的操作之外，队列提供了额外的插入，读取，检查操作。

当插入或删除元素失败时，会有两种不同的失败处理策略。

两种不同的失败处理策略

选取哪种方法的决定因素：插入和删除元素失败时，希望抛出异常还是返回布尔值

add()和offer()对比

在队列长度大小确定的场景下，队列放满元素后，添加下一个元素时

add会抛出illegalStateException异常

offer会返回false

但是它们两个方法，在插入某些不合法的元素时，都会抛出三个相同的异常。

在插入某些不合法的元素时，都会抛出三个相同的异常

remove()和poll()对比

在队列为空的场景下

remove() 会抛出NoSuchElementException异常

而poll() 则返回null

get()和peek()对比

在队列为空的情况下

get()会抛出NoSuchElementException异常，

而peek()则返回null

PriorityQueue（优先级堆+数组）

PriorityQueue是AbstractQueue的实现类

PriorityQueue不允许null元素。

底层

基于优先级堆实现的优先级队列

优先级队列是无限制的，但具有内部capacity，用于控制用于在队列中存储元素的数组大小。

优先级队列的元素，根据自然排序或者通过在构造函数时期提供Comparator，来排序，具体根据构造器判断。

图解源码

该数组中的元素通过传入Comparator进行定制排序

如果不传入Comparator时，则按照元素本身自然排序，但要求元素实现了Comparable接口，所以PriortyQueue不允许存储NULL元素。

堆是采用数组实现

应用场景

元素本身具有优先级，需要按照优先级处理元素

例如：用户在请求人工客服需要排队时，根据用户的VIP等级进行插队处理

等级越高，越先安排客服，

例如：游戏中的VIP玩家与普通玩家， VIP等级越高的玩家越先安排进入服务器玩耍，减少玩家流失。

VIP等级越高的玩家越先安排进入服务器玩耍

执行上面的代码可以得到下面这种有趣的结果，可以看到充钱使人带来快乐。

不是线程安全的

注意这个实现不是线程安全的

多线程不应该并发访问PriorityQueue实例

如果有某个线程修改了队列，使用线程安全的类PriorityBlockingQueue

队列的头在某种意义上是指定顺序的最后一个元素。

队列查找操作poll,remove,peek和element 访问队列头部元素。

该类以及迭代器实现了 Collection、Iterator接口的所有可选方法。

这个迭代器提供了iterator()方法，不能保证以任何特定顺序，遍历优先级队列的元素。

如果你需要有序遍历，考虑使用 Arrays.sort(pq.toArray())

总结

PriorityQueue是基于优先级堆，实现的优先级队列，而堆是用数组维护的

PriorityQueue适用于元素按优先级处理的业务场景，

ArrayDeque

ArrayDeque在日常使用得不多

一个更完善，可靠性更强的LIFO栈操作，由Deque接口和他的实现提供

优点

该数据结构更加完善、可靠性更好

依靠队列也可以实现LIFO的栈操作

ArrayDeque作为栈时比Stack性能好，作为队列时比LinkedList性能好

应该优先选择使用ArrayDeque实现栈

Deque<Integer> stack = new ArrayDeque<Integer>()

它与LinkedList的对比

LinkedList

采用链表实现双端队列

Array Deque

ArrayDeque的数据结构：数组，并提供头尾指针下标对数组元素进行操作

使用数组实现的双端队列，它是无界的双端队列，

最小的容量是8(JDK 1.8) ， JDK 11，默认容量已经是16

最小的容量是8(JDK 1.8) ，在JDK 11看到它默认容量已经是16了。

由于双端队列只能在头部和尾部操作元素，所以删除元素和插入元素的时间复杂度大部分都稳定在0(1)，除非在扩容时会涉及到元素的批量复制操作，但是在大多数情况下，使用它时应该指定一个大概的数组长度，避免频繁的扩容。

链表的插入、除操作涉及到指针的操作，我个人认为作者是觉得数组下标的移动要比指针的操作要廉价，而且数组采用连续的内存地址空间，而链表元素的内存地址是不连续的，所以数组操作元素的效率在寻址上会比链表要快。请批判看待观点。

Map

Map接口是什么？

映射表的基础接口

由<key , value>组成的集合，由key映射到唯一的value，所以Map不能包含重复的key，每个键至多映射一个值。

定义了存储的数据结构是<key , value>形式，存储一系列的键值对<key， value>，一个支持key-value存储的对象

Map不能包含重复的key，每个键最多映射一个值。

根据key映射到value，一个key对应一个value，所以key不可重复，而value可重复。

查找元素时，通过key查找value

这个接口代替了 Dictionary类，Dictionary是一个抽象类，而不是接口。

Map的设计理念：定位元素的时间复杂度优化到0(1)

图解整个Map集合体系的主要组成部分

图解继承关系

将存储的方式细分为不同的种类

Map接口包含什么？

SortedMap接口

该类映射可以对<key， value>按照自己的规则进行排序

具体实现

TreeMap

AbstractMap抽象类

它为子类提供好一些通用的API实现

所有的具体Map都会继承它

具体实现

HashMap

Map接口通用方法

public V put(K key,V value)

将键/值对数据存放到散列映射中，该方法同时返回键所对应的值。

public void clear()

清空散列映射。

public Object clone()

返回当前散列映射的一个克隆。

public boolean containsKey(Object key)

如果散列映射有“键/值”对使用了参数指定的键，方法返回true，否则返回false。

public boolean containsValue(Object value)

如果散列映射有“键/值”对的值是参数指定的值。

public V get(Object key)

返回散列映射中使用key做键的“键/值”对中的值。

public boolean isEmpty()

如果散列映射不含任何“键/值”对，方法返回true，否则返回false。

public V remove(Object key)

删除散列映射中键为参数指定的“键/值”对，并返回键对应的值。

public int size()

返回散列映射的大小，即散列映射中“键/值”对的数目。

Map接口的实现类

HashMap（用数组+链表+红黑树三种数据结构实现）

散列映射

HashMap<K,V>泛型类

习惯上称HashMap<K,V>对象为散列映射

HashMap<K,V>对象，采用散列表这种数据结构存储数据

例如:

HashMap<String,Student> hashtable = HashSet<String,Student>();

hashtable可以存储“键/值”对数据。

集合是Java 开发日常开发中经常会使用到的，而作为一种典型的K-V 结构的数据结构，HashMap 对于Java 开发者一定不陌生。

在日常开发中，我们经常会像如下方式以下创建一个HashMap：

Map<String, String> map = new HashMap<String, String>();

并没有给HashMap 指定容量，那么，这时候一个新创建的HashMap 的默认容量是多少呢？

遍历散列映射

public Collection<V> values()

返回一个实现Collection<V>接口类创建的对象。

使用接口回调技术，即将该对象的引用赋给Collection<V>接口变量，

该接口变量可以回调iterator()方法获取一个Iterator对象，

这个Iterator对象存放着散列映射中所有“键/值”对中的“值”。

基于散列映射的查询

对于经常需要进行查找的数据可以采用散列映射来存储这样的数据，

即为数据指定一个查找它的关键字，然后按着“键-值”对，将关键字和数据一并存入散列映射中。

一个利用哈希表原理来存储元素的集合

一个最通用的，利用哈希表，存储元素的集合

将元素放入HashMap时，将key的哈希值转换为数组的索引下标，确定存放位置

查找时，根据key的哈希地址，转换成数组的索引下标，确定查找位置

HashMap根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。

只允许一条记录的键为null

最多只允许一条记录的键为null

允许多条记录的值为null

允许空的key-value键值对

非线程安全的集合

HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。

它是非线程安全的集合

也就是说在多线程的环境下，可能会存在问题

多线程可能出现的问题

1.扩容时可能出现死循环

2.put的时候可能被失效/覆盖

线程A,B同时调用addEntry方法，同时获取到了相同的头节点，

然后A写入新的头结点之后，B也写入新的头结点，

那B的写入操作就会覆盖A的写入操作造成A的写入操作丢失。

3.修改的时候可能被覆盖

线程A,B先后修改同一key值的value，会导致覆盖

4.put非null元素后get出来的却是null

扩容时调用的transfer方法，在获取数组的每个头节点的时候，在将e=头节点之后，都会将头节点置空，此时get可能导致获取到的值为0

如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。

可以使用 Collections.synchronizedMap(new HashMap(...))来构造一个线程安全的 HashMap。

Hashtable是线程安全的容器

支持fail-fast机制

底层实现、底层原理

1.7 数组+链表

数组+链表

头插

大方向上，HashMap 里面是一个数组，然后数组中每个元素是一个单向链表。

数组的优点是访问速度快，但是插入删除操作慢

因为数组在内存中是连续存放的，因此存取很快

链表的优点是插入删除速度快，但是访问速度慢

由于链表不是连续存放的，因此插入删除时，只需要修改前后指针的指向即可，不需要移动元素位置

Java 7 HashMap的结构

上图中，每个绿色的实体是嵌套类 Entry 的实例，

Entry 包含四个属性：key, value, hash 值和用于单向链表的 next。

capacity：当前数组容量，始终保持 2^n，可以扩容，扩容后数组大小为当前的 2 倍。

loadFactor：负载因子，默认为 0.75。loadFactor：负载因子，默认为 0.75。

threshold：扩容的阈值，等于 capacity * loadFactor

1.8 数组+链表+红黑树

诞生背景

根据 Java7 HashMap 的介绍，

查找时，根据 hash 值能够快速定位到数组的具体下标，

但是之后的话，需要顺着链表一个个比较下去才能找到需要的，时间复杂度取决于链表的长度，为 O(n)。

为了降低这部分的开销，在 Java8 中，

当链表中的元素超过了 8 个以后，会将链表转换为红黑树，

在这些位置进行查找时，可以降低时间复杂度为 O(logN)。

数组+链表+红黑树

HashMap（数组+链表+红黑树）

用数组+链表+红黑树，这三种数据结构实现

Java8 对 HashMap 进行了一些修改，最大的不同就是利用了红黑树，所以其由数组+链表+红黑树组成。

尾插

拉链法由头插法改为了尾插法

因为头插法在多线程的时候可能会导致死循环

链表长度大于8时，转化为红黑树

红黑树的时间复杂度为logn,线性表查找的平均时间复杂度为n/2,因此在链表长度为8时进行转化效率最高

红黑树的转化也是比较消耗性能的

链表个数超过8则链表转换成树结构，链表个数小于6则树结构转换成链表

2的幂次

方便位运算

均匀分布

重写equals必须重写HashCode

存取的时间复杂度为O(1)

Java 8 HashMap的结构

用数组+链表+红黑树，这三种数据结构实现

发送哈希冲突时， HashMap的解决方法是

将相同映射地址的元素连成一条链表

如果链表的长度大于8时，且数组的长度大于64，则会转换成红黑树数据结构。

源码分析

put()

1.判断key是否为null，如果为null，调用putlForNullKey，将key插入到数组下标为0的位置

2.调用hash()方法计算key的hashcode，得到hash值

3.调用indexFor()方法进行取模运算，得到元素的下标位置

1.indexFor方法为：h&(length - 1)

2.使用与运算，计算速度更快，因为二进制运算比十进制运算效率更高(十进制运算还需要将二进制转化为十进制)

3.length之所以要设定为2次幂，就是为了这个indexFor方法服务

4.可以让散列更加均匀，length-1的最后一位为1，因此进行与运算时，可以散列到奇数和偶数的下标位置，如果对length直接取模，由于length为2次幂，所以最后一位一定为0，所以与运算的结果一定是偶数，这也就导致奇数下标的位置不能被散列到。

4.依次和该下标位置上的链表中的node节点比较key是否相等

e.hash == hash && ((k = e.key) == key || key.equals(k))

首先判断e.hash==hash是因为不同的key值也可能被散列到同一个位置，因此首先判断hash值，如果不相等则两个key肯定不等

如果相等，再通过==和equals比较是否相等，之所以要先判断hash值是否相等，是因为equal()很耗性能，因此先判断hash值能够提高效率

重写了hashcode()方法就必须重写equals方法

5.如果相等，更新value值，如果不相等，使用头插法(1.7)/尾插法(1.8)将entry(1.7)/Node(1.8)插入到链表中

get()

和put()方法类似，获取到桶的下标，再在链表上查找key值，再获取key对应的value值

resize()

当hashmap中的元素个数超过数组大小*loadFactor时，就会进行数组扩容

扩容时，令 capacity 为原来的两倍。

1.7时，需要new 一个新数组，并对旧数组上的所有元素进行indexFor()操作确定下标地址,这一步很费时，1.8时只需判断hash值的左边新增的那一位是否为1，即可判断此节点是留在原地lo还是移动去高位hi,如果为1，则移动去高位，否则不变

1.7时，扩容的时候可能出现死循环，1.8没有这个问题

构造方法

在第一次put()的时候，数组才初始化

数组的长度为大于指定值的最小二次幂

数组默认大小为16

HashMap源码理解容量与扩容机制（有待进一步学习）

HashMap的实例有两个参数影响其性能

初始容量

加载因子

图解HashMap中主要的成员变量

上面是一张HashMap 中主要的成员变量的图

简单解释一下这些参数的含义，然后再分析他们的作用。

HashMap 类中有以下主要成员变量

size

transient int size

记录了Map 中KV 对的个数

HashMap 就像一个“桶”，而size 表示这个桶已经装了多少元素。

size 称之为Map 中的元素个数。

capacity

容量，如果不指定，默认容量是16

DEFAULT_INITIAL_CAPACITY。

(static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;)

HashMap 就像一个“桶”，那么capacity 就是这个桶“当前”最多可以装多少元素，

capacity 就是Map 的容量

loadFactor

装载因子，用来衡量HashMap 满的程度。

LoadFactory 默认0.75

DEFAULT_LOAD_FACTOR

loadFactor 的默认值为0.75f（static final float DEFAULT_LOAD_FACTOR = 0.75f;）。

threshold

int threshold

临界值，当实际KV 个数超过threshold 时，HashMap 会将容量扩容，threshold＝容量*装载因子

为什么HashMap 的默认容量设置成16 ？

图解HashMap

HashMap 就像一个“桶”，那么capacity 就是这个桶“当前”最多可以装多少元素，而size 表示这个桶已经装了多少元素。

HashMap 就是一个“桶”，那么容量（capacity）就是这个桶当前最多可以装多少元素，而元素个数（size）表示这个桶已经装了多少元素。

HashMap 的数据结构、什么是容量

Java中保存数据有两种简单的数据结构

数组

数组的特点是：寻址容易，插入和删除困难

链表

链表的特点是：寻址困难，插入和删除容易

图解链地址

从上图看到，左边很明显是个数组，数组的每个成员是一个链表。

该数据结构所容纳的所有元素均包含一个指针，用于元素间的链接。

根据元素的自身特征把元素分配到不同的链表中去，反过来也正是通过这些特征找到正确的链表，再从链表中找出正确的元素。

其中，根据元素特征计算元素数组下标的方法就是哈希算法，即本文的主角hash()函数（当然，还包括indexOf()函数）。

size 和capacity

来看下以下代码：

定义了一个新的HashMap，并想其中put 了一个元素，然后通过反射的方式打印capacity 和size。

输出结果为：capacity : 16、size : 1。

其容量是16，已经存放的元素个数是1。

一个HashMap 的容量（capacity）是16

当我们创建一个HashMap 的时候，如果没有指定其容量，那么会得到一个默认容量为16 的Map，

那么，这个容量是怎么来的呢？又为什么是这个数字呢？

默认情况下，一个HashMap 的容量（capacity）是16，

设计成16 的好处主要是可以使用按位与替代取模来提升hash 的效率。

为什么capacity 就是这个桶“当前”最多可以装多少元素呢？

HashMap 是具有扩容机制的。

HashMap 有扩容机制，就是当达到扩容条件时会进行扩容，从16扩容到32、64、128...

在一个HashMap 第一次初始化的时候，默认情况下他的容量是16

当达到扩容条件的时候，就需要进行扩容了，会从16 扩容成32。

通过构造函数指定了一个数字作为容量

HashMap 的重载的构造函数中，有一个是支持传入initialCapacity 的，那么我们尝试着设置一下，看结果如何。

分别执行以上3 段代码，分别输出：capacity : 2、capacity : 8、capacity : 16。

也就是说，默认情况下HashMap 的容量是16，

但是，如果用户通过构造函数指定了一个数字作为容量，那么Hash 会选择大于该数字的第一个2 的幂作为容量。(1->1、7->8、9->16)

初始化HashMap时，尽量指定其大小

在初始化HashMap 的时候，应该尽量指定其大小。

尤其是当你已知map 中存放的元素个数时。

（《Java 开发手册》）

容量与哈希

要想讲清楚这个默认容量的缘由，我们要首先要知道这个容量有什么用？

什么是容量

容量就是一个HashMap 中"桶"的个数，那么，

什么是哈希

当想要往一个HashMap 中put 一个元素时，需要通过一定的算法计算出应该把他放到哪个桶中，这个过程就叫做哈希（hash），

对应的就是HashMap 中的hash 方法。

Hash，一般翻译做“散列”，也有直接音译为“哈希”的，

就是把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。

这种转换是一种压缩映射，

散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。

简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

所有散列函数都有的基本特性

根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。

但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同。

图解hash哈希过程

hash方法的功能是根据Key 来定位这个K-V 在链表数组中的位置的。也
就是hash 方法的输入应该是个Object 类型的Key，输出应该是个int 类型的数组下标。
如果让你设计这个方法，你会怎么做？
其实简单，我们只要调用Object 对象的hashCode()方法，该方法会返回一个整数，
然后用这个数对HashMap 的容量进行取模就行了。
如果真的是这么简单的话，那HashMap 的容量设置就会简单很多了，但是考虑到效
率等问题，HashMap 的hash 方法实现还是有一定的复杂的。

常见的Hash 函数有以下几个

直接定址法：

直接以关键字k 或者k 加上某个常数（k+c）作为哈希地址。

数字分析法：

提取关键字中取值比较均匀的数字作为哈希地址。

除留余数法：

用关键字k 除以某个不大于哈希表长度m 的数p，将所得余数作为哈希表地址。

分段叠加法：

按照哈希表地址位数将关键字分成位数相等的几部分，其中最后一部分可以比较短。

然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。

平方取中法：

如果关键字各个部分分布都不均匀的话，可以先求出它的平方值，

然后按照需求取中间的几位作为哈希地址。

伪随机数法：

采用一个伪随机数当作哈希函数。

什么是碰撞

两个不同的输入值，根据同一散列函数计算出的散列值相同的现象叫做碰撞。

衡量一个哈希函数的好坏的重要指标

发生碰撞的概率

发生碰撞的解决方案

任何哈希函数基本都无法彻底避免碰撞

常见的解决碰撞的方法

开放定址法

开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。

链地址法

将哈希表的每个单元作为链表的头结点，所有哈希地址为i 的元素构成一个同义词链表。

即发生冲突时就把该关键字链在以该单元为头结点的链表的尾部。

再哈希法

当哈希地址发生冲突用其他的函数计算另一个哈希函数地址，直到冲突不再产生为止。

建立公共溢出区

将哈希表分为基本表和溢出表两部分，发生冲突的元素都放入溢出表中。

为什么建议设置HashMap 的初始容量？

要设置HashMap 的初始化容量

HashMap 有扩容机制，就是当达到扩容条件时会进行扩容。HashMap 的扩容条件
就是当HashMap 中的元素个数（size）超过临界值（threshold）时就会自动扩容。在
HashMap 中，threshold = loadFactor * capacity。

所以，如果我们没有设置初始容量大小，随着元素的不断增加，HashMap 会发生多
次扩容，而HashMap 中的扩容机制决定了每次扩容都需要重建hash 表，是非常影响性
能的。

所以，首先可以明确的是，建议开发者在创建HashMap 的时候指定初始化容量。
并且《Java 开发手册》中也是这么建议的：

《Java 开发手册》中也是这么建议

HashMap 初始化容量设置多少合适？

既然建议集合初始化时，要指定初始值大小，那么创建HashMap 时，到底指定多少合适呢？

case1

有些人会自然想到，我准备塞多少个元素我就设置成多少呗。比如我准备塞7 个元素，那就new HashMap(7)。

但是，这么做不仅不对，而且以上方式创建出来的Map 的容量也不是7。

JDK 会默认计算一个相对合理的值当做初始容量。

因为，使用HashMap(int initialCapacity)来初始化容量时，HashMap并不会使用传进来的initialCapacity 直接作为初识容量。

所谓合理值，其实是找到第一个比用户传入的值大的2 的幂。

当new HashMap(7)创建HashMap 时，JDK 会通过计算，创建一个容量为8 的Map；

当new HashMap(9)创建HashMap 时，JDK 会通过计算，创建一个容量为16 的Map。

考虑到loadFactor 这个因素并进行扩容

但是，这个值看似合理，实际上并不尽然。

因为HashMap 在根据用户传入的capacity 计算得到的默认容量

并没有考虑到loadFactor 这个因素，只是简单机械的计算出第一个大约这个数字的2 的幂。

loadFactor 是负载因子，

当HashMap 中的元素个数（size）超过threshold =loadFactor * capacity 时，就会进行扩容。

如果设置的默认值是7，经过JDK 处理之后，HashMap 的容量会被设置成8，

但是，这个HashMap 在元素个数达到8*0.75 = 6 时就会进行一次扩容，这明显是不希望见到的。

那么，到底设置成什么值比较合理呢？

通过expectedSize / 0.75F + 1.0F 计算

JDK8 中putAll 方法中的实现的，这个实现在guava（21.0 版本）也被采用。

这个值的计算方法就是：

return (int) ((float) expectedSize / 0.75F + 1.0F);

比如

计划向HashMap 中放入7 个元素时，通过expectedSize / 0.75F + 1.0F 计算，

7/0.75 + 1 = 10 ,10 经过JDK 处理之后，会被设置成16，这就大大的减少了扩容的几率。

当HashMap 内部维护的哈希表的容量达到75%时（默认情况下），会触发rehash，而rehash 的过程是比较耗费时间的。

所以初始化容量要设置成expectedSize/0.75 + 1的话，可以有效的减少冲突也可以减小误差。（大家结合这个公式，好好理解下这句话）

所以，可以认为，当明确知道HashMap 中元素的个数时，把默认容量设置成expectedSize / 0.75F + 1.0F 是一个在性能上相对好的选择

但是，同时也会牺牲些内存。

这个实现在guava（21.0 版本）也被采用

这个算法在guava中有实现，开发时，可以直接通过Maps类创建一个HashMap：

Map<String, String> map = Maps.newHashMapWithExpectedSize(7);

其代码实现如下：

子主题

这个值又设置成多少，真的有那么大影响吗？其实也不见得！

但是，以上的操作是一种用内存换性能的做法，真正使用时，要考虑到内存的影响。

但是，大多数情况下，还是认为内存是一种比较富裕的资源。

但是有些时候，底要不要设置HashMap 的初识值，这个值又设置成多少，真的有那么大影响吗？其实也不见得！

可是，大的性能优化，不就是一个一个的优化细节堆叠出来的吗？

再不济，以后你写代码时，使用Maps.newHashMapWithExpectedSize(7);的写法，也可以让同事和老板眼前一亮。

或者哪一天你碰到一个面试官问你一些细节时，你也能有个印象，或者某一天你也可以拿这个出去面试问其他人~！啊哈哈哈。

HashMap中hash 方法实现原理/源码解析

hash()方法的功能

拿JDK 1.7 的HashMap 为例，其中定义了一个final int hash(Object k) 方法，其主要被以下方法引用。

上面的方法主要都是增加和删除方法

这不难理解，当要对一个链表数组中的某个元素进行增删时，首先要知道他应该保存在这个链表数组中的哪个位置，即他在这个数组中的下标。

而hash()方法的功能就是根据Key 来定位其在HashMap 中的位置。HashTable、ConcurrentHashMap 同理。

简单分析hash 方法

hash 方法的功能是根据Key 来定位这个K-V 在链表数组中的位置的。

hash 方法的输入应该是个Object 类型的Key，输出应该是个int 类型的数组下标。

如果让你设计这个hash方法，你会怎么做？

只要调用Object 对象的hashCode()方法，该方法会返回一个整数，

然后用这个数对HashMap 或者HashTable 的容量进行取模就行了。

没错，其实基本原理就是这个

只不过，在具体实现上，由两个方法来实现

hash ：

int hash (Object k)

该方法主要是将Object 转换成一个整型。

indexFor ：

int indexFor(int h, int length)

该方法主要是将hash 生成的整型转换成链表数组中的下标。

static int indexFor(int h, int length) {
return h & (length-1);
}

但是考虑到效率等问题，HashMap 的实现会稍微复杂一点。

hash 方法的实现是不同的

在同一版本的Jdk 中，HashMap、HashTable 以及ConcurrentHashMap里面的hash 方法的实现是不同的。

在不同的版本的JDK 中（Java7 和Java8）中，HashMap、HashTable 以及ConcurrentHashMap里面的hash 方法的实现也是有区别的。

HashMap In Java 7

indexFor 方法

其实主要是将hash 生成的整型转换成链表数组中的下标。

那么return h & (length-1);是什么意思呢？其实，它就是取模。

位运算(&)效率要比代替取模运算(%)高很多，

Java 之所有使用位运算(&)来代替取模运算(%)，最主要的考虑就是效率。

主要原因是位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。

为什么可以使用位运算(&)来实现取模运算(%)呢？

这实现的原理如下：

X % 2^n = X & (2^n - 1)

2^n 表示2 的n 次方，

一个数对2^n 取模== 一个数和(2^n - 1)做按位与运算。

假设n 为3

则2^3 = 8，表示成2 进制就是1000

2^3 -1 = 7 ，即0111。

此时X & (2^3 - 1) 就相当于取X 的2 进制的最后三位数。

从2 进制角度来看，X / 8 相当于X >> 3，即把X 右移3 位，

此时得到了X / 8 的商，而被移掉的部分(后三位)，则是X % 8，也就是余数。

上面的解释不知道你有没有看懂，没看懂的话其实也没关系，你只需要记住这个技巧就可以了。

或者你可以找几个例子试一下。或者你可以找几个例子试一下。

6 % 8 = 6 ，6 & 7 = 6
10 & 8 = 2 ，10 & 7 = 2

子主题

所以，return h & (length-1);只要保证length 的长度是2^n 的话，就可以实现取模运算了。

而HashMap 中的length 也确实是2 的倍数，初始值是16，之后每次扩充为原来的2 倍。

无论是用取模运算还是位运算都无法直接解决冲突较大的问题。

比如：CA11 0000 和0001 0000 在对0000 1111 进行按位与运算后的值是相等的。

子主题

两个不同的键值，在对数组长度进行按位与运算后得到的结果相同，这不就发生了冲突吗。

那么如何解决这种冲突呢，来看下Java 是如何做的。

其中的主要代码部分如下：

h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);

这段代码是为了对key 的hashCode 进行扰动计算，防止不同hashCode 的高位不同但低位相同导致的hash 冲突。

简单点说，就是为了把高位的特征和低位的特征组合起来，降低哈希冲突的概率，

也就是说，尽量做到任何一位的变化都能对最终得到的结果产生影响。

举个例子来说

我们现在想向一个HashMap 中put 一个K-V 对，Key 的值为“hollischuang”，

经过简单的获取hashcode 后，得到的值为“1011000110101110011111010011011”，

如果当前HashTable 的大小为16，即在不进行扰动计算的情况下，他最终得到的index 结果值为11。

由于15 的二进制扩展到32 位为“00000000000000000000000000001111”，

所以，一个数字在和他进行按位与操作的时候，前28 位无论是什么，计算结果都一样（因为0 和任何数做与，结果都为0）。

如下图所示。

子主题

可以看到，后面的两个hashcode 经过位运算之后得到的值也是11 ，

虽然我们不知道哪个key 的hashcode 是上面例子中的那两个，但是肯定存在这样的key，这就产生了冲突。

那么，接下来，我看看一下经过扰动的算法最终的计算结果会如何。

子主题

从上面图中可以看到，之前会产生冲突的两个hashcode，经过扰动计算之后，最终
得到的index 的值不一样了，这就很好的避免了冲突。

其实，使用位运算代替取模运算，除了性能之外，还有一个好处就是可以很好的解决负数的问题。

因为hashcode 的结果是int 类型，而int 的取值范围是-2^31 ~ 2^31 - 1，即[ -2147483648, 2147483647]；

这里面是包含负数的，对于一个负数取模还是有些麻烦的。

如果使用二进制的位运算的话就可以很好的避免这个问题。

首先，不管hashcode 的值是正数还是负数。length-1 这个值一定是个正数。

那么，他的二进制的第一位一定是0（有符号数用最高位作为符号位，“0”代表“+”，“1”代表
“-”），这样里两个数做按位与运算之后，第一位一定是个0，也就是，得到的结果一定
是个正数。

HashTable In Java 7

上面是Java 7 中HashMap 的hash 方法以及indexOf 方法的实现，那么接下来我
们要看下，线程安全的HashTable 是如何实现的，和HashMap 有何不同，并试着分析
下不同的原因。以下是Java 7 中HashTable 的hash 方法的实现。

private int hash(Object k) {
// hashSeed will be zero if alternative hashing is disabled.
return hashSeed ^ k.hashCode();
}

我们可发现，很简单，相当于只是对k 做了个简单的hash，取了一下其hashCode。
而HashTable 中也没有indexOf 方法，取而代之的是这段代码：int index = (hash &
0x7FFFFFFF) % tab.length;。也就是说，HashMap 和HashTable 对于计算数组下
标这件事，采用了两种方法。HashMap 采用的是位运算，而HashTable 采用的是直接取
模。

为啥要把hash 值和0x7FFFFFFF 做一次按位与操作呢，主要是为了保证得到的
index 的第一位为0，也就是为了得到一个正数。因为有符号数第一位0 代表正数，1 代表
负数。

我们前面说过，HashMap 之所以不用取模的原因是为了提高效率。有人认为，因为
HashTable 是个线程安全的类，本来就慢，所以Java 并没有考虑效率问题，直接使用取
模算法了呢？但是其实并不完全是，Java 这样设计还是有一定的考虑在的，虽然这样效率
确实是会比HashMap 慢一些。

其实，HashTable 采用简单的取模是有一定的考虑在的。这就要涉及到HashTable
的构造函数和扩容函数了。由于篇幅有限，这里就不贴代码了，直接给出结论：

HashTable 默认的初始大小为11，之后每次扩充为原来的2n+1。

也就是说，HashTable 的链表数组的默认大小是一个素数、奇数。之后的每次扩充结
果也都是奇数。

由于HashTable 会尽量使用素数、奇数作为容量的大小。当哈希表的大小为素数时，
简单的取模哈希的结果会更加均匀。（这个是可以证明出来的，由于不是本文重点，暂不详
细介绍，可参考：http://zhaox.github.io/algorithm/2015/06/29/hash）

至此，我们看完了Java 7 中HashMap 和HashTable 中对于hash 的实现，我们
来做个简单的总结。

 HashMap 默认的初始化大小为16，之后每次扩充为原来的2 倍。
 HashTable 默认的初始大小为11，之后每次扩充为原来的2n+1。
 当哈希表的大小为素数时，简单的取模哈希的结果会更加均匀，所以单从这一
点上看，HashTable 的哈希表大小选择，似乎更高明些。因为hash 结果越分散
效果越好。

在取模计算时，如果模数是2 的幂，那么我们可以直接使用位运算来得到结
果，效率要大大高于做除法。所以从hash 计算的效率上，又是HashMap 更胜一
筹。
 但是，HashMap 为了提高效率使用位运算代替哈希，这又引入了哈希分布
不均匀的问题，所以HashMap 为解决这问题，又对hash 算法做了一些改进，进
行了扰动计算。在取模计算时，如果模数是2 的幂，那么我们可以直接使用位运算来得到结
果，效率要大大高于做除法。所以从hash 计算的效率上，又是HashMap 更胜一
筹。

ConcurrentHashMap In Java 7

上面这段关于ConcurrentHashMap 的hash 实现其实和HashMap 如出一辙。

（１）通过位运算代替取模

（２）然后再对hashcode进行扰动。

区别在于，ConcurrentHashMap 使用了一种变种的Wang/Jenkins 哈希算法，

其主要目的也是为了把高位和低位组合在一起，避免发生冲突。

至于为啥不和HashMap 采用同样的算法进行扰动，我猜这只是程序员自由意志的选择吧。

至少我目前没有办法证明哪个更优。

HashMap In Java 8

在Java 8 之前，HashMap 和其他基于map 的类都是通过链地址法解决冲突，它们
使用单向链表来存储相同索引值的元素。

在最坏的情况下，这种方式会将HashMap 的get 方法的性能从O(1)降低到O(n)。

为了解决在频繁冲突时hashmap 性能降低的问题，Java 8 中使用平衡树来替代链表存储冲突的元素。

这意味着我们可以将最坏情况下的性能从O(n)提高到O(logn)。

关于HashMap 在Java 8 中的优化，我后面会有文章继续深入介绍。

如果恶意程序知道用的是Hash 算法，则在纯链表情况下，它能够发送大量请求
导致哈希碰撞，然后不停访问这些key 导致HashMap 忙于进行线性查找，最终陷入瘫痪，
即形成了拒绝服务攻击（DoS）。

关于Java 8 中的hash 函数，原理和Java 7 中基本类似。

Java 8 中这一步做了优化，只做一次16 位右位移异或混合，而不是四次，但原理是不变的。

static final int hash(Object key) {
　　int h;
　　return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

在JDK1.8 的实现中，优化了高位运算的算法，通过hashCode()的高16 位异或低1
6 位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的。

以上方法得到的int 的hash 值，然后再通过h & (table.length -1)来得到该对象在数据
中保存的位置。

HashTable In Java 8

在Java 8 的HashTable 中，已经不在有hash 方法了。但是哈希的操作还是在的，
比如在put 方法中就有如下实现：

int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

这其实和Java 7 中的实现几乎无差别，就不做过多的介绍了。

ConcurrentHashMap In Java 8

Java 8 里面的求hash 的方法从hash 改为了spread。

实现方式如下：

static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}

Java 8 的ConcurrentHashMap 同样是通过Key 的哈希值与数组长度取模确定该Key 在数组中的索引。

同样为了避免不太好的Key 的hashCode 设计，它通过如下方法计算得到Key 的最终哈希值。

不同的是，Java 8 的ConcurrentHashMap 作者认为引入红黑树后，即使哈希冲突比较严重，寻址效率也足够高，

所以作者并未在哈希值的计算上做过多设计，只是将Key 的hashCode 值与其高16 位作异或并保证最高位为0（从而保证最终结果为正整数）。

总结

HashMap 的数据是存储在链表数组里面的。

在对HashMap 进行插入/删除等操作时，都需要根据K-V 对的键值定位到他应该保存在数组的哪个下标中。

而这个通过键值求取下标的操作就叫做哈希。

HashMap 的数组是有长度的，Java 中规定这个长度只能是2 的倍数，初始值为16。

简单的做法是先求取出键值的hashcode，然后在将hashcode 得到的int 值对数组长度进行取模。

为了考虑性能，Java 总采用按位与操作实现取模操作。

总结

HashMap 作为一种数据结构，元素在put 的过程中需要进行hash 运算，目的是计算出该元素存放在hashMap 中的具体位置。

hash 运算的过程其实就是对目标元素的Key 进行hashcode，再对Map 的容量进行
取模，而JDK 的工程师为了提升取模的效率，使用位运算代替了取模运算，这就要求
Map 的容量一定得是2 的幂。

而作为默认容量，太大和太小都不合适，所以16 就作为一个比较合适的经验值被采用了。

为了保证任何情况下Map 的容量都是2 的幂，HashMap 在两个地方都做了限制。

首先是，如果用户制定了初始容量，那么HashMap 会计算出比该数大的第一个2 的幂作为初始容量。

另外，在扩容时，也是进行成倍的扩容，即4 变成8，8 变成16。

总结

至此，我们已经分析完了HashMap、HashTable 以及ConcurrentHashMap 分别在Jdk 1.7 和Jdk 1.8 中的实现。

可以发现，为了保证哈希的结果可以分散、为了提高哈希的效率，JDK 在一个小小的hash 方法上就有很多考虑，做了很多事情。

当然，我希望我们不仅可以深入了解背后的原理，还要学会这种对代码精益求精的态度。

Jdk 的源代码，每一行都很有意思，都值得花时间去钻研、推敲。

loadFactor 和threshold

扩容条件指的是什么呢？

HashMap 的扩容条件就是当HashMap 中的元素个数（size）超过临界值（threshold）时就会自动扩容。

在HashMap 中，threshold = loadFactor * capacity。

loadFactor

装载因子，表示HashMap 满的程度

默认值为0.75f，设置成0.75有一个好处，那就是0.75 正好是3/4，而capacity 又是2 的幂。

所以，两个数的乘积都是整数。

对于一个默认的HashMap 来说，默认情况下，当其size 大于12(16*0.75)时就会触发扩容。

验证代码如下：

子主题

输出结果：

子主题

当HashMap 中的元素个数达到13 的时候，capacity 就从16 扩容到32 了。

HashMap 中还提供了一个支持传入initialCapacity,loadFactor 两个参数的方法，来初始化容量和装载因子。

不过，一般不建议修改loadFactor 的值。

创建一个空数组重新Hash

Hash公式跟长度有关

总结

HashMap 中

size 表示当前共有多少个KV 对，

capacity 表示当前HashMap 的容量是多少，默认值是16，每次扩容都是成倍的。

loadFactor 是装载因子，当Map 中元素个数超过loadFactor* capacity 的值时，会触发扩容。

loadFactor* capacity 可以用threshold 表示。

HashMap 初始化容量设置多少合适

总结

它是集合中最常用的Mop集合类型

底层由数组+链表+红黑树组成

HashMap不是线程安全的

插入元素时，通过计算元素的哈希值，通过哈希映射函数，转换为数组下标

查找元素时，同样通过哈希映射函数，得到数组下标，定位元素的位置

LinkedHashMap 类（HashMap和LinkedList的结合）

底层原理

LinkedHashMap是Map接口的哈希表和链表的实现。

底层是数组+链表+红黑树+双向链表

可以看作是HashMap和LinkedList的结合

这个实现与HashMap不同之处在于，它维护了一个贯穿其所有条目的双向链表。

它在HashMap的基础上添加，维护了一条双向链表，该链表存储了所有元素

双向链表

默认存储各个元素的插入顺序

这个链表定义了遍历顺序，通常是插入map中的顺序。

它提供一个特殊的LinkedHashMap(int,float,boolean)构造器来创建LinkedHashMap，其遍历顺序是其最后一次访问的顺序。

由于这条双向链表，使得LinkedHashMap可以实现LRU缓存淘汰策略，因为我们可以设置这条双向链表按照元素的访问次序进行排序

获取头结点与尾节点

图解底层原理

底层原理

维护链表顺序和访问顺序，记录插入顺序

LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，

在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。

它使用一个额外的双向链表来维护链表的访问顺序

Node节点额外增加了before和after指针，用于维护链表的访问顺序

next指针用来维护链表顺序

与HashMap的区别

HashMap的子类，具备HashMap的所有特点

它在HashMap的基础上维护了一条双向链表，该链表存储了所有元素

由于维护链表的额外开销，性能可能会低于HashMap，

这个类提供了所有可选择的map操作，并且允许null元素。

可以实现LRU缓存淘汰策略

利用LinkedHashMap可以实现LRU缓存淘汰策略

由于这条双向链表，使得LinkedHashMap可以实现LRU缓存淘汰策略，可以设置这条双向链表按照元素的访问次序进行排序

因为它提供了一个方法：removeEldestEntry

可以实现LRU缓存淘汰策略

该方法可以移除最靠近链表头部的一个节点

可以重写removeEldestEntry(Map.Entry)方法，以便在将新映射添加到map时，强制删除过期映射的策略。

原理

LinkedHashMap 可以通过构造参数 accessOrder 来指定双向链表是否在元素被访问后改变其在双向链表中的位置。

其原理是通过设置accessOrder为true，并重写removeEldestEntry方法，定义淘汰元素时，需满足的条件

当accessOrder为true时，get方法和put方法都会调用recordAccess方法使得最近使用的Entry移到双向链表的末尾；

当accessOrder为默认值false时，recordAccess方法什么也不会做。

LRU实现

插入数据后对调用afterNodeInsertion，afterNodeInsertion()方法中会调用removeEldestEntry，

如果removeEldestEntry(first)返回true，按照LRU策略，那么会删除头节点(注意这里删除的是头节点！！！

所以每次访问元素或者插入元素之后都要将该元素放到链表末尾)。

这个也是实现LRU的关键点！！！！！

实现一个LRU缓存策略，需要做两件事情

指定accessOrder=true

可以设定链表按照访问顺序排列，通过提供的构造器可以设定accessOrder

默认元素的顺序与插入顺序一致，

若accessOrder属性为true，则遍历顺序按元素的访问次序进行排序。

代码

重写removeEldestEntry()方法，内部定义逻辑

通常是判断容量是否达到上限

若是则执行淘汰

性能可能会低于HashMap

由于维护链表的额外开销，性能可能会低于HashMap，

有一条除外：遍历 LinkedHashMap 中的 collection-views 需要与 map.size 成正比，无论其容量如何。

HashMap的迭代看起来开销更大，因为还要求时间与其容量成正比。

有两个因素影响了它的构成

初始容量

加载因子

不是线程安全的

注意这个实现不是线程安全的。

如果多线程并发访问LinkedHashMap，并且至少一个线程修改了 map，必须进行外部加锁。

这通常通过在自然封装集合的某个对象上进行同步来实现Map m = Collections.synchronizedMap(new LinkedHashMap(...))

实现fail-fast机制

总结

它底层维护了一条双向链表，因为继承了HashMap，所以它也不是线程安全的

可以实现LRU缓存淘汰策略，其原理是通过设置accessOrder为true，并重写removeEldestEntry方法，定义淘汰元素时，需满足的条件

参考1：http://www.importnew.com/28263.html

参考2：http://www.importnew.com/20386.html#comment-648123

TreeMap 类（log(n)的红黑树与排序）

树映射

TreeMap<K,V>类实现了Map<K,V>接口，称TreeMap<K,V>对象为树映射。

树映射使用public V put(K key,V value);方法添加节点

底层原理

基于红黑树数据结构实现

TreeMap处处都是红黑树的身影!

它是基于红黑树数据结构实现的

底层实现为红黑树

一个基于NavigableMap实现的红黑树。

TreeMap是一个有序的key-value集合，基于红黑树实现。

能够保证树总是平衡的，如果插入删除导致树不平衡，会自动进行调整

变色

左旋

右旋

主要规则

1.每个节点或者是黑色，或者是红色。

2.根节点是黑色

3.叶子节点为黑色

4.如果一个节点是红色的，则它的子节点必须是黑色的

5.从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

图解TreeMap

红黑树的每一个节点都是一个Entry

Entry

包含了left，right，parent节点

每一个键值对<key， value>都是一个结点

注意，这些元素都是已经按照key排好序了，整个数据结构都是保持着有序的状态!

接口实现

NavigableMap

是SortedMap接口的子接口，

在其基础上扩展了一些方法，例如floorEntry，lowEntry,ceilingEntry等

为了防止外部修改Entry，使用了ExportEntry修饰floorEntry等方法

SortedMap

定义按照key排序的Map结构，能够令Map按照key的自然顺序或者构造器顺序进行排序。

TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，

TreeMap是SortedMap的子类，所以它具有排序功能

提供了 log(n)的时间开销

查找的平均时间复杂度为O(logN)

它底层是由红黑树这种数据结构实现的，所以操作的时间复杂度恒为0(LogN)

为 containsKey,get,put 和 remove 方法，提供了 log(n)的时间开销。

对key进行自然排序或者自定义排序

TreeMap（可排序）

当用Iterator遍历TreeMap时，得到的记录是排过序的。

如果使用排序的映射，建议使用TreeMap。

使用TreeMap时

定义按照key排序的Map结构，能够令Map按照key的自然顺序或者构造器顺序进行排序。

该映射根据其键的自然顺序进行排序，或者根据创建时提供的Comparator进行排序

key必须

实现Comparable接口（自然排序）

要求key必须实现Comparable接口

默认情况：自然排序

根据key自然排序存储

默认是按键值的升序排序

由于Integer类实现了Comparable接口，按照自然排序规则是按照key从小到大排序。

在构造TreeMap时，传入自定义Comparator（定制排序）

指定排序的比较器

通过传入定制的Comparator进行自定义规则排序

通过Comparator进行定制排序。

另一种：定制排序

在初始化TreeMap时，传入新的Comparator，不要求key实现Comparable接口

通过传入新的Comparator比较器，可以覆盖默认的排序规则

上面的代码，按照key降序排序，在实际应用中，还可以按照其它规则，自定义排序。

compare() 方法的返回值

返回0

代表两个元素相等，不需要调换顺序

返回+1

代表前面的元素需要与后面的元素调换位置

返回-1

代表前面的元素不需要与后面的元素调换位置

何时返回+1和-1，则自定义， JDK默认是按照自然排序，可以根据key的不同，去定义降序还是升序排序。

否则，会在运行时抛出java.lang.ClassCastException类型的异常。

参考：https://www.ibm.com/developerworks/cn/java/j-lo-tree/index.html

不是线程安全的

注意：这个实现不是线程安全的。

如果多线程并发访问TreeMap，并且至少一个线程修改了 map, 必须进行外部加锁。

这通常通过在自然封装集合的某个对象上进行同步来实现，

或者使用 SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...))

fail-fast机制

总结

它底层是由红黑树这种数据结构实现的，所以操作的时间复杂度恒为O(logN)

TreeMap可以对key进行自然排序或者自定义排序

自定义排序时，需传入Comparator

自然排序时，要求key实现Comparable接口

TreeMap不是线程安全的

WeakHashMap类（经常用作缓存）

底层原理

Weak HashMap底层存储的元素的数据结构是数组+链表，没有红黑树哦

为什么没有红黑树？

如果还有红黑树，那干脆直接继承HashMap，然后再扩展就完事了嘛，然而它并没有这样做：

public class WeakHashMap<K， V>extends AbstractMap<K,V>implements Map <K,V>{

WeakHashMap的数据结构图

图中，被虚线标识的元素，将会在下一次访问WeakHashMap时，被删除掉

WeakHashMap内部会做好一系列的调整工作

队列的作用就是标志那些已经被GC回收掉的元素。

基于哈希表的Map基础实现

基于哈希表的Map基础实现，带有弱键。

它是基于普通的Map实现的

基于map接口

是一种弱键相连

使用场景

日常开发中比较少见

经常用作缓存

WeakHashMap中的entry

里面Entry中的键在每一次的垃圾回收都会被清除掉

当不再使用时还会自动移除。

WeakHashMap里面的键会自动回收

更准确的说，给定key的映射的存在将不会阻止key被垃圾收集器丢弃。

非常适合用于短暂访问、仅访问一次的元素

缓存在Weak HashMap中，并尽早地把它回收掉

当Entry被GC时， Weak HashMap是如何感知到某个元素被回收的呢?

在Weak HashMap内部维护了一个引用队列queue

private final ReferenceQueue ＜Object>queue=new ReferenceQueue<>()

这个queue里包含了所有被GC掉的键，

当JVM开启GC后，如果回收掉Weak HashMap中的key，会将key放入queue中，

在expungeStaleEntries()中遍历queue，把queue中的所有key拿出来，并在WeakHashMap中删除掉，以达到同步

expungeStaleEntries()源码

支持null值和null键

fast-fail 机制

不允许重复

总结

它的键是一种弱键，放入WeakHashMap时，随时会被回收掉，所以不能确保某次访问元素一定存在

它依赖普通的Map进行实现，是一个非线程安全的集合

WeakHashMap通常作为缓存使用，适合存储那些只需访问一次、或只需保存短暂时间的键值对

HashTable类（因性能差的线性安全被弃用）

Hashtable类实现了一个哈希表，能够将键映射到值。任何非空对象都可以用作键或值。

底层的存储结构

底层的存储结构是数组+链表

这幅图是否有点眼熟哈哈哈哈，本质上就是Weak HashMap的底层存储结构了

HashTable底层采用数组+链表存储键值对，由于被弃用，后人也没有对它进行任何改进

HashTable本质上是HashMap的前辈

不建议在新代码中使用

HashTable（线程安全）

它是一个线程安全的集合，一个线程安全的Map，所有的操作都是线程安全的

与新的集合实现不同，Hashtable是线程安全的，但是因为这个线程安全，它就被淘汰掉了

它所有的方法都被加上了synchronized关键字，也是因为这个关键字，它注定成为了时代的弃儿。

它被淘汰的原因也主要因为两个字：性能

为什么Weak HashMap不继承Hashtable

Hashtable的性能在并发环境下非常差

在非并发环境下，可以用HashMap更优。

如果不需要线程安全的容器，推荐使用 HashMap

如果需要多线程高并发，推荐使用ConcurrentHashMap。

Hashtable是同步的，而HashMap不是。因此，HashMap更适合于单线程环境，而Hashtable适合于多线程环境。

HashTable是线程安全的，因为所有方法上都加了synchronized关键字。

不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable，

需要线程安全的场合可以用ConcurrentHashMap替换。

支持fail-fast机制

HashMap提供了可供应用迭代的键的集合，因此，HashMap是快速失败的。

HashMap是快速失败的

Hashtable提供了对键的列举(Enumeration)

Hashtable提供了对键的列举(Enumeration)。

Hashtable是遗留类

HashMap和Hashtable都实现了Map接口，因此很多特性非常相似。

很多映射的常用功能与HashMap类似

HashTable的key和value都不可以为null。

HashMap允许键和值是null，而Hashtable不允许键或者值是null。

不需要线程安全的场合可以用HashMap替换

并发性不高

并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。

HashTable的扩容机制

HashTable默认长度为11，

数组默认大小为11

扩容时，capacity=2*capacity+1

负载因子为0.75F，即元素个数达到数组长度的75%时，会进行一次扩容，每次扩容为原来数组长度的2倍

查找下标时，没有使用hash&length-1，而是直接进行计算的

HashMap 和HashTable 有何不同？

线程安全

HashTable 中的方法是同步的，在多线程并发的环境下，可以直接使用HashTable

HashMap 中的方法在默认情况下是非同步的。在多线程并发的环境下，要使用HashMap需自行增加同步处理。

继承关系

HashTable 是基于陈旧的Dictionary 类继承而来

HashMap 继承的抽象类AbstractMap 实现了Map 接口。

允不允许null 值

HashTable 中，key 和value 都不允许出现null 值，否则会抛出NullPointerException 异常。

HashMap 中，null 可以作为键，这样的键只有一个；可以有一个或多个键所对应的值为null。

默认初始容量和扩容机制

HashTable 中的hash 数组初始大小是11，增加的方式是old*2+1。

HashMap 中hash 数组的默认大小是16，而且一定是2 的指数。

哈希值的使用不同

HashTable 直接使用对象的hashCode。

HashMap 重新计算hash 值。

遍历方式的内部实现上不同

HashTable、HashMap 都使用了Iterator

而由于历史原因，HashTable还使用了Enumeration 的方式，

Hashtable 的Iterator 遍历支持fast-fail，用Enumeration 不支持fast-fail。

HashMap 实现Iterator，支持fast-fail，

常见问题

HashMap和HashTable有什么区别？

IdentityHashMap 类

比较小众的Map实现，这个类不是一个通用的Map实现

故意违反了 Map的约定

虽然这个类实现了 Map接口，但它故意违反了 Map的约定，

该约定要求在比较对象时，使用equals方法

仅适用于需要引用相等语义的极少数情况。

同HashMap, IdentityHashMap也是无序的

不是线程安全的

该类不是线程安全的，如果要使之线程安全

可以调用 Collections.synchronizedMap(new IdentityHashMap(...))方法来实现。

支持fail-fast机制

集合实现类特征图

下图汇总了部分集合框架的主要实现类的特征图，让你能有清晰明了看出每个实现类之间的差异性

集合实现类特征图

规律总结

排序

所有含有Hash字眼的集合类，都没有排序

随机访问

不支持的

LinkedList

Stack

TreeSet

其他都支持

key-value存储

所有的Map都是key-value存储

HashTable也是key-value存储

重复元素

除了List的子类，Stack，Vetor支持重复数据

空元素

所有含有Tree字眼的集合类，都不能有空元素

HashTable，ConcurrentHashMap不能有空元素

线程安全

基本上所有Collection集合全家桶都是非线程安全的

当然，也有例外

Vector

Stack

HashTable

四种抽象集合类型内部也会衍生出许多具有不同特性的集合类，不同场景下择优使用，没有最佳的集合

List接口

Set接口

Queue接口

Map接口

JDK为集合的各种操作提供了两个工具类

Collections工具类

是什么？

不属于Java集合框架继承树上的内容，它属于单独的分支

一个包装类

针对集合类的一个帮助类

就像一个工具类，服务于Java 的Collection 框架

作用

此类不能实例化

为集合框架提供某些功能实现

提供一系列静态方法实现对集合的各种操作，如sort()

此类只包括静态方法操作或者返回collections。

包含有各种有关集合操作的静态多态方法

同步包装

同步包装器

将自动同步(线程安全性)添加到任意集合。

六个核心集合接口都有一个静态工厂方法

Collection

List

Set

SortedSet

Map

SortedMap

六个核心集合接口都有一个静态工厂方法

不可修改的包装

不可修改的包装器

通过拦截，修改集合的操作，并抛出UnsupportedOperationException

使用场景

构建集合后，使其不可变

在这种情况下，最好不要去获取返回collection的引用

这样有利于保证不变性

允许某些客户端，以只读方式，访问你的数据结构

你保留对返回的collection的引用，但分发对包装器的引用。

通过这种方式，客户可以查看但不能修改，同时保持完全访问权限。

不可修改的包装方法列举

线程安全的Collections

Java1.5并发包(java.util.concurrent)提供了线程安全的collections

允许遍历时，进行修改，通过设计iterator为 fail-fast ，并抛出 ConcurrentModificationException。

一些实现类举例

ConcurrentHashMap

CopyOnWriteArrayList

CopyOnWriteArraySet

Collections 算法

此类包含用于集合框架算法的方法

例如二进制搜索，排序，重排，反向等

提供用于排序和查找的类方法

public static sort(List<E> list)

该方法可以将list中的元素升序排列

compareTo(E b)

实现Comparable<E>接口类创建的对象

可以调用compareTo(E b)方法和参数指定的对象比较大小关系。

Collections 的自定义排序没有正确判断if else引发的血案

Plm 30765 这个单号查询流程报错，请协助处理分析处理一下，谢谢

子主题

int binarySearch(List<T> list, T key)

使用折半法查找list是否含有和参数key相等的元素，

如果key链表中某个元素相等，方法返回和key相等的元素在链表中的索引位置（链表的索引位置从0开始），否则返回-1。

提供将链表中的数据重新随机排列的类方法

public static void shuffle(List<E> list)

将list中的数据按洗牌算法重新随机排列

提供旋转链表中数据的类方法

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

旋转链表中的数据

public static void reverse(List<E> list)

翻转list中的数据

强引用、弱引用、虚引用

Arrays工具类

是什么？

JDK 提供了一个工具类专门用来操作数组的工具类，即 Arrays

该 Arrays 工具类提供了大量的静态方法

应用场景

在实际项目开发中

推荐使用，这样既快捷又不会发生错误

在面试时

若出现对数组操作的题目，就决不允许使用 Arrays 类提供的方法，

因为面试官考察的是对数组的操作能力，而不是对 Arrays 类的应用。

常用方法

集合与数组互转

数组转集合

public static List asList(T… a)

返回由指定数组支持的固定大小的列表

import java.util.*;
import java.io.*;

public class Example{
   public static void main(String args[])
   throws IOException{
      int n = 5;         // 5 个元素
      String[] name = new String[n];
      for(int i = 0; i < n; i++){
         name[i] = String.valueOf(i);
      }
      List<String> list = Arrays.asList(name);
      System.out.println();
      for(String li: list){
         String str = li;
         System.out.print(str + " ");
      }
   }
}

集合转数组

public static String[] asArray(T… a)

import java.util.*;

public class Main{
   public static void main(String[] args){
      List<String> list = new ArrayList<String>();
      list.add("菜");
      list.add("鸟");
      list.add("教");
      list.add("程");
      list.add("www.runoob.com");
      String[] s1 = list.toArray(new String[0]);
      for(int i = 0; i < s1.length; ++i){
         String contents = s1[i];
         System.out.print(contents);
     }
   }
}

数组转换为字符串

public static String toString(int[] a)

返回指定数组的内容的字符串表示形式

在程序开发中，经常需要把数组以字符串的形式输出，可以使用 Arrays 工具类的 toString(int[] arr)，

需要注意的是，该方法并不是对 Object 类 toString() 方法的重写，只是用于返回指定数组的字符串形式。

import java.util.*;

public class Example {
    public static void main(String[] args){
        int[] arr = {9, 8, 3, 5, 2};
        String arrString = Arrays.toString(arr);
        System.out.println(arrString);
    }
}

注意： Arrays 类的 toString(int[] arr) 方法可将任意整数转为字符串。

提供用于排序和查找的类方法

public static void sort(int[] a)

按照数字顺序排列指定的数组

Arrays 工具类中的静态方法 sort() 可以对数组进行排序。

排序

import java.util.*;

public class Example {
    public static void main(String[] args){
        int[] arr = {9, 8, 3, 5, 2};     //初始化一个数组
        System.out.print("排序前：");
        printArray(arr);
        Arrays.sort(arr);
        System.out.print("排序后：");
        printArray(arr);
    }

    public static void printArray(int[] arr){   //定义打印数组方法
        System.out.print("[");
        for(int x=0; x<arr.length; x++){
            if(x != arr.length - 1){
                System.out.print(arr[x] + ",");
            } else {
               System.out.println(arr[x] + "]");
            }
        }
    }
}

public static int binarySearch(Object[] a, Object key)

查找元素

使用二叉搜索算法搜索指定对象的指定数组

Arrays 工具类中的静态方法 binarySearch(Object[] a, Object key) 用于查找元素。

import java.util.*;

public class Example {
    public static void main(String[] args){
        int[] arr = {9, 8, 3, 5, 2};     //初始化一个数组
        Arrays.sort(arr);
        int index = Arrays.binarySearch(arr, 3);
        //输出元素所在的索引位置
        System.out.println("数组排序后元素 3 的索引是：" + index);
    }
}

拷贝元素

public static int[] copyOfRange(int[] original, int from, int to)

将指定数组的指定范围复制到新数组中

在程序开发中，经常需要在不破坏原数组的情况下，使用数组中的部分元素

可以Arrays 工具类中的静态方法 copyOfRange(int[] original, int from, int to) 方法将数组中指定范围的元素复制到一个新的数组中。

copyOfRange(int[] original, int from, int to)方法参数说明如下：

参数 original 表示被复制的数组
参数 from 表示被复制元素的初始索引（包括）
参数 to 表示被复制元素的最后索引（不包括）

import java.util.*;

public class Example {
    public static void main(String[] args){
        int[] arr = {9, 8, 3, 5, 2};     //初始化一个数组
        int[] copied = Arrays.copyOfRange(arr, 1, 7);
        for(int i=0; i<copied.length; i++){
            System.out.print(copied[i] + " ");
        }
    }
}

填充元素

public static void fill(Object[] a, Object val)

程序开发中，经常需要用一个值替换数组中的所有元素，

将指定的对象引用分配给指定的对象数组的每个元素

使用 Array 的 fill(Object[] a, Object val) 方法，该方法可以将指定的值赋给数组中的每一个元素。

import java.util.*;

public class Example {
    public static void main(String[] args){
        int[] arr = {1, 2, 3, 4};     //初始化一个数组
        Arrays.fill(arr, 8);
        for(int i=0; i<arr.length; i++){
            System.out.println(i + ": " +arr[i]);
        }
    }
}

Arrays.asList 获得的List 使用时需要注意什么

1、asList 得到的只是一个Arrays 的内部类，一个原来数组的视图List，因此如果对它进行增删操作会报错。

2、用ArrayList 的构造器，可以将其转变成真正的ArrayList。

Apache 集合处理工具类的使用

Commons Collections作用

增强了Java Collections Framework

它提供了几个功能，使收集处理变得容易。

它提供了许多新的接口，实现和实用程序

Commons Collections主要功能

Bag

Bag 界面，简化了每个对象具有多个副本的集合。

Bag 定义了一个集合，用于计算对象在集合中出现的次数。

例如，如果Bag 包含{a，a，b，c}，则getCount（“a”）将返回2，而uniqueSet（）将返回唯一值。

子主题

它将打印以下结果：

BidiMap

BidiMap 接口，提供双向映射，可用于使用值使用键或键查找值。

使用双向映射，可以使用值查找键，并且可以使用键轻松查找值。

样例代码

子主题

它将打印以下结果：

子主题

MapIterator

JDK的Map接口很难迭代，因为迭代要在EntrySet 或KeySet对象上完成。

MapIterator 接口，提供简单而容易的迭代迭代。

MapIterator 提供了对Map 的简单迭代。

样例代码

它将打印以下结果：

Ordered Map

有序地图保留添加元素的顺序。

OrderedMap是地图的新接口，用于保留添加元素的顺序。LinkedMap 和ListOrderedMap 是两个可用的实现。

此接口支持Map 的迭代器，并允许在Map 中向前或向后迭代两个方向。

样例代码

子主题

它将打印以下结果：

子主题

Transforming Decorators

转换装饰器可以在将集合添加到集合时更改集合的每个对象。

Composite Collections

在需要统一处理多个集合的情况下使用复合集合。

Ordered Set

有序集保留了添加元素的顺序。

Reference map

参考图允许在密切控制下对键/值进行垃圾收集。

Comparator implementations

可以使用许多Comparator 实现。

Iterator implementations

许多Iterator 实现都可用。

Adapter Classes

适配器类可用于将数组和枚举转换为集合。

CollectionUtils 类（Utilities）

实用程序可用于测试测试或创建集合的典型集合论属性，

例如union，intersection。支持关闭。

Apache Commons Collections 库的CollectionUtils 类为常见操作提供了各种实用方法，涵盖了广泛的用例。

它有助于避免编写样板代码。

这个库在jdk 8 之前非常有用，因为Java 8 的Stream API 现在提供了类似的功能。

Ignore NULL 忽略空值

样例代码

子主题

它将打印以下结果：

[a]
Null value is not present

Safe Empty Checks 安全空检查

样例代码

子主题

它将打印以下结果：

子主题

Inclusion 检查列表是否是另一个列表的一部分

检查列表是否是另一个列表的一部分：

子主题

Intersection 获取两个集合（交集）之间的公共对象

用于获取两个集合（交集）之间的公共对象：

Subtraction 通过从其他集合中减去一个集合的对象来获取新集合

子主题

Union获取两个集合的并集

子主题

原文地址：

https://iowiki.com/commons_collections/commons_collections_index.html

常见面试题

通用

Java常用的集合有哪些？

java 容器都有哪些？

Java集合类框架的最佳实践有哪些？

根据应用的需要正确选择要使用的集合的类型对性能非常重要，比如：假如元素的大小是固定的，而且能事先知道，我们就应该用Array而不是ArrayList。

有些集合类允许指定初始容量。因此，如果我们能估计出存储的元素的数目，我们可以设置初始容量来避免重新计算hash值或者是扩容。

为了类型安全，可读性和健壮性的原因总是要使用泛型。同时，使用泛型还可以避免运行时的ClassCastException。

使用JDK提供的不变类(immutable class)作为Map的键可以避免为我们自己的类实现hashCode()和equals()方法。

编程的时候接口优于实现。

底层的集合实际上是空的情况下，返回长度是0的集合或者是数组，不要返回null。

Java集合类框架的基本接口有哪些？

集合类接口指定了一组叫做元素的对象。集合类接口的每一种具体的实现类都可以选择以它自己的方式对元素进行保存和排序。有的集合类允许重复的键，有些不允许。

Java集合类提供了一套设计良好的支持对一组对象进行操作的接口和类。Java集合类里面最基本的接口有：

Collection：代表一组对象，每一个对象都是它的子元素。
Set：不包含重复元素的Collection。
List：有顺序的collection，并且可以包含重复元素。
Map：可以把键(key)映射到值(value)的对象，键不能重复。

为什么集合类没有实现Cloneable和Serializable接口？

克隆(cloning)或者是序列化(serialization)的语义和含义是跟具体的实现相关的。因此，应该由集合类的具体实现来决定如何被克隆或者是序列化。

迭代器 Iterator 是什么？

Iterator 怎么使用？有什么特点？

Iterator 和 ListIterator 有什么区别？

快速失败(fail-fast)和安全失败(fail-safe)的区别是什么？

fail-fast机制和fail-safe机制的区别

Iterator的安全失败是基于对底层集合做拷贝，因此，它不受源集合上修改的影响。

java.util包下面的所有的集合类都是快速失败的

JUC包下面的所有的类都是安全失败的。

快速失败的迭代器会抛出ConcurrentModificationException异常，而安全失败的迭代器永远不会抛出这样的异常。

hashCode()和equals()方法的重要性体现在什么地方？

Java中的HashMap使用hashCode()和equals()方法来确定键值对的索引，当根据键获取值的时候也会用到这两个方法。

如果没有正确的实现这两个方法，两个不同的键可能会有相同的hash值，因此，可能会被集合认为是相等的。

而且，这两个方法也用来发现重复元素。所以这两个方法的实现对HashMap的精确性和正确性是至关重要的。

请解释hashCode()和equals()方法有什么联系？

相同的对象必须具有相等的Hash码

两个对象的Hash码相同，他们并不一定相同。

若不重写hashCode()的话，hashCode()如何计算？

该方法直接返回对象的地址。

如何权衡是使用无序的数组还是有序的数组？

有序数组最大的好处在于查找的时间复杂度是O(log n)，而无序数组是O(n)。有序数组的缺点是插入操作的时间复杂度是O(n)，因为值大的元素需要往后移动来给新元素腾位置。相反，无序数组的插入时间复杂度是常量O(1)。

哪些集合类是线程安全的？

怎么确保一个集合不能被修改？

Collection和Collections的区别

Collection是集合类的上级接口，继承他的主要有Set和List

Collections是针对集合类的一个帮助类，他提供一系列静态方法实现对集合的各种操作，如sort()

解释某个类底层的数据结构

请说说常用的集合类及方法？

最常用的集合类是List和Map。

List里最常用的就是ArrayList.他是可变长度的列表，

Map里最常用的就是HashMap，他按键值对进行存储，但HashMap线程不安全。

Map

HashMap和HashTable的区别+3

HashMap和Hashtable的区别

A：HashMap和Hashtable两个类都实现了Map接口，二者保存K-V对（key-value对）
B：HashTable不允许null值(key和value都不可以),HashMap允许null值(key和value都可以)。
C：Hashtable的方法是Synchronize的，而HashMap不是，在多个线程访问Hashtable时，不需要自己为它的方法实现同步，而HashMap 就必须为之提供外同步。
D：由所有HashMap类的“collection 视图方法”所返回的迭代器都是快速失败的：在迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器本身的 remove 方法，其他任何时间任何方式的修改，迭代器都将抛出ConcurrentModificationException。Hashtable和HashMap的区别主要是前者是同步的，后者是快速失败机制保证

HashMap和Hashtable

HashMap允许key和value是null，而HashTable不允许key或value是null。

HashTable（这是一个遗留类）是线程安全的，HashMap是线程不安全的。

Java中的HashMap的工作原理是什么？+2

Java中的HashMap是以键值对(key-value)的形式存储元素的。

HashMap需要一个hash函数，它使用hashCode()和equals()方法来向集合/从集合添加和检索元素。

当调用put()方法的时候，HashMap会计算key的hash值，然后把键值对存储在集合中合适的索引上。

如果key已经存在了，value会被更新成新值。

HashMap的一些重要的特性是它的容量(capacity)，负载因子(load factor)和扩容极限(threshold resizing)。

HashMap的数据结构？

JDK8中HashMap的新特性？

红黑树

HashMap的插入和获取过程

HashMap是线程安全的吗？

线程不安全

如果HashMap的可以是一个自定义的类，怎么办？

就必须重写hashCode()和equals()。

哈希冲突是什么？

HashMap的resize的过程

如何决定使用 HashMap 还是 TreeMap？

HashMap和ConcurrentHashMap的区别

Map有哪些？

Map是无序的吗？

HashMap是无序的

LinkedHashMap是有序的

TreeMap是按key排序的。

List、Set、Map是否继承自Collection接口？

List、Set是，Map不是。

Set和List的区别，List、Set、Map 之间的区别是什么？

Comparable和Comparator接口是干什么的？列出它们的区别。

Java提供了只包含一个compareTo()方法的Comparable接口。这个方法可以个给两个对象排序。具体来说，它返回负数，0，正数来表明输入对象小于，等于，大于已经存在的对象。

Java提供了包含compare()和equals()两个方法的Comparator接口。compare()方法用来给两个输入参数排序，返回负数，0，正数表明第一个参数是小于，等于，大于第二个参数。equals()方法需要一个对象作为参数，它用来决定输入参数是否和comparator相等。只有当输入参数也是一个comparator并且输入参数和当前comparator的排序结果是相同的时候，这个方法才返回true。

线程安全的Map在JDK1.5以及更高版本环境，有以下哪几种方式可以实现

HashMap,TreeMap 未进行同步考虑，是线程不安全的。

HashTable 和 ConcurrentHashMap 都是线程安全的。

区别在于：他们对加锁的范围不同，
HashTable 对整张Hash表进行加锁，
而ConcurrentHashMap将Hash表分为16桶(segment)，每次只对需要的桶进行加锁。

Collections 类提供了synchronizedXxx()方法，可以将指定的集合包装成线程同步的集合。比如，
List list = Collections.synchronizedList(new ArrayList());

Set set = Collections.synchronizedSet(new HashSet());

List

List你用过哪几种？

Java List一共三个实现类：

ArrayList

Vector

LinkedList

如何实现数组和 List 之间的转换？

List之间的去重与合并？

Java链表与数组的区别？

ArrayList 和 LinkedList 的区别是什么？

Array 和 ArrayList 有何区别？

ArrayList 和 Vector 的区别是什么？

数组(Array)和列表(ArrayList)有什么区别？什么时候应该使用Array而不是ArrayList？

下面列出了Array和ArrayList的不同点：

Array可以包含基本类型和对象类型，ArrayList只能包含对象类型。
Array大小是固定的，ArrayList的大小是动态变化的。
ArrayList提供了更多的方法和特性，比如：addAll()，removeAll()，iterator()等等。
对于基本类型数据，集合使用自动装箱来减少编码工作量。但是，当处理固定大小的基本数据类型的时候，这种方式相对比较慢。

聊一聊LinkedList底层实现（双向链接用于双端队列）

ArrayList和LinkedList的区别？ArrayList和LinkedList有什么区别？+3

ArrayList和LinkedList都实现了List接口，他们有以下的不同点：

ArrayList是基于索引的数据接口，它的底层是数组。它可以以O(1)时间复杂度对元素进行随机访问。与此对应，LinkedList是以元素列表的形式存储它的数据，每一个元素都和它的前一个和后一个元素链接在一起，在这种情况下，查找某个元素的时间复杂度是O(n)。
相对于ArrayList，LinkedList的插入，添加，删除操作速度更快，因为当元素被添加到集合任意位置的时候，不需要像数组那样重新计算大小或者是更新索引。
LinkedList比ArrayList更占内存，因为LinkedList为每一个节点存储了两个引用，一个指向前一个元素，一个指向下一个元素。
也可以参考ArrayList vs. LinkedList。

SynchronizedList和Vector的区别

ArrayList和Vector的区别

ArrayList源码解释

Set

说一下 HashSet 的实现原理？

HashSet和TreeSet有什么区别？

Set如何保证元素不重复

HashSet为什么禁止插入Key为NULL的元素

为什么重写equals()时必须重写hashCode()

HashSet依靠什么方法来区分重复元素？

hashCode() 和equals()方法

例题

HashSet内部，使用Map保存数据，即将HashSet的数据作为Map的key值保存，这也是HashSet中元素不能重复的原因。

而Map中保存key值前，会去判断当前Map中是否含有该key对象，

内部是先通过key的hashCode，确定有相同的hashCode之后，再通过equals方法判断是否相同。

如果之类的hashCode()值相等，equals()也相等，就确定为相等，即重复元素。

Queue

什么是Java优先级队列(Priority Queue)？

PriorityQueue是一个基于优先级堆的无界队列，它的元素是按照自然顺序(natural order)排序的。在创建的时候，我们可以给它提供一个负责给元素排序的比较器。PriorityQueue不允许null值，因为他们没有自然顺序，或者说他们没有任何的相关联的比较器。最后，PriorityQueue不是线程安全的，入队和出队的时间复杂度是O(log(n))。

在 Queue 中 poll()和 remove()有什么区别？

集合了解哪些队列

1.

2.

3.

子主题