当年学长把这份Java总结给我,让我普通二本校招拿到22K

Source

💂 个人主页: Java程序鱼
🤟 整个Java 体系的面试题我都会分享,大家可以持续关注
💬 如果文章对你有帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦
💅 有任何问题欢迎私信,看到会及时回复!

序号 内容 链接地址
1 Java基础知识面试题 https://blog.csdn.net/qq_35620342/article/details/119636436
2 Java集合容器面试题 https://blog.csdn.net/qq_35620342/article/details/119947254
3 Java并发编程面试题 https://blog.csdn.net/qq_35620342/article/details/119977224
4 Java异常面试题 https://blog.csdn.net/qq_35620342/article/details/119977051
5 JVM面试题 待分享
6 Java Web面试题 https://blog.csdn.net/qq_35620342/article/details/119642114
7 Spring面试题 https://blog.csdn.net/qq_35620342/article/details/119956512
8 Spring MVC面试题 https://blog.csdn.net/qq_35620342/article/details/119965560
9 Spring Boot面试题 待分享
10 MyBatis面试题 https://blog.csdn.net/qq_35620342/article/details/119956541
11 Spring Cloud面试题 待分享
12 Redis面试题 https://blog.csdn.net/qq_35620342/article/details/119575020
13 MySQL数据库面试题 https://blog.csdn.net/qq_35620342/article/details/119930887
14 RabbitMQ面试题 待分享
15 Dubbo面试题 待分享
16 Linux面试题 待分享
17 Tomcat面试题 待分享
18 ZooKeeper面试题 待分享
19 Netty面试题 待分享
20 数据结构与算法面试题 待分享


前言

为什么要学习JDK源码?
各种各样的系统或者技术,最底层、最最核心的一块,其实都是集合(在内存里面存放数据)、并发(分布式系统,底层都会开多个线程,并发的处理一些东西,这里会涉及到一些锁,同步,等等)、IO(读写磁盘上的文件里的数据,发起网络IO,通过网络读写数据)、网络(如何在分布式系统中,各个机器建立网络连接,互相发送请求进行通信),本期先给大家分享集合源码。


一、List

List 是有序的 Collection

List中的元素是有序的、可重复的,主要实现方式有动态数组和链表。

java中提供的List的实现主要有ArrayList、LinkedList、CopyOnWriteArrayList,另外还有两个古老的类Vector和Stack。

在这里插入图片描述

1.ArrayList

ArrayList实现了List, RandomAccess, Cloneable, java.io.Serializable等接口。
ArrayList实现了List,提供了基础的添加、删除、遍历等操作。
ArrayList实现了RandomAccess,提供了随机访问的能力。
ArrayList实现了Cloneable,可以被克隆。
ArrayList实现了Serializable,可以被序列化。
AbstractCollection:主要实现了toString()、toArray()、contains()
AbstractList:主要实现了equals()、hashCode()

缺点:
①数组长度固定,java里面数组都是定长数组,比如数组大小设置为100,此时你不停的往ArrayList里面塞入这个数据,此时元素数量超过了100以后,此时就会发生一个数组的扩容,就会搞一个更大的数组,把以前的数组拷贝到新的数组里面去,这个数组扩容+元素拷贝的过程,相对来说会慢一些
②中间插入慢,数组来实现,数组你要是往数组的中间加一个元素,要把数组中那个新增元素后面的元素全部往后面挪动一位,所以说,如果你是往ArrayList中间插入一个元素,性能比较差,会导致他后面的大量的元素挪动一个位置

优点:
①支持随机访问,通过索引访问元素极快,时间复杂度为O(1)

核心参数:

/**
* 默认容量
*/
private static final int DEFAULT_CAPACITY = 10;

/**
* 空数组,如果传入的容量为0时使用

*/
private static final Object[] EMPTY_ELEMENTDATA = {
    
      };

/**
* 空数组,传传入容量时使用,添加第一个元素的时候会重新初始为默认容量大小
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
    
      };

/**
* 存储元素的数组
*/
transient Object[] elementData; // non-private to simplify nested class access

/**
* 集合中元素的个数
*/
private int size;

