前言

数据结构作为每一个开发者不可回避的问题,而 Java 对于不同的数据结构提供了非常成熟的实现,这一个又一个实现既是面试中的难点,也是工作中必不可少的工具,在此,笔者经历漫长的剖析,将其抽丝剥茧的呈现出来,在此仅作抛砖引玉,望得诸君高见,若君能有所获则在下甚是不亦乐乎,若有疑惑亦愿与诸君共求之!本文一共 3.5 W字,25 张图,预计阅读 2h。可以收藏这篇文章,用的时候防止找不到,这可能是你能看到的最详细的一篇文章了。整理了2021年Java面试题。

1、集合框架

Java整个集合框架如上图所示(这儿不包括Map,Map的结构将放在集合后边进行讲述),可见所有集合实现类的最顶层接口为Iterable和Collection接口,再向下Collection分为了三种不同的形式,分别是List,Queue和Set接口,然后就是对应的不同的实现方式。

1.1顶层接口Iterable

//支持lambda函数接口importjava.util.function.Consumer;publicinterfaceIterable{//iterator()方法Iteratoriterator();defaultvoidforEach(Consumer

2、List

List表示一串有序的集合,和Collection接口含义不同的是List突出有序的含义。

2.1 List接口

packagejava.util;importjava.util.function.UnaryOperator;publicinterfaceListextendsCollection{ T[] toArray(T[] a);booleanaddAll(Collection c);booleanaddAll(intindex, Collection c);defaultvoidreplaceAll(UnaryOperator operator){Objects.requireNonNull(operator);finalListIterator li =this.listIterator();while(li.hasNext()) {li.set(operator.apply(li.next()));}}defaultvoidsort(Comparator c){Object[] a =this.toArray();Arrays.sort(a, (Comparator) c);ListIterator i =this.listIterator();for(Object e : a) {i.next();i.set((E) e);}}booleanequals(Object o);Eget(intindex);Eset(intindex, E element);voidadd(intindex, E element);intindexOf(Object o);intlastIndexOf(Object o);ListIteratorlistIterator();ListsubList(intfromIndex,inttoIndex);@OverridedefaultSpliteratorspliterator(){returnSpliterators.spliterator(this, Spliterator.ORDERED);}}复制代码

可见List其实比Collection多了添加方法add和addAll查找方法get,indexOf,set等方法,并且支持index下标操作Collection 与 List 的区别?a. 从上边可以看出Collection和List最大的区别就是Collection是无序的,不支持索引操作,而List是有序的。Collection没有顺序的概念。b. List中Iterator为ListIterator。c. 由a推导List可以进行排序,所以List接口支持使用sort方法。d. 二者的Spliterator操作方式不一样。**为什么子类接口里重复申明父类接口呢?**官方解释: 在子接口中重复声明父接口是为了方便看文档。比如在 java doc 文档里,在 List 接口里也能看到 Collecion 声明的相关接口。

2.2 List实现ArrayList

ArrayList是List接口最常用的一个实现类,支持List接口的一些列操作。

2.2.1 ArrayList继承关系

2.2.2 ArrayList组成

privatestaticfinalObject[] EMPTY_ELEMENTDATA = {};privatestaticfinalObject[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}//真正存放元素的数组transientObject[] elementData;// non-private to simplify nested class accessprivateintsize;复制代码

一定要记住ArrayList中的transient Object[] elementData,该elementData是真正存放元素的容器,可见ArrayList是基于数组实现的。

2.2.3 ArrayList构造函数

>publicArrayList(intinitialCapacity){if(initialCapacity >0) {this.elementData =newObject[initialCapacity];}elseif(initialCapacity ==0) {this.elementData = EMPTY_ELEMENTDATA;}else{thrownewIllegalArgumentException("Illegal Capacity: "+initialCapacity);}}publicArrayList(){this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}复制代码
  1. Object[] elementData 是ArrayList真正存放数据的数组。
  2. ArrayList支持默认大小构造,和空构造,当空构造的时候存放数据的Object[] elementData是一个空数组{}。

2.2.4 ArrayList中添加元素