(1)DEFAULT_CAPACITY 默认容量为10,也就是通过new ArrayList()创建时的默认容量。
(2)EMPTY_ELEMENTDATA 空的数组,这种是通过new ArrayList(0)创建时用的是这个空数组。
(3)DEFAULTCAPACITY_EMPTY_ELEMENTDATA 也是空数组,这种是通过new ArrayList()创建时用的是这个空数组,与EMPTY_ELEMENTDATA的区别是在添加第一个元素时使用这个空数组的会初始化为DEFAULT_CAPACITY(10)个元素。
(4)elementData 真正存放元素的地方,使用transient是为了不序列化这个字段。 至于没有使用private修饰,后面注释是写的“为了简化嵌套类的访问”,但是楼主实测加了private嵌套类一样可以访问。 private表示是类私有的属性,只要是在这个类内部都可以访问,嵌套类或者内部类也是在类的内部,所以也可以访问类的私有成员。
(5)size 真正存储元素的个数,而不是elementData数组的长度。

核心方法:

构造器

(1)不传初始容量,初始化为DEFAULTCAPACITY_EMPTY_ELEMENTDATA空数组,会在添加第一个元素的时候扩容为默认的大小,即10。

public ArrayList() {
    
      
      // 如果没有传入初始容量,则使用空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA
      // 使用这个数组是在添加第一个元素的时候会扩容到默认大小10
      this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

(2)ArrayList(int initialCapacity)构造方法,传入初始容量,如果大于0就初始化elementData为对应大小,如果等于0就使用EMPTY_ELEMENTDATA空数组,如果小于0抛出异常

public ArrayList(int initialCapacity) {
    
      
       if (initialCapacity > 0) {
    
      
           this.elementData = new Object[initialCapacity];
       } else if (initialCapacity == 0) {
    
      
           this.elementData = EMPTY_ELEMENTDATA;
       } else {
    
      
           throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
       }
}

DEFAULTCAPACITY_EMPTY_ELEMENTDATA 也是空数组,这种是通过new ArrayList()创建时用的是这个空数组,与EMPTY_ELEMENTDATA的区别是在添加第一个元素时使用这个空数组的会初始化为DEFAULT_CAPACITY(10)个元素。

(3)ArrayList(Collection c)构造方法

传入集合并初始化elementData,这里会使用拷贝把传入集合的元素拷贝到elementData数组中,如果元素个数为0,则初始化为EMPTY_ELEMENTDATA空数组。

public ArrayList(Collection<? extends E> c) {
    
      
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
    
      
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
    
      
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
}

根据业务预测初始化的数组的大小,避免数组太小,往里面塞入数据的时候,导致数据不断的扩容,不断的搞新的数组

add()

(1)默认添加

添加元素到size+1位置,平均时间复杂度为O(1)。

public boolean add(E e) {
    
      
       // 检查是否需要扩容
       ensureCapacityInternal(size + 1);  // Increments modCount!!
       // 把元素插入到最后一位
       elementData[size++] = e;
       return true;
}

private void ensureCapacityInternal(int minCapacity) {
    
      
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    
      
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    
      
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    
      
        modCount++;

        // 判断是否需要扩容:size + 1 - 当前数组长度 > 0时扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
}

补充:当前数组长度10,添加第11个元素时才扩容

private void grow(int minCapacity) {
    
      
        // overflow-conscious code
        int oldCapacity = elementData.length;
        // 新容量是老容量的1.5倍(oldCapacity + (oldCapacity >> 1))
        // 老的大小 + 老的大小 >> 1(相当于除以2)
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 如果加了这么多容量发现比需要的容量还小,则以需要的容量为准
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 创建新容量的数组并把老数组拷贝到新数组
        elementData = Arrays.copyOf(elementData, newCapacity);
}

补充:空参构造器,第一次初始化时,就需要以需要的容量为准,因为0+(0>>1)=0

(2)添加到指定位置

public void add(int index, E element) {
    
      
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 把插入索引位置后的元素都往后挪一位
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        // 在插入索引位置放置插入的元素
        elementData[index] = element;
        size++;
}

addAll()

public boolean addAll(Collection<? extends E> c) {
    
      

    Object[] a = c.toArray();
    int numNew = a.length;

    ensureCapacityInternal(size + numNew);  // Increments modCount

    System.arraycopy(a, 0, elementData, size, numNew);

    size += numNew;

    return numNew != 0;

}

①将集合C转化为数组a
②获取数组a长度
③判断是否需要扩容

get()

获取指定索引位置的元素,时间复杂度为O(1)。

public E get(int index) {
    
      

    rangeCheck(index);
    return elementData(index);

}

private void rangeCheck(int index) {
    
      

    if (index >= size)

        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

}

E elementData(int index) {
    
      

    return (E) elementData[index];

}

remove()

(1)通过索引删除
删除指定索引位置的元素,时间复杂度为O(n)。

public E remove(int index) {
    
      

    rangeCheck(index);
    modCount++;

    E oldValue = elementData(index);

    int numMoved = size - index - 1;

    // 如果index不是最后一位,则将index之后的元素往前挪一位
    if (numMoved > 0)

        System.arraycopy(elementData, index+1, elementData, index,

                         numMoved);

    // 将最后一个元素删除,帮助GC
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;

}

private void rangeCheck(int index) {
    
      

    if (index < 0 || index >= this.size)

        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

}

(2)通过元素删除

删除指定元素值的元素,时间复杂度为O(n)。

public boolean remove(Object o) {
    
      

    if (o == null) {
    
      

        for (int index = 0; index < size; index++)

            if (elementData[index] == null) {
    
      

                fastRemove(index);
                return true;
            }

    } else {
    
      

        for (int index = 0; index < size; index++)

            if (o.equals(elementData[index])) {
    
      

                fastRemove(index);
                return true;
            }

    }
    return false;

}

private void fastRemove(int index) {
    
      

    modCount++;

    int numMoved = size - index - 1;

    if (numMoved > 0)

        System.arraycopy(elementData, index+1, elementData, index,

                         numMoved);

    elementData[--size] = null; // clear to let GC do its work

}

①找到第一个等于指定元素值的元素;
②快速删除;

fastRemove(int index)相对于remove(int index)少了检查索引越界的操作,可见jdk将性能优化到极致。

6.迭代器

private class Itr implements Iterator<E> {
    
      

    ...
}
private class ListItr extends Itr implements ListIterator<E> {
    
      

    ...
}

ListItr继承了Itr和ListIterator,ListIterator有插入和修改删除方法,同时还具有向前遍历的方法,所以ListIterator就具备了增删改查的功能,比Itr的功能更加齐全

快速失败机制

假设存在两个线程(线程1、线程2),线程1通过Iterator在遍历集合A中的元素,在某个时候线程2修改了集合A的结构(是结构上面的修改,而不是简单的修改集合元素的内容),那么这个时候程序就会抛出 ConcurrentModificationException 异常,从而产生fail-fast。
在这里插入图片描述

检查modCount标识符

final void checkForComodification() {
    
      

    if (modCount != expectedModCount)

        throw new ConcurrentModificationException();

}

无论是add()、remove(),还是clear(),只要涉及到修改集合中的元素个数时,都会改变modCount的值(都是modCount+1)。

ArrayList的Iterator实现类中调用next()时,会“调用checkForComodification()比较‘expectedModCount’和‘modCount’的大小”;但是,CopyOnWriteArrayList的Iterator实现类中,没有所谓的checkForComodification(),更不会抛出ConcurrentModificationException异常!

ArrayList如何把元素序列化?

elementData设置成了transient,那ArrayList是怎么把元素序列化的呢?

一般地,只要实现了Serializable接口即可自动序列化,writeObject()和readObject()是为了自己控制序列化的方式,这两个方法必须声明为private,在java.io.ObjectStreamClass#getPrivateMethod()方法中通过反射获取到writeObject()这个方法。(用户自定义的 writeObject 和 readObject 方法可以允许用户控制序列化的过程)

Serializable:一个对象序列化的接口,一个类只有实现了Serializable接口,它的对象才是可序列化的。
Serializeble的作用仅仅是一个标识这个类是可序列化的

什么情况下需要序列化?(应用场景)
①将内存对象保存到磁盘中或数据库中(持久化)。
②最常见的用法,web客服端连接服务器的时候,假如连接的客服端比较多,这时服务端压力比较大(内存不足),为了解决这些问题,把一些Session序列化,存入硬盘用的时候拿出来。
③在跨平台环境下,通过网络传输对象的时候需要序列化,例如WebService SOAP

transient:表示方法和属性等成员变量是透明的,不参与序列化。
static:静态变量不能序列化

什么是序列化和反序列化?
序列化机制:将内存Java 对象通过字节输出流写入硬盘(大部分是乱码,因为是二进制)。
反序列化机制:通过字节输入流从硬盘中文件中把对象读到内存中。(字节序列转换成Java对象)
为什么要有序列号?

如果没有给序列号,会根据属性和方法算出序列号,若属性和方法改变会报错,因为序列号不同,若加了序列号,可以添删属性,改变toString都不会报错
elementData定义为transient的优势,自己根据size序列化真实的元素,而不是根据数组的长度序列化元素,减少了空间占用。

总结:
(1)ArrayList内部使用数组存储元素,当数组长度不够时进行扩容,每次加一半的空间,ArrayList不会进行缩容;
(2)ArrayList支持随机访问,通过索引访问元素极快,时间复杂度为O(1);
(3)ArrayList添加元素到尾部极快,平均时间复杂度为O(1);
(4)ArrayList添加元素到中间比较慢,因为要搬移元素,平均时间复杂度为O(n);
(5)ArrayList从尾部删除元素极快,时间复杂度为O(1);
(6)ArrayList从中间删除元素比较慢,因为要搬移元素,平均时间复杂度为O(n);

2.LinkedList

LinkedList是一个以双向链表实现的List,它除了作为List使用,还可以作为队列或者栈来使用
在这里插入图片描述
ArrayList+Deque

因为ArrayList代表了List的典型实现,LInkedList代表了Deque的典型实现,同时LinkedList也实现了List,通过这两个类一首一尾正好可以把整个集合贯穿起来。

优点:
①插入性能高,不管是从末尾插入还是中间插入

缺点:
随机读性能差,例如LinkedList.get(10),这种操作,性能就很低,因为他需要遍历这个链表,从头开始遍历这个链表,直到找到index = 10的这个元素为止

使用场景

(1)ArrayList:一般场景,都是用ArrayList来代表一个集合,只要别频繁的往里面插入和灌入大量的元素就可以了,遍历,或者随机查,都可以

(2)LinkedList:适合,频繁的在list中插入和删除某个元素,然后尤其是LinkedList他其实是可以当做队列来用的,这个东西的话呢,我们后面看源码的时候,可以来看一下,先进先出,在list尾部怼进去一个元素,从头部拿出来一个元素。如果要在内存里实现一个基本的队列的话,可以用LinkedList

我们之前在电商系统开发的时候,在第一个版本中,用到了内存队列,用的就是LinkedList,他里面基于链表实现,天然就可以做队列的数据结构,先进先出,链表来实现,特别适合频繁的在里面插入元素什么的,也不会导致数组扩容

其实在工作中使用的时候,都是用的是java并发包下面的一些线程安全的集合,这个东西等到讲java并发包的时候,我们可以再来看一下

LinkedList作为队列使用
offer(),就是在队列尾部入队,将一个元素插入队列尾部
poll(),从队列头部出队
peek(),获取队列头部的元素,但是头部的元素不出队
offerFirst()
offerLast()

双向链表数据结构

item是元素
prev、next是指针
在这里插入图片描述

插入元素的原理

(1)尾部插入

add(),默认就是在队列的尾部插入一个元素,在那个双向链表的尾部插入一个元素
addLast(),跟add()方法是一样的,也是在尾部插入一个元素

在这里插入图片描述

public boolean add(E e) {
    
      
     linkLast(e);
     return true;
}

void linkLast(E e) {
    
      
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
}

(2)队列中间插入

add(index, element),是在队列的中间插入一个元素

在这里插入图片描述

public void add(int index, E element) {
    
      
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
}

void linkBefore(E e, Node<E> succ) {
    
      
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
}

Node<E> node(int index) {
    
      
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
    
      
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
    
      
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
}

(3)头部插入

在这里插入图片描述

addFirst(),在队列的头部插入一个元素

public void addFirst(E e) {
    
      
     linkFirst(e);
}

private void linkFirst(E e) {
    
      
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
}

获取元素的原理

(1)获取头部元素

getFirst() 获取头部的元素,他其实就是直接返回first指针指向的那个Node他里面的数据,他们都是返回头部的元素。getFirst()如果是对空list调用,会抛异常;peek()对空list调用,会返回null

(2)获取尾部元素

getLast():获取尾部的元素,他其实就是直接返回last指针指向的那个Node他里面的数据

public E getLast() {
    
      
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
 }

(3)获取中间的元素

public E get(int index) {
    
      
        checkElementIndex(index);
        return node(index).item;
}

Node<E> node(int index) {
    
      
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
    
      
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
    
      
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
}

LinkedList而言,get(int index)这个方法,是他的弱项,也是他的缺点,如果他要获取某个随机位置的元素,需要使用node(index)这个方法,是要进行链表的遍历,会判断一下index和size >> 1进行比较,如果在前半部分,就会从头部开始遍历;如果在后半部分,就会从尾部开始遍历

删除元素的原理

(1)删除尾部

(2)删除头部

(3)删除中间的元素

3.Vector&Stack

栈由Vector和Stack两个来实现,Stack代表了一个栈这种数据结构,他是继承自Vector来实现的,Vector是一种类似于ArrayList(基于数组来实现的)数据结构,有序的集合,Stack是一种基于数组来实现的栈数据结构

栈,先进后出,跟队列的先进先出是不一样

队列:一般是队尾巴进去开始排队,从队头开始出来,排队的过程,先进先出
栈:进去的时候直接压入栈底,出来的时候是从栈的最上面一个元素开始先出来,先进后出

ArrayList每次扩容是1.5倍,capacity + (capacity >> 1) = 1.5
Vector每次扩容默认是2倍,默认情况下是直接扩容两倍,2倍


二、Map

1.HashMap

核心成员变量

// 数组默认的初始大小,16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 负载因子,如果你在数组里的元素的个数达到了数组大小 * 负载因子,就会进行数组的扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 这个数组就是所谓的map里的核心数据结构的数组,数组的元素就可以看到是Node类型的,天然就可以挂成一个链表,单向链表,Node里面只有一个next指针
transient Node<K,V>[] table;
// 这个size代表的是就是当前hashmap中有多少个key-value对,如果这个数量达到了指定大小 * 负载因子,那么就会进行数组的扩容
transient int size;
static class Node<K,V> implements Map.Entry<K,V> {
    
      
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
}

这是一个很关键的内部类,他其实是代表了一个key-value对,里面包含了key的hash值,key,value,还有就是可以有一个next的指针,指向下一个Node,也就是指向单向链表中的下一个节点

通过这个next指针,就可以形成一个链表

优化后的降低冲突概率的hash算法

基础补充:
左移运算符(<<)
定义:将一个运算对象的各二进制位全部左移若干位(左边的二进制位丢弃,右边补0)。
设 a=1010 1110,a = a<< 2 将a的二进制位左移2位、右补0,即得a=1011 1000。
若左移时舍弃的高位不包含1,则每左移一位,相当于该数乘以2。

右移运算符(>>)
定义:将一个数的各二进制位全部右移若干位,正数左补0,负数左补1,右边丢弃。
例如:a=a>>2 将a的二进制位右移2位,左补0 或者 左补1得看被移数是正还是负。
操作数每右移一位,相当于该数除以2。

异或:两个位相同为0,相异为1

map.put(key, value) -> 对key进行hash算法,通过hash获取到对应的数组中的index位置

static final int hash(Object key) {
    
      
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

第一步:计算出key的哈希值

第二步:把hash值右移16位
假设原hashcode值是:1111 1111 1111 1111 1111 1010 0111 1100
h >>> 16,这个是位运算的操作,这个东西是把32位的二进制的数字,所有的bit往右侧右移了16位
在这里插入图片描述

第三步:用原hash值与右移16位的哈希值做异或操作
在这里插入图片描述

提前在hash()函数里面,就会把高16位和低16位进行一下异或运算,就可以保证说,在hash值的低16位里面,可以同时保留他的高16位和低16位的特征

相当于是在后面定位到数组index的位运算的时候,哪怕只有低16位参与了运算,其实运算的时候,他的hash值的高16位和低16位的特征都参与到了运算定位到那个数组的index

这么做有什么好处呢?为什么要保证同时将高16位和低16位的特征同时纳入运算,考虑到数组index的定位中去呢?因为这样子可以保证降低hash冲突的概率,如果说直接用hash值的低16位去运算定位数组index的话,可能会导致一定的hash冲突

为什么要做这么一个操作呢?hash算法里,为什么是hash值跟hash >>> 16位的结果,异或运算的结果呢?他这么做的话,这里牵扯到很多数学的概念,暂时先记住结论就行

目标是什么呢?通过这样的方式算出来的hash值,可以降低hash冲突的概率

结论1:后面在用这个hash值定位到数组的index的时候,也有一个位运算,但是的话呢,一般那个后面的位运算,一般都是用低16位在进行运算,所以说如果你不把hash值的高16位和低16位进行运算的话,那么就会导致你后面在通过hash值找到数组index的时候,只有hash值的低16位参与了运算
结论2:这样可以把他原来的高16位变成低16位,他其实只取16位,相当于把高16位和低16位做了一个异或运算,在hash值的低16位里面,可以同时保留他的高16位和低16位的特征
结论3:数组index定位时,只取hash前16位

继续关注put方法,才能完全看懂hash算法的优化

put操作原理

基础补充
与操作:两个位都为1时,结果才为1

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;
        // 1.假设,hashmap是空的,通过resize扩容,数组大小就是默认的16,负载因子就是默认的12
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 2.这是一个寻址算法,用&操作寻址,性能会比用取模高
        // 2.1 n是数组的长度,用数组长度和hash做与运算
        // 2.2在数组长度比较小的时候,高16基本上就废掉了
        // 3.这个数组里的元素是空的
        // 3.1这个分支,他的意思是说tab[i],i就是hash定位到的数组index,tab[i]如果为空,也就是hash定位到的这个位置是空的,之前没有任何人在这里,此时直接是放一个Node在数组的这个位置即可
        if ((p = tab[i = (n - 1) & hash]) == null)
        	// 3.2定位到数组了,那就把元素插入到链表或者红黑树里
            tab[i] = newNode(hash, key, value, null);
        else {
    
      
            // 4.hash定位到的数组位置,是已经有了Node了
            Node<K,V> e; K k;
            // 5.相同的key(会覆盖旧的value)
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
    	// 6.红黑树
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
    
      
    	     // 7.链表
                for (int binCount = 0; ; ++binCount) {
    
      
                    if ((e = p.next) == null) {
    
      
                        p.next = newNode(hash, key, value, null);
                        // 8.如果链表的长度大于等于8的话,链表的总长度达到8的话,那么此时就需要将这个链表转换为一个红黑树的数据结构
                        // 当你遍历到第8个节点,此时binCount是7,同时你挂上了第9个节点,然后就会发现binCount >= 7,达到了临界值,也就是说,当你的链表节点的数量超过8的时候,此时就会将链表转换为红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 相同的key(会覆盖旧的value)
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            // 9.相同的key,覆盖旧的value
            if (e != null) {
    
       // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
}

注意:每次扩容,数组的大小就是2的n次方,只要保证数组的大小是2的n次方,就可以保证说,(n - 1) & hash,可以保证就是hash % 数组.length取模的一样的效果,也就是说通过(n - 1) & hash,就可以将任意一个hash值定位到数组的某个index里去

JDK1.8红黑树优化

如果说出现大量的hash冲突之后,假设某给位置挂的一个链表特别的长,就很恶心了,如果链表长度太长的话,会导致有一些get()操作的时间复杂度就是O(n),正常来说,table[i]数组索引直接定位的方式的话,O(1)

但是如果链表,大量的key冲突,会导致get()操作,性能急剧下降,导致很多的问题

所以说JDK 1.8以后人家优化了这块东西,会判断,如果链表的长度达到8的时候,那么就会将链表转换为红黑树,如果用红黑树的话,get()操作,即使对一个很大的红黑树进行二叉查找,那么时间复杂度会变成O(logn),性能会比链表的O(n)得到大幅度的提升

基于数组扩容原理

hashmap底层是基于数组来实现的核心的数据结构,如果是用数组的话,就天然会有一个问题,就跟ArrayList一样,就是数组如果满了,就必须要扩容,hashmap所以也是有扩容的问题存在的

2倍扩容 + rehash,2倍扩容之后,每个key-value对,都会基于key的hash值取模数组长度重新寻址找到新数组的新的位置

hashmap扩容的原理,数组一次扩容2倍,rehash过程,基于key的hash值重新在新的数组里找到新的位置,很多key在新数组的位置都不一样了,如果是之前冲突的这个key可能就会在新的数组里分布在不同的位置上了

这个原理大体上是JDK 1.7以前的原理,现在的话呢,JDK 1.8以后,都是数组大小是2的n次方扩容,用的是与操作符来实现hash寻址的算法,来进行扩容的时候,rehash

JDK 1.8以后,为了提升rehash这个过程的性能,不是说简单的用key的hash值对新数组.length取模,取模给大家讲过,性能较低,所以JDK 1.8以后hash寻址这块,用的与操作

此时,上面两个hash值会出现hash碰撞的问题,使用链表,或者是红黑树来解决

如果数组的长度扩容之后 = 32,重新对每个hash值进行寻址,也就是用每个hash值跟新数组的length - 1进行与操作

hash2的位置,从原来的5变成了21,规律是什么?

也就是说,JDK 1.8,扩容一定是2的倍数,从16到32到64到128

就可以保证说,每次扩容之后,你的每个hash值要么是停留在原来的那个index的地方,要么是变成了原来的index(5) + oldCap(16) = 21

所以说,这个就是JDK 1.8以后,数组扩容的时候,元素重新寻址的一个过程和原理

如果面试官问你,hashmap的底层原理
(1)hash算法:为什么要高位和低位做异或运算?
(2)hash寻址:为什么是hash值和数组.length - 1进行与运算?
(3)hash冲突的机制:链表,超过8个以后,红黑树
(4)扩容机制:数组2倍扩容,重新寻址(rehash),hash & n - 1,判断二进制结果中是否多出一个bit的1,如果没多,那么就是原来的index,如果多了出来,那么就是index + oldCap,通过这个方式,就避免了rehash的时候,用每个hash对新数组.length取模,取模性能不高,位运算的性能比较高

通过这个方式的话,可以有效的将原来冲突在一个位置的多个key,给分散到新数组的不同的位置去

get()

public V get(Object key) {
    
      
     Node<K,V> e;
     // 1.计算key的hash值
     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 &&
        	// 1.先确定数组下标
            (first = tab[(n - 1) & hash]) != null) {
    
      
    	// 2.如果第一个节点的hash和当前值的hash相等,且值也相等,直接返回
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
    
      
                // 3.如果是红黑树,走红黑树获取节点方法
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
    	     // 4.如果是链表,遍历链表比较
                do {
    
      
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
}

2.LinkedHashMap

LinkedHashMap内部维护了一个双向链表,能保证元素按插入的顺序访问,也能以访问顺序访问,可以用来实现LRU缓存策略。

HashMap,比如你放了一堆key-value对进去,后面的话呢如果你要遍历这个HashMap的话,遍历的顺序,并不是按照你插入的key-value的顺序来的。

LinkedHashMap,他会记录你插入key-value的顺序, 如果你在遍历的时候,他是按照插入key-value对的顺序给你遍历出来的

在这里插入图片描述

核心属性

/**
* 双向链表头结点
*/
transient LinkedHashMap.Entry<K,V> head;

/**
* 双向链表尾结点
*/
transient LinkedHashMap.Entry<K,V> tail;

/**
* 是否按访问顺序排序
*/
final boolean accessOrder;

(1)head双向链表的头节点,旧数据存在头节点。
(2)tail双向链表的尾节点,新数据存在尾节点。
(3)accessOrder是否需要按访问顺序排序,如果为false则按插入顺序存储元素,如果是true则按访问顺序存储元素。

在调用LinkedHashMap的put()方法的时候,其实调用的是父类HashMap的put()方法

newNode()

LinkedHashMap重写了HashMap的newNode()方法

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    
      
        LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<K,V>(hash, key, value, e);
        linkNodeLast(p);
        return p;
}
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    
      
        LinkedHashMap.Entry<K,V> last = tail;
        tail = p;
        // 一开始这个链表里就一个节点,所以tail和head两个指针,都会指向这个p
        if (last == null)
            head = p;
        else {
    
      
            p.before = last;
            last.after = p;
        }
}

LinkedHashMap内部维护了一个双向链表,head(双向链表头结点)、tail(双向链表尾结点)

补充:
HashMap的newNode创建的是HashMap的内部类Node,Node实现了Map.Entry
LinkedHashMap的newNode创建的是LinkedHashMap的内部类Entry,Entry继承了HashMap.Node

afterNodeInsertion

调用完put()方法,插入一个key-value对之后,其实就会调用afterNodeInsertion(evict);,LinkedHashMap重写了afterNodeInsertion(evict)方法

void afterNodeInsertion(boolean evict) {
    
       // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
    
      
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
}

evict:驱逐的意思
(1)如果evict为true,且头节点不为空,且确定移除最老的元素,那么就调用HashMap.removeNode()把头节点移除(这里的头节点是双向链表的头节点,而不是某个桶中的第一个元素);
(2)HashMap.removeNode()从HashMap中把这个节点移除之后,会调用afterNodeRemoval()方法;
(3)afterNodeRemoval()方法在LinkedHashMap中也有实现,用来在移除元素后修改双向链表;
(4)默认removeEldestEntry()方法返回false,也就是不删除元素。

afterNodeAccess

但是如果accessOrder是true的话,那么如果你get一个key,或者是覆盖这个key的值,就会导致个key-value对顺序会在链表里改变,他会被挪动到链表的尾部去,如果你把accessOrder指定为true,你每次修改一个key的值,或者是get访问一下这个key,都会导致这个key挪动到链表的尾部去

补充:可以通过构造器指定accessOrder,默认false

总结
(1)LinkedHashMap继承自HashMap,具有HashMap的所有特性;
(2)LinkedHashMap内部维护了一个双向链表存储所有的元素;
(3)如果accessOrder为false,则可以按插入元素的顺序遍历元素;
(4)如果accessOrder为true,则可以按访问元素的顺序遍历元素;
(5)LinkedHashMap的实现非常精妙,很多方法都是在HashMap中留的钩子(Hook),直接实现这些Hook就可以实现对应的功能了,并不需要再重写put()等方法;
(6)默认的LinkedHashMap并不会移除旧元素,如果需要移除旧元素,则需要重写removeEldestEntry()方法设定移除策略;
(7)LinkedHashMap可以用来实现LRU缓存淘汰策略;

3.TreeMap

TreeMap使用红黑树存储元素,按key的自然顺序来排序。
在这里插入图片描述
TreeMap实现了Map、SortedMap、NavigableMap、Cloneable、Serializable等接口。

public V put(K key, V value) {
    
      
        Entry<K,V> t = root;
        if (t == null) {
    
      
            compare(key, key); // type (and possibly null) check

            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
    
      
            do {
    
      
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
    
      
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable<? super K> k = (Comparable<? super K>) key;
            do {
    
      
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        Entry<K,V> e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
}

TreeMap底层的Entry实现了Map.Entry,里面包含left(左节点)、right(右节点)、parent(父节点)、color(颜色)

三、Set

1.HashSet

比如说HashSet就是基于HashMap来实现的

HashSet,他其实就是说一个集合,里面的元素是无序的,他里面的元素不能重复的,HashMap的key是无顺序的,你插入进去的顺序,跟你迭代遍历的顺序是不一样的,而且HashMap的key是没有重复的,HashSet可以直接基于HashMap来实现

2.LinkedHashSet

LinkedHashSet,他是有顺序的set,也就是维持了插入set的这个顺序,你迭代LinkedHashSet的顺序跟你插入的顺序是一样的,底层直接就可以基于LinkedHashMap来实现

3.TreeSet

TreeSet,默认是根据你插入进去的元素的值来排序的,而且可以定制Comparator,自己决定排序的算法和逻辑,他底层可以基于TreeMap来实现

Set底层的Map,只有key是有值的,value都是null值,都是空的