>publicbooleanadd(E e){ensureCapacityInternal(size +1);// Increments modCount!!elementData[size++] = e;returntrue;}复制代码

注意ArrayList中有一个modCount的属性,表示该实例修改的次数。(所有集合中都有modCount这样一个记录修改次数的属性),每次增改添加都会增加一次该ArrayList修改次数,而上边的add(E e)方法是将新元素添加到list尾部。

2.2.4 ArrayList扩容

privatestaticintcalculateCapacity(Object[] elementData,intminCapacity){if(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//DEFAULT_CAPACITY是10returnMath.max(DEFAULT_CAPACITY, minCapacity);}returnminCapacity;}复制代码

可见当初始化的list是一个空ArrayList的时候,会直接扩容到DEFAULT_CAPACITY,该值大小是一个默认值10。而当添加进ArrayList中的元素超过了数组能存放的最大值就会进行扩容。注意到这一行代码

int newCapacity = oldCapacity + (oldCapacity>>1);复制代码

采用右移运算,就是原来的一般,所以是扩容1.5倍。比如10的二进制是1010,右移后变成101就是5。

privatevoidgrow(intminCapacity){// overflow-conscious codeintoldCapacity = elementData.length;intnewCapacity = oldCapacity + (oldCapacity >>1);if(newCapacity - minCapacity 0)newCapacity = hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a win:elementData = Arrays.copyOf(elementData, newCapacity);}复制代码

2.2.5 数组copy

Java 是无法自己分配空间的,是底层C和C++的实现。以 C 为例,我们知道 C 中数组是一个指向首部的指针,比如我们 C 语言对数组进行分配内存。Java 就是通过 arraycopy 这个 native 方法实现的数组的复制。

publicstaticnativevoidarraycopy(Object src,intsrcPos,Object dest,intdestPos,intlength);复制代码
p = (int*)malloc(len*sizeof(int));复制代码

这样的好处何在呢?**Java里内存是由jvm管理的,而数组是分配的连续内存,而arrayList不一定是连续内存,当然jvm会帮我们做这样的事,jvm会有内部的优化,会在后续的例子中结合问题来说明。

2.2.6 why" />

可见LinkedList既是List接口的实现也是Queue的实现(Deque),故其和ArrayList相比LinkedList支持的功能更多,其可视作队列来使用,当然下文中不强调其队列的实现。

2.3.2 LinkedList的结构

transientNode first;/*** Pointer to last node.* Invariant: (first == null && last == null) ||* (last.next == null && last.item != null)*/transientNode last;复制代码

LinkedList由一个头节点和一个尾节点组成,分别指向链表的头部和尾部。 LinkedList中Node源码如下,由当前值item,和指向上一个节点prev和指向下个节点next的指针组成。并且只含有一个构造方法,按照(prev, item, next)这样的参数顺序构造。

privatestaticclassNode {E item;Node next;Node prev;Node(Node prev, E element, Node next) {this.item = element;this.next = next;this.prev = prev;}}复制代码

那LinkedList里节点Node是什么结构呢? LinkedList由一个头节点,一个尾节点和一个默认为0的size构成,可见其是双向链表。

transientintsize =0;transientNode first;transientNode last;publicLinkedList(){}复制代码

数据结构中链表的头插法linkFirst和尾插法linkLast

/*** Links e as first element. 头插法*/privatevoidlinkFirst(E e){finalNode f = first;finalNode newNode =newNode(null, e, f);first = newNode;if(f ==null)last = newNode;elsef.prev = newNode;size++;modCount++;}/*** Links e as last element. 尾插法*/voidlinkLast(E e){finalNode l = last;finalNode newNode =newNode(l, e,null);last = newNode;if(l ==null)first = newNode;elsel.next = newNode;size++;modCount++;}复制代码

2.3.3 LinkedList查询方法

按照下标获取某一个节点**:get方法,获取第index个节点。

publicEget(intindex){checkElementIndex(index);returnnode(index).item;}复制代码

node(index)方法是怎么实现的呢?判断index是更靠近头部还是尾部,靠近哪段从哪段遍历获取值。

Nodenode(intindex){// assert isElementIndex(index);//判断index更靠近头部还是尾部if(index >1)) {Node x = first;for(inti =0; i < index; i++)x = x.next;returnx;}else{Node x = last;for(inti = size -1; i > index; i--)x = x.prev;returnx;}}复制代码

查询索引修改方法,先找到对应节点,将新的值替换掉老的值。

publicEset(intindex, E element){checkElementIndex(index);Node x = node(index);E oldVal = x.item;x.item = element;returnoldVal;}复制代码

这个也是为什么ArrayList随机访问比LinkedList快的原因**,LinkedList要遍历找到该位置才能进行修改,而ArrayList是内部数组操作会更快。

2.4.3 LinkedList修改方法

新增一个节点,可以看到是采用尾插法将新节点放入尾部。

publicbooleanadd(E e){linkLast(e);returntrue;}复制代码

2.5 Vector

和ArrayList一样,Vector也是List接口的一个实现类。其中List接口主要实现类有ArrayLIst,LinkedList,Vector,Stack,其中后两者用的特别少。

2.5.1 vector组成

和ArrayList基本一样。

//存放元素的数组protectedObject[] elementData;//有效元素数量,小于等于数组长度protectedintelementCount;//容量增加量,和扩容相关protectedintcapacityIncrement;复制代码

2.5.2 vector线程安全性

vector是线程安全的,synchronized修饰的操作方法。

2.5.3 vector扩容

privatevoidgrow(intminCapacity){// overflow-conscious codeintoldCapacity = elementData.length;//扩容大小intnewCapacity = oldCapacity + ((capacityIncrement >0) ?capacityIncrement : oldCapacity);if(newCapacity - minCapacity 0)newCapacity = hugeCapacity(minCapacity);elementData = Arrays.copyOf(elementData, newCapacity);}复制代码

看源码可知,扩容当构造没有capacityIncrement时,一次扩容数组变成原来两倍,否则每次增加capacityIncrement。

2.5.4 vector方法经典示例

移除某一元素

publicsynchronizedEremove(intindex){modCount++;if(index >= elementCount)thrownewArrayIndexOutOfBoundsException(index);E oldValue = elementData(index);intnumMoved = elementCount - index -1;if(numMoved >0)//复制数组,假设数组移除了中间某元素,后边有效值前移1位System.arraycopy(elementData, index+1, elementData, index,numMoved);//引用null ,gc会处理elementData[--elementCount] =null;// Let gc do its workreturnoldValue;}复制代码

这儿主要有一个两行代码需要注意,笔者在代码中有注释。数组移除某一元素并且移动后,一定要将原来末尾设为null,且有效长度减1。总体上vector实现是比较简单粗暴的,也很少用到,随便看看即可。

2.6 Stack

Stack也是List接口的实现类之一,和Vector一样,因为性能原因,更主要在开发过程中很少用到栈这种数据结构,不过栈在计算机底层是一种非常重要的数据结构,下边将探讨下Java中Stack。

2.6.1 Stack的继承关系

Stack继承于Vector,其也是List接口的实现类。之前提到过Vector是线程安全的,因为其方法都是synchronized修饰的,故此处Stack从父类Vector继承而来的操作也是线程安全的。

2.6.2 Stack的使用

正如Stack是栈的实现,故其主要操作为push入栈和pop出栈,而栈最大的特点就是LIFO(Last In First Out)。

Stack strings =newStack();strings.push("aaa");strings.push("bbb");strings.push("ccc");System.err.println(strings.pop());复制代码

上边代码可以看到,最后push入栈的字符串"ccc"也最先出栈。

2.6.3 Stack源码

/*** Stack源码(Jdk8)*/publicclassStackextendsVector{publicStack(){}//入栈,使用的是Vector的addElement方法。publicEpush(E item){addElement(item);returnitem;}//出栈,找到数组最后一个元素,移除并返回。publicsynchronizedEpop(){E obj;intlen = size();obj = peek();removeElementAt(len -1);returnobj;}publicsynchronizedEpeek(){intlen = size();if(len ==0)thrownewEmptyStackException();returnelementAt(len -1);}publicbooleanempty(){returnsize() ==0;}publicsynchronizedintsearch(Object o){inti = lastIndexOf(o);if(i >=0) {returnsize() - i;}return-1;}privatestaticfinallongserialVersionUID =1224463164541339165L;}复制代码

从Stack的源码中可见,其用的push方法用的是Vector的addElement(E e)方法,该方法是将元素放在集合的尾部,而其pop方法使用的是Vector的removeElementAt(Index x)方法,移除并获取集合的尾部元素,可见Stack的操作就是基于线性表的尾部进行操作的。

3、Queue

正如数据结构中描述,queue是一种先进先出的数据结构,也就是first in first out。可以将queue看作一个只可以从某一段放元素进去的一个容器,取元素只能从另一端取,整个机制如下图所示,不过需要注意的是,队列并没有规定是从哪一端插入,从哪一段取出。

3.1 什么是Deque

Deque英文全称是Double ended queue,也就是俗称的双端队列。就是说对于这个队列容器,既可以从头部插入也可以从尾部插入,既可以从头部获取,也可以从尾部获取,其机制如下图所示。

3.1.1 Java中的Queue接口

此处需要注意,Java中的队列明确有从尾部插入,头部取出,所以Java中queue的实现都是从头部取出。

packagejava.util;publicinterfaceQueueextendsCollection{//集合中插入元素booleanadd(E e);//队列中插入元素booleanoffer(E e);//移除元素,当集合为空,抛出异常Eremove();//移除队列头部元素并返回,如果为空,返回nullEpoll();//查询集合第一个元素,如果为空,抛出异常Eelement();//查询队列中第一个元素,如果为空,返回nullEpeek();}复制代码

Java queue常常使用的方法如表格所示,对于表格中接口和表格中没有的接口方法区别为:队列的操作不会因为队列为空抛出异常,而集合的操作是队列为空抛出异常。

3.1.2 Deque接口

packagejava.util;publicinterfaceDequeextendsQueue{//deque的操作方法voidaddFirst(E e);voidaddLast(E e);booleanofferFirst(E e);booleanofferLast(E e);EremoveFirst();EremoveLast();EpollFirst();EpollLast();EgetFirst();EgetLast();EpeekFirst();EpeekLast();booleanremoveFirstOccurrence(Object o);booleanremoveLastOccurrence(Object o);// *** Queue methods ***booleanadd(E e);booleanoffer(E e);Eremove();Epoll();Eelement();Epeek();// 省略一堆stack接口方法和collection接口方法}复制代码

和Queue中的方法一样,方法名多了First或者Last,First结尾的方法即从头部进行操作,Last即从尾部进行操作。

3.1.3 Queue,Deque的实现类

Java中关于Queue的实现主要用的是双端队列,毕竟操作更加方便自由,Queue的实现有PriorityQueue,Deque在java.util中主要有ArrayDeque和LinkedList两个实现类,两者一个是基于数组的实现,一个是基于链表的实现。在之前LinkedList文章中也提到过其是一个双向链表,在此基础之上实现了Deque接口。

3.2 PriorityQueue

PriorityQueue是Java中唯一一个Queue接口的直接实现,如其名字所示,优先队列,其内部支持按照一定的规则对内部元素进行排序。

3.2.1 PriorityQueue继承关系

先看下PriorityQueue的继承实现关系,可知其是Queue的实现类,主要使用方式是队列的基本操作,而之前讲到过Queue的基本原理,其核心是FIFO(First In First Out)原理。 Java中的PriorityQueue的实现也是符合队列的方式,不过又略有不同,却别就在于PriorityQueue的priority上,其是一个支持优先级的队列,当使用了其priority的特性的时候,则并非FIFO。

3.2.2 PriorityQueue的使用

案列1:

PriorityQueuequeue=newPriorityQueue();queue.add(20);queue.add(14);queue.add(21);queue.add(8);queue.add(9);queue.add(11);queue.add(13);queue.add(10);queue.add(12);queue.add(15);while(queue.size()>0){Integer poll =queue.poll();System.err.print(poll+"->");}复制代码

上述代码做的事为往队列中放入10个int值,然后使用Queue的poll()方法依次取出,最后结果为每次取出来都是队列中最小的值,说明 了PriorityQueue内部确实是有一定顺序规则的。

案例2:

<preTest{"+"a="+ a +'}';}@OverridepublicintcompareTo(Test o){return0;}}publicstaticvoidmain(String[] args){PriorityQueuequeue=newPriorityQueue();queue.add(newTest(20));queue.add(newTest(14));queue.add(newTest(21));queue.add(newTest(8));queue.add(newTest(9));queue.add(newTest(11));queue.add(newTest(13));queue.add(newTest(10));queue.add(newTest(12));queue.add(newTest(15));while(queue.size()>0){Test poll =queue.poll();System.err.print(poll+"->");}}复制代码

上述代码重写了compareTo方法都返回0,即不做优先级排序。发现我们返回的顺序为Test{a=20}->Test{a=15}->Test{a=12}->Test{a=10}->Test{a=13}->Test{a=11}->Test{a=9}->Test{a=8}->Test{a=21}->Test{a=14},和放入的顺序还是不同,所以这儿需要注意在实现Comparable接口的时候一定要按照一定的规则进行优先级排序,关于为什么取出来的顺序和放入的顺序不一致后边将从源码来分析。

3.2.3 PriorityQueue组成

/*** 默认容量大小,数组大小*/privatestaticfinalintDEFAULT_INITIAL_CAPACITY =11;/*** 存放元素的数组*/transient Object[]queue;// non-private to simplify nested class access/*** 队列中存放了多少元素*/privateintsize =0;/*** 自定义的比较规则,有该规则时优先使用,否则使用元素实现的Comparable接口方法。*/privatefinal Comparator

可见ArrayDeque是Deque接口的实现,和LinkedList不同的是,LinkedList既是List接口也是Deque接口的实现。

3.3.2 ArrayDeque使用

案列

ArrayDequedeque=newArrayDeque();deque.offer("aaa");deque.offer("bbb");deque.offer("ccc");deque.offer("ddd");//peek方法只获取不移除System.err.println(deque.peekFirst());System.err.println(deque.peekLast());复制代码

案例二:

ArrayDequedeque=newArrayDeque();deque.offerFirst("aaa");deque.offerLast("bbb");deque.offerFirst("ccc");deque.offerLast("ddd");String a;while((a =deque.pollLast())!=null){System.err.print(a+"->");}复制代码

上述程序最后得到队列中排列结果为ccc,aaa,bbb,ddd所以循环使用pollLast(),结果ddd,bbb,aaa,ccc,图示案列二的插入逻辑如下:

3.3.4 ArrayDeque内部组成

//具体存放元素的数组,数组大小一定是2的幂次方transientObject[] elements;// non-private to//队列头索引transientinthead;//队列尾索引transientinttail;//默认的最小初始化容量,即传入的容量小于8容量为8,而默认容量是16privatestaticfinalintMIN_INITIAL_CAPACITY =8;复制代码

3.3.5 数组elements长度

此处elements数组的长度永远是2的幂次方,此处的实现方法和hashMap中基本一样,即保证长度的二进制全部由1组成,然后再加1,则变成了100…,故一定是2的幂次方。

privatestaticintcalculateSize(intnumElements){intinitialCapacity = MIN_INITIAL_CAPACITY;// Find the best power of two to hold elements.// Tests "= initialCapacity) {initialCapacity = numElements;initialCapacity |= (initialCapacity >>>1);initialCapacity |= (initialCapacity >>>2);initialCapacity |= (initialCapacity >>>4);initialCapacity |= (initialCapacity >>>8);initialCapacity |= (initialCapacity >>>16);initialCapacity++;if(initialCapacity >>=1;// Good luck allocating 2 ^ 30 elements}returninitialCapacity;}复制代码

3.3.6 ArrayDeque实现机制

如下图所示:

此处应将数组视作首尾相连的,最初头部和尾部索引都是0,addLast方向往右,addFirst方向往左,所以数组中间可能是空的,当头指针和尾指针相遇的时候对数组进行扩容,并对元素位置进行调整。 源码:

publicvoidaddFirst(E e){if(e ==null)thrownewNullPointerException();elements[head = (head -1) & (elements.length -1)] = e;if(head == tail)doubleCapacity();}复制代码

注意下边这行代码,表示当head-1大于等于0时,head=head-1,否则head=elements.length - 1。

head= (head -1) & (elements.length -1)复制代码

换一种写法就是下边这样,是不是就是上边addFirst的指针移动方向?

head= head-1>=0" />

4.2.2HashSet源码

publicclassHashSetextendsAbstractSetimplementsSet,Cloneable,java.io.Serializable{staticfinallongserialVersionUID =-5024744406713321676L;privatetransient HashMapmap;privatestaticfinal Object PRESENT =newObject();publicHashSet(){map=newHashMap();}publicHashSet(Collection c){map=newHashMap(Math.max((int) (c.size()/.75f) +1,16));addAll(c);}publicHashSet(intinitialCapacity,floatloadFactor){map=newHashMap(initialCapacity, loadFactor);}publicHashSet(intinitialCapacity){map=newHashMap(initialCapacity);}HashSet(intinitialCapacity,floatloadFactor, boolean dummy) {map=newLinkedHashMap(initialCapacity, loadFactor);}publicIterator iterator() {returnmap.keySet().iterator();}publicintsize(){returnmap.size();}publicbooleanisEmpty(){returnmap.isEmpty();}publicbooleancontains(Object o){returnmap.containsKey(o);}publicbooleanadd(E e){returnmap.put(e, PRESENT)==null;}publicbooleanremove(Object o){returnmap.remove(o)==PRESENT;}publicvoidclear(){map.clear();}}复制代码

可以看到HashSet内部其实是一个HashMap。

4.2.3 HashSet是如何保证不重复的呢?

可见HashSet的add方法,插入的值会作为HashMap的key,所以是HashMap保证了不重复。map的put方法新增一个原来不存在的值会返回null,如果原来存在的话会返回原来存在的值。关于HashMap是如何实现的,见后续!

4.3 LinkedHashSet

LinkedHashSet用的也比较少,其也是基于Set的实现。

4.3.1 LinkedHashSet继承关系

和HashSet一样,其也是Set接口的实现类,并且是HashSet的子类。

4.3.2 LinkedHashSet源码

packagejava.util;publicclassLinkedHashSetextendsHashSetimplementsSet,Cloneable,java.io.Serializable{privatestaticfinallongserialVersionUID = -2851667679971038690L;publicLinkedHashSet(intinitialCapacity,floatloadFactor){//调用HashSet的构造方法super(initialCapacity, loadFactor,true);}publicLinkedHashSet(intinitialCapacity){super(initialCapacity, .75f,true);}publicLinkedHashSet(){super(16, .75f,true);}publicLinkedHashSet(Collection

5、Map

Map是一种键值对的结构,就是常说的Key-Value结构,一个Map就是很多这样K-V键值对组成的,一个K-V结构我们将其称作Entry,在Java里,Map是用的非常多的一种数据结构。上图展示了Map家族最基础的一个结构(只是指java.util中)。整理了2021年Java面试题。

5.1 Map接口

package java.util;importjava.util.function.BiConsumer;importjava.util.function.BiFunction;importjava.util.function.Function;importjava.io.Serializable;publicinterfaceMap {// Query Operationsint size();booleanisEmpty();booleancontainsKey(Objectkey);booleancontainsValue(Objectvalue);Vget(Objectkey);// Modification OperationsV put(K key, V value);V remove(Objectkey);// Bulk OperationsvoidputAll(Map m);voidclear();Set keySet();Collection values();Set<Map.Entry> entrySet();interfaceEntry {K getKey();V getValue();V setValue(V value);booleanequals(Objecto);int hashCode();publicstatic<KextendsComparable, V> Comparator<Map.Entry> comparingByKey() {return(Comparator<Map.Entry> & Serializable)(c1, c2) -> c1.getKey().compareTo(c2.getKey());}publicstatic<K, VextendsComparable> Comparator<Map.Entry> comparingByValue() {return(Comparator<Map.Entry> & Serializable)(c1, c2) -> c1.getValue().compareTo(c2.getValue());}publicstatic Comparator<Map.Entry> comparingByKey(Comparator cmp) {Objects.requireNonNull(cmp);return(Comparator<Map.Entry> & Serializable)(c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());}publicstatic Comparator<Map.Entry> comparingByValue(Comparator cmp) {Objects.requireNonNull(cmp);return(Comparator<Map.Entry> & Serializable)(c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());}}// Comparison and hashingbooleanequals(Objecto);int hashCode();defaultV getOrDefault(Objectkey, V defaultValue) {V v;return(((v =get(key)) !=null) || containsKey(key))? v: defaultValue;}defaultvoidforEach(BiConsumer action) {Objects.requireNonNull(action);for(Map.Entry entry : entrySet()) {K k;V v;try{k = entry.getKey();v = entry.getValue();}catch(IllegalStateException ise) {// this usually means the entry is no longer in the map.thrownewConcurrentModificationException(ise);}action.accept(k, v);}}defaultvoidreplaceAll(BiFunctionfunction){Objects.requireNonNull(function);for(Map.Entry entry : entrySet()) {K k;V v;try{k = entry.getKey();v = entry.getValue();}catch(IllegalStateException ise) {// this usually means the entry is no longer in the map.thrownewConcurrentModificationException(ise);}// ise thrown from function is not a cme.v =function.apply(k, v);try{entry.setValue(v);}catch(IllegalStateException ise) {// this usually means the entry is no longer in the map.thrownewConcurrentModificationException(ise);}}}defaultV putIfAbsent(K key, V value) {V v =get(key);if(v ==null) {v = put(key, value);}returnv;}defaultbooleanremove(Objectkey,Objectvalue) {ObjectcurValue =get(key);if(!Objects.equals(curValue, value) ||(curValue ==null&& !containsKey(key))) {returnfalse;}remove(key);returntrue;}defaultbooleanreplace(K key, V oldValue, V newValue) {ObjectcurValue =get(key);if(!Objects.equals(curValue, oldValue) ||(curValue ==null&& !containsKey(key))) {returnfalse;}put(key, newValue);returntrue;}defaultV replace(K key, V value) {V curValue;if(((curValue =get(key)) !=null) || containsKey(key)) {curValue = put(key, value);}returncurValue;}defaultV computeIfAbsent(K key,Function mappingFunction) {Objects.requireNonNull(mappingFunction);V v;if((v =get(key)) ==null) {V newValue;if((newValue = mappingFunction.apply(key)) !=null) {put(key, newValue);returnnewValue;}}returnv;}defaultV computeIfPresent(K key,BiFunction remappingFunction) {Objects.requireNonNull(remappingFunction);V oldValue;if((oldValue =get(key)) !=null) {V newValue = remappingFunction.apply(key, oldValue);if(newValue !=null) {put(key, newValue);returnnewValue;}else{remove(key);returnnull;}}else{returnnull;}}defaultV compute(K key,BiFunction remappingFunction) {Objects.requireNonNull(remappingFunction);V oldValue =get(key);V newValue = remappingFunction.apply(key, oldValue);if(newValue ==null) {// delete mappingif(oldValue !=null|| containsKey(key)) {// something to removeremove(key);returnnull;}else{// nothing to do. Leave things as they were.returnnull;}}else{// add or replace old mappingput(key, newValue);returnnewValue;}}defaultV merge(K key, V value,BiFunction remappingFunction) {Objects.requireNonNull(remappingFunction);Objects.requireNonNull(value);V oldValue =get(key);V newValue = (oldValue ==null) ? value :remappingFunction.apply(oldValue, value);if(newValue ==null) {remove(key);}else{put(key, newValue);}returnnewValue;}}复制代码

Map接口本身就是一个顶层接口,由一堆Map自身接口方法和一个Entry接口组成,Entry接口定义了主要是关于Key-Value自身的一些操作,Map接口定义的是一些属性和关于属性查找修改的一些接口方法。

5.2 HashMap

HashMap是Java中最常用K-V容器,采用了哈希的方式进行实现,HashMap中存储的是一个又一个Key-Value的键值对,我们将其称作Entry,HashMap对Entry进行了扩展(称作Node),使其成为链表或者树的结构使其存储在HashMap的容器里(是一个数组)。

5.2.1 HashMap继承关系

5.2.2 HashMap存储的数据

Map接口中有一个Entry接口,在HashMap中对其进行了实现,Entry的实现是HashMap存放的数据的类型。其中Entry在HashMap的实现是Node,Node是一个单链表的结构,TreeNode是其子类,是一个红黑树的类型,其继承结构图如下:

HashMap存放数据的数据是什么呢?代码中存放数据的容器如下:

transient Node[]table;复制代码

说明了该容器中是一个又一个node组成,而node有三种实现,所以hashMap中存放的node的形式既可以是Node也可以是TreeNode。

5.2.3 HashMap的组成

有了上边的概念之后来看一下HashMap里有哪些组成吧!

//是hashMap的最小容量16,容量就是数组的大小也就是变量,transient Node[] table。staticfinalintDEFAULT_INITIAL_CAPACITY =1<<4;// aka 16//最大数量,该数组最大值为2^31一次方。staticfinalintMAXIMUM_CAPACITY =1<<30;//默认的加载因子,如果构造的时候不传则为0.75staticfinalfloatDEFAULT_LOAD_FACTOR =0.75f;//一个位置里存放的节点转化成树的阈值,也就是8,比如数组里有一个node,这个// node链表的长度达到该值才会转化为红黑树。staticfinalintTREEIFY_THRESHOLD =8;//当一个反树化的阈值,当这个node长度减少到该值就会从树转化成链表staticfinalintUNTREEIFY_THRESHOLD =6;//满足节点变成树的另一个条件,就是存放node的数组长度要达到64staticfinalintMIN_TREEIFY_CAPACITY =64;//具体存放数据的数组transientNode[] table;//entrySet,一个存放k-v缓冲区transientSet<Map.Entry> entrySet;//size是指hashMap中存放了多少个键值对transientintsize;//对map的修改次数transientintmodCount;//加载因子finalfloatloadFactor;复制代码

这儿要说两个概念,table是指的存放数据的数组,bin是指的table中某一个位置的node,一个node可以理解成一批/一盒数据。

5.2.4 HashMap中的构造函数*

//只有容量,initialCapacitypublicHashMap(intinitialCapacity){this(initialCapacity, DEFAULT_LOAD_FACTOR);}publicHashMap(){this.loadFactor = DEFAULT_LOAD_FACTOR;// all other fields defaulted}publicHashMap(Map MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;if(loadFactor <=0|| Float.isNaN(loadFactor))thrownewIllegalArgumentException("Illegal load factor: "+loadFactor);this.loadFactor = loadFactor;//当前数组table的大小,一定是是2的幂次方// tableSizeFor保证了数组一定是是2的幂次方,是大于initialCapacity最结进的值。this.threshold = tableSizeFor(initialCapacity);}复制代码

tableSizeFor()方法保证了数组大小一定是是2的幂次方,是如何实现的呢?

staticfinal int tableSizeFor(int cap) {intn = cap-1;n|= n >>>1;n|= n >>>2;n|= n >>>4;n|= n >>>8;n|= n >>>16;return(n = MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n +1;}复制代码

该方法将一个二进制数第一位1后边的数字全部变成1,然后再加1,这样这个二进制数就一定是100…这样的形式。此处实现在ArrayDeque的实现中也用到了类似的方法来保证数组长度一定是2的幂次方。

5.2.5 put方法

开发人员使用的put方法:

publicVput(K key, Vvalue){returnputVal(hash(key), key,value,false,true);}复制代码

真正HashMap内部使用的put值的方法:

final VputVal(inthash, K key, Vvalue, boolean onlyIfAbsent,boolean evict){Node[] tab; Node p;intn, i;if((tab = table) ==null|| (n = tab.length) ==0)n = (tab = resize()).length;//当hash到的位置,该位置为null的时候,存放一个新node放入// 这儿p赋值成了table该位置的node值if((p = tab[i = (n -1) & hash]) ==null)tab[i] = newNode(hash, key,value,null);else{Node e; K k;//该位置第一个就是查找到的值,将p赋给eif(p.hash == hash &&((k = p.key) == key || (key !=null&& key.equals(k))))e = p;//如果是红黑树,调用红黑树的putTreeVal方法elseif(p instanceof TreeNode)e = ((TreeNode)p).putTreeVal(this, tab, hash, key,value);else{//是链表,遍历,注意e = p.next这个一直将下一节点赋值给e,直到尾部,注意开头是++binCountfor(intbinCount =0; ; ++binCount) {if((e = p.next) ==null) {p.next = newNode(hash, key,value,null);//当链表长度大于等于7,插入第8位,树化if(binCount >= TREEIFY_THRESHOLD -1)// -1 for 1sttreeifyBin(tab, hash);break;}if(e.hash == hash &&((k = e.key) == key || (key !=null&& key.equals(k))))break;p = e;}}if(e !=null) {// existing mapping for keyV oldValue = e.value;if(!onlyIfAbsent || oldValue ==null)e.value=value;afterNodeAccess(e);returnoldValue;}}++modCount;if(++size > threshold)resize();afterNodeInsertion(evict);returnnull;}复制代码

5.2.6 查找方法

final NodegetNode(inthash, Object key){Node[] tab; Node first, e;intn; K k;//先判断表不为空if((tab = table) !=null&& (n = tab.length) >0&&//这一行是找到要查询的Key在table中的位置,table是存放HashMap中每一个Node的数组。(first = tab[(n -1) & hash]) !=null) {//Node可能是一个链表或者树,先判断根节点是否是要查询的key,就是根节点,方便后续遍历Node写法并且//对于只有根节点的Node直接判断if(first.hash == hash &&// always check first node((k = first.key) == key || (key !=null&& key.equals(k))))returnfirst;//有子节点if((e = first.next) !=null) {//红黑树查找if(first instanceof TreeNode)return((TreeNode)first).getTreeNode(hash, key);do{//链表查找if(e.hash == hash &&((k = e.key) == key || (key !=null&& key.equals(k))))returne;}//遍历链表,当链表后续为null则推出循环while((e = e.next) !=null);}}returnnull;}复制代码

5.3 HashTable

和HashMap不同,HashTable的实现方式完全不同,这点从二者的类继承关系就可以看出端倪来,HashTable和HashMap虽然都实现了Map接口,但是HashTable继承了DIctionary抽象类,而HashMap继承了AbstractMap抽象类。

5.3.1 HashTable的类继承关系图

HashTable

HashMap

5.3.2 Dictionary接口

publicabstractclassDictionary{publicDictionary(){}publicabstractintsize();publicabstractbooleanisEmpty();publicabstractEnumerationkeys();publicabstractEnumerationelements();publicabstractVget(Object key);publicabstractVput(K key, V value);publicabstractVremove(Object key);}复制代码

Dictionary类中有这样一行注释,当key为null时会抛出空指针NullPointerException,这也说明了HashTabel是不允许Key为null的。

//throws NullPointerExceptionifthe {@code key}is{@codenull}.

复制代码

5.3.3 HashTable组成

/*** The hash table data.* 真正存放数据的数组*/privatetransient Entry entry = (Entry)tab[index];for(; entry !=null; entry = entry.next) {//如果遍历链表找到了则替换旧值并返回if((entry.hash == hash) && entry.key.equals(key)) {V old = entry.value;entry.value=value;returnold;}}addEntry(hash, key,value, index);returnnull;}复制代码

本质上就是先hash求索引,遍历该索引Entry链表,如果找到hash值和key都和put的key一样的时候就替换旧值,否则使用addEntry方法添加新值进入table,因为添加新元素就涉及到修改元素大小,还可能需要扩容等,具体看下边的addEntry方法可知。

privatevoidaddEntry(inthash, K key, Vvalue,intindex){Entry tab[] = table;//如果扩容需要重新计算hash,所以index和table都会被修改if(count >= threshold) {// Rehash the table if the threshold is exceededrehash();tab = table;hash = key.hashCode();index = (hash &0x7FFFFFFF) % tab.length;}// Creates the new entry.@SuppressWarnings("unchecked")Entry e = (Entry) tab[index];//插入新元素tab[index] =newEntry(hash, key,value, e);count++;modCount++;}复制代码
tab[index]= new Entry(hash, key, value, e);复制代码

这行代码是真正插入新元素的方法,采用头插法,单链表一般都用头插法(快)。

5.3.6 get方法

@SuppressWarnings("unchecked")publicsynchronized Vget(Object key){Entry tab[] = table;inthash =key.hashCode();intindex = (hash &0x7FFFFFFF) % tab.length;for(Entry e = tab[index] ; e !=null; e = e.next) {if((e.hash == hash) && e.key.equals(key)) {return(V)e.value;}}returnnull;}复制代码

get方法就简单很多就是hash,找到索引,遍历链表找到对应的value,没有则返回null。相比诸君都已经看到,HashTable中方法是用synchronized修饰的,所以其操作是线程安全的,但是效率会受影响。