黑马面试集合(ArrayList, HashMap)篇笔记整理,结尾附Java的集合相关高频面试题及答案

标签：key 面试题 Java HashMap 复杂度链表线程数组集合

集合

操作数据的特点-算法复杂度分析

数据结构

算法复杂度分析

为什么要进行复杂度分析?

指导编写性能更优的代码
评判别人写代码的好坏

时间复杂度分析

时间复杂度分析: 来评估代码的执行耗时的

假设每行代码的执行耗时一样: 1ms
分析这段代码一共执行多少行?

3n + 3
代码耗时总时间: T(n) = (3n + 3) * 1ms

大O表示法: 不具体表示代码真正的执行时间, 而是表示代码执行时间随数据规模增长的变化趋势
T(n)与代码的执行次数成正比(代码行数越多, 执行时间越长)

T(n) = O(3n + 3) —> T(n) = O(n)
当n很大时, 公式中的低阶, 常量, 系数三部分并不左右其增长趋势, 因此可以忽略, 我们只需要记录一个最大的量级就可以了

常见复杂度表示形式

描述	表示形式
常数	O(1)
对数	O(log n)
线性	O(n)
线性对数	O(n * log n)
平方	O(n^2)
立方	O(n^3)
k次方	O(n^k)
指数	O(x^n)
阶乘	O(n!)

速记口诀: 常对幂指阶

常见复杂度

一

public int test01(int n){
    int i=0;
    int j = 1;
    return i+j;
}

时间复杂度: O(1)

public void test02(int n){
    int i=0;
    int sum=0;
    for(;i<100;i++){
        sum = sum+i;
    }
    System.out.println(sum);
}

时间复杂度: O(1)

总结: 只要代码的执行时间不随着n的增大而增大, 这样的代码复杂度就是O(1)

二

public int sum(int n) {
    int sum = 0;
    for ( int i = 1; i <= n; i++) {
        sum = sum + i;
    }
    return sum;
}

时间复杂度: O(n)

public int sum2(int n) {
    int sum = 0;
    for (int i=1; i <= n; ++i) {
        for (int j=1; j <= n; ++j) {
            sum = sum +  i * j;
        }
    }
    return sum;
}

时间复杂度: O(n^2)

三

public void test04(int n){
    int i=1;
    while(i < n){
        i = i * 2;
    }
}

复杂度分析就是要弄清楚代码的执行次数和数据规模n之间的关系

由以上分析可知, 代码的时间复杂度表示为O(log n)

public void test04(int n){
    int i=1;
    while(i < n){
        i = i * 10;
    }
}

时间复杂度: O(log n)

四

public void test05(int n){
    int i=0;
    for(;i<=n;i++){
        test04(n);
    }
}

public void test04(int n){
    int i=1;
    while(i<=n){
        i = i * 2;
    }
}

test05的时间复杂度为O(n)

test04的时间复杂度为O(log n)

两段代码结合在一起的时间复杂度为: O(n * log n)线性对数级

总结

常见的时间复杂度:

O(1)、O(n)、O(n^2)、O(log n)、O(n * log n)

空间复杂度

空间复杂度全称是渐进空间复杂度, 表示算法占用的额外存储空间与数据规模之间的增长关系

public void test(int n){
    int i=0;
    int sum=0;
    for(;i<n;i++){
        sum = sum+i;
    }
    System.out.println(sum);
}

空间复杂度: O(1)

变量已经定义好, 运行时不需要再创建新的变量

void print(int n) {
    int i = 0;
    int[] a = new int[n];
    for (i; i <n; ++i) {
        a[i] = i * i;
    }
    for (i = n-1; i >= 0; --i) {
        System.out.println(a[i]);
    }
}

空间复杂度: O(n)

我们常见的空间复杂度就是O(1)、O(n)、O(n^2), 其他像对数级的复杂度机会用不到, 因此空间复杂度比时间复杂度分析要简单的多.

总结

什么是算法时间复杂度

时间复杂度表示了算法的执行时间与数据规模之间的增长关系
常见的时间复杂度有哪些?

O(1)、O(n)、O(n^2)、O(log n)

速记口诀: 常对幂指阶

描述表示形式
常数 O(1)
对数 O(log n)
线性 O(n)
线性对数 O(n * log n)
平方 O(n^2)
立方 O(n^3)
k次方 O(n^k)
指数 O(x^n)
阶乘 O(n!)
什么是算法的空间复杂度?

表示算法占用的额外存储空间与数据规模之间的增长关系

常见的空间复杂度: O(1)、O(n)、O(n^2)

List

数据结构 - 数组
ArrayList源码分析
⬆️底层实现
ArrayList底层的实现原理是什么
ArrayList list = new ArrayList(10)中的list扩容几次
如何实现数组和List之间的转换
ArrayList和LinkedList的区别是什么?
⬆️面试问题

数组

数组(Array)是一种用连续的内存空间存储相同数据类型数据的线性数据结构

数组如何获取其他元素的地址值?

寻址公式: a[i] = baseAddress + i * dataTypeSize

baseAddress: 数组的首地址
dataTypeSize: 代表数组中元素类型的大小, int型的数据, dataTypeSize是四个字节

为什么数组索引从0开始呢? 假如从1开始不行吗?

原来的寻址公式: a[i] = baseAddress + i * dataTypeSize

新寻址公式: a[i] = baseAddress + (i - 1) * dataTypeSize

对于cpu来说, 增加了一个减法指令

回答面试题:

在根据数组索引获取元素的时候, 会用索引和寻址公式来计算内存所对应的元素数据, 寻址公式是: 数组的首地址 + 索引 * 存储数据的类型大小
如果数组的索引从1开始, 寻址公式中, 就需要增加一次减法操作, 对于CPU来说就多了一次指令, 性能不高

操作数组的时间复杂度(查找)

随机查询(根据索引查询)

数组元素的访问是通过下标来访问的, 计算机通过数组的首地址和寻址公式能够很快速的找到想要访问的元素
```
public int test01(int[] a,int i){
    return a[i];
    // a[i] = baseAddress + i * dataSize
}
```
时间复杂度: O(1)
未知索引查询

情况一: 查找数组内的元素(比如55), 未排序的情况

此时平均的时间复杂度就是O(n)

情况二: 查找排序后数组内的元素(55)

二分查找: O(log n)

操作数组的时间复杂度(插入、删除)

数组是一段连续的内存空间, 因此为了保证数组的连续性会使得数组的插入和删除的效率变得很低.

最好情况(尾操作)下是O(1)的, 最坏情况下是O(n)的, 平均情况下的时间复杂度是O(n).

总结

数组(Array)是一种用连续的内存空间存储相同数据类型数据的线性数据结构.
数组下标为什么从0开始?

寻址公式: baseAddress + i * dataTypeSize, 计算下标的内存地址效率较高
查找的时间复杂度
- 随机(通过下标)查询的时间复杂度是O(1)
- 查找元素(未知下标)的时间复杂度为O(n)
- 查找元素(未知下标但排序)通过二分查找的时间复杂度是O(log n)
插入和删除时间复杂度

插入和删除的时候, 为了保证数组的内存连续性, 需要挪动数组元素, 平均时间复杂度为O(n)

ArrayList源码分析

成员变量

/**
* 默认初始的容量(CAPACITY)
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 用于空实例的共享空数组实例
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 用于默认大小的空实例的共享空数组实例。
* 我们将其与 EMPTY_ELEMENTDATA 区分开来，以了解添加第一个元素时要膨胀多少
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 存储 ArrayList 元素的数组缓冲区。 ArrayList 的容量就是这个数组缓冲区的长度。
* 当添加第一个元素时，任何具有 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空 ArrayList * 都将扩展为 DEFAULT_CAPACITY
 * 当前对象不参与序列化
 */
transient Object[] elementData; // non-private to simplify nested class access
/**
* ArrayList 的大小（它包含的元素数量）
* @serial
*/
private int size;

构造方法

这段代码作用: 将Collection对象转换成数组, 然后将数组的地址的值赋给elementData

添加和扩容操作(第一次添加数据)

添加和扩容操作(第2至10次添加数据)

添加和扩容操作(第11次添加数据)

ArrayList底层的实现原理是什么

ArrayList底层是用动态的数组实现的
ArrayList初始容量为0, 当第一次添加数据的时候才会初始化容量为10
ArrayList在进行扩容的时候是原来容量的1.5倍, 每次扩容都需要拷贝数组
ArrayList在添加数据的时候
- 确保数组已使用长度(size)加1之后足够存下下一个数据
- 计算数组的容量, 如果当前数组已使用长度加1后的长度大于当前的数组长度, 则调用grow方法扩容(原来的1.5倍)
- 确保新增的数据有地方存储之后, 则将新元素添加到位于size的位置上
- 返回添加成功布尔值.

`ArrayList list = new ArrayList(10)`中的`list`扩容几次

/**
* 构造一个具有指定初始容量的空列表。
* 参数：initialCapacity - 列表的初始容量
* 抛出：IllegalArgumentException – 如果指定的初始容量为负
*/
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);
    }
}

参考回答:

该语句只是声明和实例了一个ArrayList, 指定了容量为10, 未进行扩容

如何实现数组和List之间的转换

//数组转List
public static void testArray2List(){
    String[] strs = {"aaa","bbb","ccc"};
    List<String> list = Arrays.asList(strs);
    for (String s : list) {
        System.out.println(s);
    }
}
//List转数组
public static void testList2Array(){
    List<String> list = new ArrayList<String>();
    list.add("aaa");
    list.add("bbb");
    list.add("ccc");
    String[] array = list.toArray(new String[list.size()]);
    for (String s : array) {
        System.out.println(s);
    }
}

参考回答:

数组转List, 使用JDK中java.util.Arrays工具类的asList方法
List转数组, 使用List的toArray方法. 无参toArray方法返回Object数组, 传入初始化长度的数组对象, 返回该对象数组

面试官再问:

用Arrays.asList转List后, 如果修改了数组内容, list会受影响吗
List用toArray转数组后, 如果修改了List内容, 数组会受影响吗

//数组转List
public static void testArray2List(){
    String[] strs = {"aaa","bbb","ccc"};
    List<String> list = Arrays.asList(strs);
    for (String s : list) {
        System.out.println(s);
    }
    strs[1]="ddd";
    System.out.println("================");
    for (String s : list) {
        System.out.println(s);
    }
}
//List转数组
public static void testList2Array(){
    List<String> list = new ArrayList<String>();
    list.add("aaa");
    list.add("bbb");
    list.add("ccc");
    String[] array = list.toArray(new String[list.size()]);
    for (String s : array) {
        System.out.println(s);
    }
    list.add("ddd");
    System.out.println("================");
    for (String s : array) {
        System.out.println(s);
    }
}

Arrays.asList源码:

此处的new ArrayList<>(a)并不是之前见过的ArrayList类, 而是在Arrays当前类中的一个内部类. 这里是调用了内部类的构造方法, 构造方法中有一个方法Objects.requirNonNull(array)这个方法就是判断array是为空, 为空直接报错, 不为空直接复制给成员变量a. 这里只涉及到了成员的引用, 并没有创建对象, 所以用Arrays.asList方法转List之后, 修改数组内容, 集合内容也会随之改变, 指向同一块内存空间

list.toArray源码:

这段代码中的System.arraycopy(elementData, 0, a, 0, size);是将参数a的内容拷贝到新的数组elementData中, 所以这两个是不同的对象, 所以不会受到影响

再答:

Arrays.asList转换list之后, 如果修改了数组的内容, list会受影响, 因为它的底层使用的Arrays类中的一个内部类ArrayList来构造的集合, 在这个集合的构造器中, 把我们传入的这个集合进行了包装而已, 最终指向的都是同一个内存地址
list用了toArray转数组后, 如果修改了list内容, 数组不会影响, 当调用了toArray以后, 在底层是进行了数组的拷贝, 跟原来的元素就没有关系了, 所以即使list修改了以后, 数组也不会受影响.

单向链表

链表中的每一个元素称之为结点(Node)
物理存储单元上, 非连续、非顺序的存储结构
单向链表: 每个结点包括两个部分: 一个是存储数据元素的数据域, 另一个是存储下一个结点地址的指针域. 记录下个结点地址的指针叫做后继指针 next

Java代码实现

private static class Node<E> {
    E item;
    Node<E> next;
    
    Node(E element, Node<E> next) {
        this.item = element;
        this.next = next;
    }
}

链表中的某个结点为B, B的下一个结点为C

表示: B.next == C

单向链表时间复杂度分析

查询

只有在查询头节点的时候不需要遍历链表, 时间复杂度为O(1)
查询其他结点需要遍历链表, 时间复杂度为O(n)

插入/删除操作

只有在添加和删除头节点的时候不需要遍历链表, 时间复杂度是O(1)

添加或删除其他节点需要遍历链表找到对应结点后, 才能完成新增或者删除结点, 时间复杂度是O(n)

双向链表

而双向链表, 顾名思义, 它支持两个方向

每个结点不止有一个后继指针next指向后面的结点
有一个前驱指针prev指向前面的结点

Java代码实现

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

对比单向链表:

双向链表需要额外的两个空间来存储后继节点和前驱节点的地址
支持双向遍历, 这样也带来了双向链表操作的灵活性

双向链表时间复杂度分析

查询

查询头尾节点的时间复杂度是O(1)

平均的查询时间复杂度为O(n)

给定结点找前驱节点的时间复杂度为O(1)

增删操作

头尾结点增删的时间复杂度为O(1)

其他部分结点增删的时间复杂度为O(n)

给定结点增删的时间复杂度为O(1)

单双向链表总结

单向链表和双向链表的区别是什么
- 单向链表只有一个方向, 结点只有一个后继指针next
- 双向链表支持两个方向, 每个结点不止有一个后继指针next指向后面的结点, 还有一个前驱指针prev指向前面的结点
链表操作数据的时间复杂度是多少?

查询/新增删除
单向链表头O(1),其他O(n)
双向链表尾O(1),其他O(n),给定节点O(1)

	查询/新增删除
单向链表	头O(1),其他O(n)
双向链表	尾O(1),其他O(n),给定节点O(1)

ArrayList和LinkedList的区别是什么?

底层数据结构
- ArrayList是动态数组的数据结构实现
- LinkedList是双向链表的数据结构实现
操作数据效率
- ArrayList按照下标查询的时间复杂度为O(1)[内存是连续的, 根据寻址公式查找], LinkedList不支持下标查询
- 查找(未知索引): ArrayList需要遍历, 链表也需要遍历, 时间复杂度都是O(n)
- 新增和删除
  - ArrayList尾部插入和删除, 时间复杂度为O(1); 其他部分增删需要挪动数组, 时间复杂度是O(n)
  - LinkedList头尾节点增删时间复杂度是O(1); 其他都需要遍历链表, 时间复杂度是O(n)
内存空间占用
- ArrayList底层时数组, 内存连续, 节省内存
- LinkedList是双向链表需要存储数据, 和两个指针, 更占用内存
线程安全
- ArrayList和LinkedList都不是线程安全的
- 如果需要保证线程安全, 有两种方案:
  - 在方法内使用, 局部变量则是线程安全的
  - 使用线程安全的ArrayList和LinkedList
```
List<Object> syncArrayList = Collections.synchronizedList(new ArrayList<>());
List<Object> syncLinkedList = Collections.synchronizedList(new LinkedList<>());
```

总结

ArrayList和LinkedList的区别是什么?

底层数据结构
效率
空间
线程是否安全

HashMap

数据结构
- 二叉树
- 红黑树
- 散列表
面试问题
- HashMap实现原理
- HashMap的put方法的具体流程
- HashMap的寻址算法
- 讲一讲HashMap的扩容机制
- 为何HashMap的数组长度一定是2的次幂?
- HashMap在1.7情况下的多线程死循环问题
- HashSet与HashMap的区别
- HashTable与HashMap的区别

二叉树

介绍

二叉树, 顾名思义, 每个节点最多有两个"叉", 也就是两个子节点, 分别是左子节点和右子节点. 不过, 二叉树并不要求每个节点都有两个子节点, 有的节点只有左子节点, 有的节点只有右子节点.

二叉树每个节点的左子树和右子树也分别满足二叉树的定义

Java中有两个方式实现二叉树: 数组存储, 链式存储.

基于链式存储的树的节点可定义如下:

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode() {}

    TreeNode(int val) { 
        this.val = val; 
    }
    
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

二叉搜索树

二叉搜索树(Binary Search Tree, BST)又名二叉查找树, 有序二叉树或者排序二叉树, 是二叉树中比较常用的一种类型

二叉查找树要求, 在树中的任意一个节点, 其左子树的每个节点的值, 都要小于这个节点的值, 而右子树节点的值都要大于这个节点的值

时间复杂度分析

实际上由于二叉查找树的形态各异, 时间复杂度也不尽相同

插入, 查找, 删除的时间复杂度是O(log n)

但是, 二叉查找树的极端情况:

对于图中这种情况属于最坏的情况, 二叉查找树已经退化成了链表, 左右子树极度不平衡, 此时查找的时间复杂度肯定是O(n)

总结

什么是二叉树
- 每个节点最多有两个"叉", 分别是左子节点和右子节点.
- 不要求每个节点都有两个子节点, 有的节点只有左子节点, 有的节点只有右子节点
- 二叉树每个节点的左子树和右子树也分别满足二叉树的定义
什么是二叉搜索树

二叉搜索树(Binary Search Tree, BST)又名二叉查找树, 有序二叉树
在树中的任意一个节点, 其左子树的每个节点的值, 都要小于这个节点的值而右子树结点的值都大于这个节点的值
没有键值相等的节点
通常情况下二叉搜索树的时间复杂度为O(log n)

红黑树

红黑树(Red Black Tree): 也是一种自平衡的二叉搜索树(BST), 之前叫做平衡二叉B树(Symmetric Binary B-Tree)

特质

节点要么是红色, 要么是黑色
根节点是黑色
叶子节点都是黑色的空节点
红黑树中红色节点的子节点都是黑色
从任一节点到叶子节点的所有路径都包含相同数目的黑色节点

在添加或删除节点的时候, 如果不符合这些性质会发生旋转, 以达到所有的性质

时间复杂度

查找:

红黑树也是一棵BST(二叉搜索树)树, 查找操作的时间复杂度为: O(log n)
添加:

添加先要从根节点开始找到元素添加的位置, 时间复杂度O(log n)

添加完成后涉及到复杂度为O(1)的旋转调整操作

故整体复杂度为: O(log n)
删除:

首先从根节点开始找到被删除元素的未知, 时间复杂度O(log n)

删除完成后涉及到复杂度为O(1)的旋转调整操作

故整体复杂度为: O(log n)

总结

什么是红黑树?

红黑树(Red Black Tree): 是一种自平衡的二叉搜索树(BST)
所有的红黑规则都是希望红黑树能够保证平衡
红黑树的时间复杂度: 查找、添加、删除都是O(log n)

散列表

在HashMap中最重要的一个数据结构就是散列表, 在散列表中又使用到了红黑树和链表

散列表(Hash Table)

散列表(Hash Table)又名哈希表/Hash表, 是根据键(Key)直接访问在内存存储位置值(Value)的数据结构, 它是由数组演化而来的, 利用了数组支持按照下标进行随机访问数据的特性

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

假设有100个人参加马拉松, 编号是1-100, 如何编程实现根据选手的编号迅速找到选手信息?

假设有100个人参加马拉松, 不采用1-100的自然数对选手进行编号, 编号有一定的规则比如: 2023ZHBJ001, 其中2023代表年份, ZH代表中国, BJ代表北京, 001代表原来的编号, 那此时的编号2023ZHBJ001不能直接作为数组的下标, 此时应该如何实现呢?

将键(Key)映射为数组下标的函数叫做散列函数. 可表示为: hashValue = hash(key)

散列函数的基本要求:

散列函数计算得到的散列值必须是大于等于0的正整数, 因为hashValue需要作为数组的下标
如果Key1 == Key2, 那么经过Hash后得到的哈希值也必相同即: hash(key1) == hash(key2)
如果key1 != key2, 那么经过Hash后得到的哈希值也必不相同即: hash(key1) != hash(key2)

散列冲突

实际的情况下想要找一个散列函数能够做到对于不同的key计算得到的散列值都不同几乎是不可能的, 即便像著名的MD5, SHA等哈希算法也无法避免这一情况, 这就是散列冲突(或者哈希冲突, 哈希碰撞, 就是指多个key映射到同一个数组下标位置)

链表法(拉链)

在散列表中, 数组的每个下标位置我们可以称之为桶(bucket)或者槽(slot), 每个桶(槽)会对应一条链表, 所有散列值相同的元素我们都放到相同槽位对应的链表中.

时间复杂度

插入操作, 通过散列函数计算出对应的散列槽位, 对其插入到对应链表中即可, 插入的时间复杂度为O(1)
当查找、删除一个元素时, 我们同样通过散列函数计算出对应的槽, 然后遍历链表查找或者删除
- 平均情况下基于链表法解决冲突时查询的时间复杂度是O(1)
- 散列表可能会退化为链表, 查询的时间复杂度就从O(1)退化为O(n)
- 将链表法中的链表改造为其他高效的动态数据结构, 比如红黑树, 查询的时间复杂度是O(log n)

将链表法中的链表改造红黑树还有一个非常重要的原因, 可以防止DDos攻击

DDos攻击

分布式拒绝服务攻击(英文意思是Distributed Denial of Service, 简称DDoS)

指处于不同位置的多个攻击者同时向一个或数个目标发动攻击, 或者一个攻击者控制了位于不同位置的多台机器并利用这些机器对受害者同时实施攻击. 由于攻击的发出点是分布在不同地方的, 这类攻击称为分布式拒绝服务攻击, 其中的攻击者可以有多个

总结

什么是散列表?
- 散列表(Hash Table)又名哈希表/Hash表
- 根据键(key)直接访问在内存存储位置值(Value)的数据结构
- 由数组演化而来的, 利用了数组支持按照下标进行随机访问数据
散列冲突
- 散列冲突又称哈希冲突, 哈希碰撞
- 指多个key映射到同一个数组下标位置
散列冲突-链表法(拉链)
- 数组的每个下标位置称之为桶(bucket)或者槽(slot)
- 每个桶(槽)会对应一条链表
- Hash冲突后的元素都放到相同槽位对应的链表中或红黑树中

HashMap实现原理

HashMap的数据结构: 底层使用Hash表数据结构, 即数组和链表或红黑树

当我们往HashMap中put元素时, 利用key的hashCode重新Hash计算出当前对象的元素在数组中的下标
存储时, 如果出现Hash值相同的key, 此时有两种情况.
1. 如果key相同, 则覆盖原始值;
2. 如果key不相同(出现冲突), 则将当前的key-value放入链表或红黑树中
获取时, 直接找到Hash值对应的下标, 再进一步判断key是否相同, 从而找到对应值

面试官追问: HashMap的JDK1.7和JDK1.8有什么区别?

HashMap的JDK1.7和JDK1.8有什么区别?

JDK1.8之前采用的是拉链法. 拉链法: 将链表和数组相结合. 也就是说创建一个链表数组, 数组中每一格就是一个链表. 若遇到哈希冲突, 则将冲突的值加到链表中即可
JDK1.8在解决哈希冲突时有了较大的变化, 当链表长度大于阈值(默认为8)并且数组长度达到64时, 将链表转换为红黑树, 以减少搜索时间. 扩容resize()时, 红黑树拆分成的树的节点数小于等于临界值6个, 则退化成链表

总结

说一下HashMap的实现原理
- 底层使用Hash表数据结构, 即数组 + (链表 | 红黑树)
- 添加数据时, 计算key的值确定元素在数组中的下标
  - key相同则替换
  - 不同则存入链表或红黑树中
- 获取数据通过key的Hash计算数组下标获取元素
HashMap的JDK1.7和JDK1.8有什么区别
- JDK1.8之前, 老元素挂在新元素后面, 采用的拉链法, 数组 + 链表
- JDK1.8之后, 新元素直接挂在老元素后面, 采用数组 + 链表 + 红黑树, 链表长度大于8且数组长度大于64则会从链表转化为红黑树

HashMap的`put`方法的具体流程

HashMap源码分析

常见属性

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;
transient HashMap.Node<K,V>[] table;
transient int size;

DEFAULT_INITIAL_CAPACITY: 默认的初始容量
DEFAULT_LOAD_FACTOR: 默认的加载因子
扩容阈值 == 数组容量 * 加载因子

transient HashMap.Node<K,V>[] table;:

static class Node<K, V> implements Map.Entry<K, V> {
    final int hash;
    final K key;
    V value;
    HashMap.Node<K, V> next;
    
    Node(int hash, K key, V value, HashMap.Node<K, V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

HashMap是懒惰加载, 在创建对象时并没有初始化数组
在无参的构造函数中, 设置了默认的加载因子是0.75

添加数据

添加数据流程图:

源码:

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;
    //判断数组是否未初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        //如果未初始化，调用resize方法 进行初始化
        n = (tab = resize()).length;
    //通过 & 运算求出该数据（key）的数组下标并判断该下标位置是否有数据
    if ((p = tab[i = (n - 1) & hash]) == null)
        //如果没有，直接将数据放在该下标位置
        tab[i] = newNode(hash, key, value, null);
    //该数组下标有数据的情况
    else {
        Node<K,V> e; K k;
        //判断该位置数据的key和新来的数据是否一样
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            //如果一样，证明为修改操作，该节点的数据赋值给e,后边会用到
            e = p;
        //判断是不是红黑树
        else if (p instanceof TreeNode)
            //如果是红黑树的话，进行红黑树的操作
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //新数据和当前数组既不相同，也不是红黑树节点，证明是链表
        else {
            //遍历链表
            for (int binCount = 0; ; ++binCount) {
                //判断next节点，如果为空的话，证明遍历到链表尾部了
                if ((e = p.next) == null) {
                    //把新值放入链表尾部
                    p.next = newNode(hash, key, value, null);
                    //因为新插入了一条数据，所以判断链表长度是不是大于等于8
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        //如果是，进行转换红黑树操作
                        treeifyBin(tab, hash);
                    break;
                }
                //判断链表当中有数据相同的值，如果一样，证明为修改操作
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                //把下一个节点赋值为当前节点
                p = e;
            }
        }
        //判断e是否为空（e值为修改操作存放原数据的变量）
        if (e != null) { // existing mapping for key
            //不为空的话证明是修改操作，取出老值
            V oldValue = e.value;
            //一定会执行  onlyIfAbsent传进来的是false
            if (!onlyIfAbsent || oldValue == null)
                //将新值赋值当前节点
                e.value = value;
            afterNodeAccess(e);
            //返回老值
            return oldValue;
        }
    }
    //计数器，计算当前节点的修改次数
    ++modCount;
    //当前数组中的数据数量如果大于扩容阈值
    if (++size > threshold)
        //进行扩容操作
        resize();
    //空方法
    afterNodeInsertion(evict);
    //添加操作时 返回空值
    return null;
}

面试官: HashMap的`put`方法的具体流程

判断键值对数组table是否为空或者为null, 否咋执行resize()进行扩容(初始化)
根据键值key计算Hash值得到数组索引
判断table[i] == null, 条件成立, 直接新建节点添加
如果table[i] == null, 不成立
1. 判断table[i]的首个元素是否和key一样,如果相同直接覆盖value
2. 判断table[i]是否为treeNode, 即table[i]是否是红黑树, 如果是红黑树, 则直接在树中插入键值对
3. 遍历table[i], 链表的尾部插入数据, 然后判断链表长度是否大于8, 大于8的话吧链表转换为红黑树, 在红黑树中执行插入操作, 遍历过程中若发现key已经存在直接覆盖value
插入成功后, 判断实际存在的键值对数量size是否超过了最大容量threshold(数组长度*0.75), 如果超过, 进行扩容

HashMap的扩容机制

源码分析-扩容

扩容的流程:

源码:

//扩容、初始化数组
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    //如果当前数组为null的时候，把oldCap老数组容量设置为0
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //老的扩容阈值
    int oldThr = threshold;
    int newCap, newThr = 0;
    //判断数组容量是否大于0，大于0说明数组已经初始化
    if (oldCap > 0) {
        //判断当前数组长度是否大于最大数组长度
        if (oldCap >= MAXIMUM_CAPACITY) {
            //如果是，将扩容阈值直接设置为int类型的最大数值并直接返回
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //如果在最大长度范围内，则需要扩容  OldCap << 1等价于oldCap*2
        //运算过后判断是不是最大值并且oldCap需要大于16
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold  等价于oldThr*2
    }
    //如果oldCap<0，但是已经初始化了，像把元素删除完之后的情况，那么它的临界值肯定还存在，       			如果是首次初始化，它的临界值则为0
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    //数组未初始化的情况，将阈值和扩容因子都设置为默认值
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //初始化容量小于16的时候，扩容阈值是没有赋值的
    if (newThr == 0) {
        //创建阈值
        float ft = (float)newCap * loadFactor;
        //判断新容量和新阈值是否大于最大容量
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    //计算出来的阈值赋值
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    //根据上边计算得出的容量 创建新的数组       
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    //赋值
    table = newTab;
    //扩容操作，判断不为空证明不是初始化数组
    if (oldTab != null) {
        //遍历数组
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            //判断当前下标为j的数组如果不为空的话赋值个e，进行下一步操作
            if ((e = oldTab[j]) != null) {
                //将数组位置置空
                oldTab[j] = null;
                //判断是否有下个节点
                if (e.next == null)
                    //如果没有，就重新计算在新数组中的下标并放进去
                    newTab[e.hash & (newCap - 1)] = e;
                //有下个节点的情况，并且判断是否已经树化
                else if (e instanceof TreeNode)
                    //进行红黑树的操作
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                //有下个节点的情况，并且没有树化（链表形式）
                else {
                    //比如老数组容量是16，那下标就为0-15
                    //扩容操作*2，容量就变为32，下标为0-31
                    //低位：0-15，高位16-31
                    //定义了四个变量
                    //        低位头          低位尾
                    Node<K,V> loHead = null, loTail = null;
                    //        高位头		   高位尾
                    Node<K,V> hiHead = null, hiTail = null;
                    //下个节点
                    Node<K,V> next;
                    //循环遍历
                    do {
                        //取出next节点
                        next = e.next;
                        //通过 与操作 计算得出结果为0
                        if ((e.hash & oldCap) == 0) {
                            //如果低位尾为null，证明当前数组位置为空，没有任何数据
                            if (loTail == null)
                                //将e值放入低位头
                                loHead = e;
                            //低位尾不为null，证明已经有数据了
                            else
                                //将数据放入next节点
                                loTail.next = e;
                            //记录低位尾数据
                            loTail = e;
                        }
                        //通过 与操作 计算得出结果不为0
                        else {
                            //如果高位尾为null，证明当前数组位置为空，没有任何数据
                            if (hiTail == null)
                                //将e值放入高位头
                                hiHead = e;
                            //高位尾不为null，证明已经有数据了
                            else
                                //将数据放入next节点
                                hiTail.next = e;
                            //记录高位尾数据
                            hiTail = e;
                        }

                    } 
                    //如果e不为空，证明没有到链表尾部，继续执行循环
                    while ((e = next) != null);
                    //低位尾如果记录的有数据，是链表
                    if (loTail != null) {
                        //将下一个元素置空
                        loTail.next = null;
                        //将低位头放入新数组的原下标位置
                        newTab[j] = loHead;
                    }
                    //高位尾如果记录的有数据，是链表
                    if (hiTail != null) {
                        //将下一个元素置空
                        hiTail.next = null;
                        //将高位头放入新数组的(原下标+原数组容量)位置
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    //返回新的数组对象
    return newTab;
}

面试官: 讲一讲HashMap的扩容机制

在添加元素或初始化的时候需要调用resize方法进行扩容, 第一次添加数据初始化数组长度为16, 以后每次扩容都是达到了扩容阈值(数组长度 * 0.75)
每次扩容的时候, 都是扩容之前容量的2倍;
扩容之后, 会新创建一个数组, 需要把老数组中的数据挪动到新的数组中
- 没有Hash冲突的节点, 则直接使用e.hash & (newCap -1)计算新数组的索引位置
- 如果是红黑树, 走红黑树的添加逻辑
- 如果是链表, 则需要遍历链表, 可能需要拆分链表, 判断e.hash & oldCap是否为0, 该元素的位置要么停留在原始位置, 要么移动到原始位置 + 增加的数组大小这个位置上

HashMap源码分析–动画演示

来自黑马Java研究院-满一航老师

hash-demo.jar

运行需要JDK14以上环境,进入jar包目录, 执行下面命令

java -jar --add-exports java.base/jdk.internal.misc=ALL-UNNAMED hash-demo.jar

HashMap的寻址算法

put源码:

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

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

(h = key.hashCode()) ^ (h >>> 16)扰动算法, 使Hash值更均匀, 减少Hash冲突

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    ……;
    if ((p = tab[i = (n - 1) & hash]) == null)
        ……;
}

(n - 1) & hash: 得到数组中的索引, 代替取模, 性能更好, 数组长度必须是2的n次幂

为何HashMap的数组长度一定是2的次幂?

计算索引时效率更高: 如果是2的n次幂可以使用位于运算代替取模
扩容时重新计算索引效率更高: hash & oldCap == 0的元素留在原来位置, 否在新位置 = 旧位置 + oldCap

总结

HashMap的寻址算法
- 计算对象的hashCode()
- 再进行调用hash()方法进行二次哈希, hashCode值右移16位再异或运算, 让哈希分布更为均匀
- 最后(capacity - 1) & hash得到索引
为何HashMap的数组长度一定是2的次幂
- 计算索引时效率更高: 如果是2的n次幂可以使用位于运算代替取模
- 扩容时重新计算索引效率更高: hash & oldCap == 0的元素留在原来的位置, 否则新位置 = 旧位置 + oldCap

HashMap在1.7情况下的多线程死循环问题

JDK7的数据结构是: 数组 + 链表

在数组进行扩容的时候, 因为链表是头插法,在进行数据迁移的过程中, 有可能导致死循环

链表迁移源码:

变量e指向的是需要迁移的对象
变量next指向的是下一个需要迁移的对象
JDK1.7中的链表采用的头插法
在数据迁移的过程中并没有新的对象产生, 只是改变了对象的引用

线程1和线程2的变量e和next都引用了这个两个节点

线程2扩容后, 由于头插法, 链表顺序颠倒, 但是线程1的临时变量e和next还引用了这两个节点

由于线程2迁移的时候, 已经把B的next指向了A

此时在线程1中, A指向了B, 同时B也指向了A

参考回答

在JDK1.7的HashMap中在数组进行扩容的时候, 因为链表是头插法, 在进行数据迁移的过程中, 有可能导致死循环

比如说, 现在有两个线程

线程一: 读取到当前的HashMap数据, 数据中一个链表, 在进行扩容时, 线程二介入

线程二: 也读取HashMap, 直接进行扩容. 因为是头插法, 链表的顺序会进行颠倒过来. 比如原来的顺序是AB, 扩容后的顺序是BA, 线程二执行结束.

线程一: 继续执行的时候就会出现死循环的问题.

线程一先将A移入新的链表, 再将B插入到链表头, 由于另一个线程的原因, B的next指向了A, 所以B -> A -> B, 形成循环.

当然, JDK8将扩容算法做了调整, 不再将元素加入链表头(而是保持与扩容前一样的顺序), 尾插法, 就避免了JDK7中死循环的问题

HashSet与HashMap的区别

(1)HashSet实现了Set接口, 仅存储对象; HashMap实现了 Map接口, 存储的是键值对.

(2)HashSet底层其实是用HashMap实现存储的, HashSet封装了一系列HashMap的方法. 依靠HashMap来存储元素值,(利用hashMap的key键进行存储), 而value值默认为Object对象. 所以HashSet也不允许出现重复值, 判断标准和HashMap判断标准相同, 两个元素的hashCode相等并且通过equals()方法返回true.

HashTable与HashMap的区别

主要区别：

区别	HashTable	HashMap
数据结构	数组+链表	数组+链表+红黑树
是否可以为null	Key和value都不能为null	可以为null
hash算法	key的hashCode()	二次hash
扩容方式	当前容量翻倍 +1	当前容量翻倍
线程安全	同步(synchronized)的，线程安全	非线程安全

在实际开中不建议使用HashTable，在多线程环境下可以使用ConcurrentHashMap类

真实面试还原

Java常见的集合类

面试官：说一说Java提供的常见集合？（画一下集合结构图）

候选人：

嗯~~，好的。

在java中提供了量大类的集合框架，主要分为两类：

第一个是Collection 属于单列集合，第二个是Map 属于双列集合

在Collection中有两个子接口List和Set。在我们平常开发的过程中用的比较多像list接口中的实现类ArrarList和LinkedList。在Set接口中有实现类HashSet和TreeSet。
在map接口中有很多的实现类，平时比较常见的是HashMap、TreeMap，还有一个线程安全的map:ConcurrentHashMap

List

面试官：ArrayList底层是如何实现的？

候选人：

嗯~，我阅读过arraylist的源码，我主要说一下add方法吧

第一：确保数组已使用长度（size）加1之后足够存下下一个数据

第二：计算数组的容量，如果当前数组已使用长度+1后的大于当前的数组长度，则调用grow方法扩容（原来的1.5倍）

第三：确保新增的数据有地方存储之后，则将新元素添加到位于size的位置上。

第四：返回添加成功布尔值。

面试官：ArrayList list=new ArrayList(10)中的list扩容几次

候选人：

是new了一个ArrarList并且给了一个构造参数10，对吧？(问题一定要问清楚再答)

面试官：是的

候选人：

好的，在ArrayList的源码中提供了一个带参数的构造方法，这个参数就是指定的集合初始长度，所以给了一个10的参数，就是指定了集合的初始长度是10，这里面并没有扩容。

面试官：如何实现数组和List之间的转换

候选人：

嗯，这个在我们平时开发很常见

数组转list，可以使用jdk自动的一个工具类Arrars，里面有一个asList方法可以转换为数组

List 转数组，可以直接调用list中的toArray方法，需要给一个参数，指定数组的类型，需要指定数组的长度。

面试官：用Arrays.asList转List后，如果修改了数组内容，list受影响吗？List用toArray转数组后，如果修改了List内容，数组受影响吗

候选人：

Arrays.asList转换list之后，如果修改了数组的内容，list会受影响，因为它的底层使用的Arrays类中的一个内部类ArrayList来构造的集合，在这个集合的构造器中，把我们传入的这个集合进行了包装而已，最终指向的都是同一个内存地址

list用了toArray转数组后，如果修改了list内容，数组不会影响，当调用了toArray以后，在底层是它是进行了数组的拷贝，跟原来的元素就没啥关系了，所以即使list修改了以后，数组也不受影响

面试官：ArrayList 和 LinkedList 的区别是什么？

候选人：

嗯，它们两个主要是底层使用的数据结构不一样，ArrayList 是动态数组，LinkedList 是双向链表，这也导致了它们很多不同的特点。

1，从操作数据效率来说

ArrayList按照下标查询的时间复杂度O(1)【内存是连续的，根据寻址公式】， LinkedList不支持下标查询

查找（未知索引）： ArrayList需要遍历，链表也需要链表，时间复杂度都是O(n)

新增和删除

ArrayList尾部插入和删除，时间复杂度是O(1)；其他部分增删需要挪动数组，时间复杂度是O(n)
LinkedList头尾节点增删时间复杂度是O(1)，其他都需要遍历链表，时间复杂度是O(n)

2，从内存空间占用来说

ArrayList底层是数组，内存连续，节省内存

LinkedList 是双向链表需要存储数据，和两个指针，更占用内存

3，从线程安全来说，ArrayList和LinkedList都不是线程安全的

面试官：嗯，好的，刚才你说了ArrayList 和 LinkedList 不是线程安全的，你们在项目中是如何解决这个的线程安全问题的？

候选人：

嗯，是这样的，主要有两种解决方案：

第一：我们使用这个集合，优先在方法内使用，定义为局部变量，这样的话，就不会出现线程安全问题。

第二：如果非要在成员变量中使用的话，可以使用线程安全的集合来替代

ArrayList可以通过Collections 的 synchronizedList 方法将 ArrayList 转换成线程安全的容器后再使用。

LinkedList 换成ConcurrentLinkedQueue来使用

HashMap

面试官：说一下HashMap的实现原理？

候选人：

嗯。它主要分为了一下几个部分：

1，底层使用hash表数据结构，即数组+（链表 | 红黑树）

2，添加数据时，计算key的值确定元素在数组中的下标

key相同则替换

不同则存入链表或红黑树中

3，获取数据通过key的hash计算数组下标获取元素

面试官：HashMap的jdk1.7和jdk1.8有什么区别

候选人：

JDK1.8之前采用的拉链法，数组+链表

JDK1.8之后采用数组+链表+红黑树，链表长度大于8且数组长度大于64则会从链表转化为红黑树

面试官：好的，你能说下HashMap的put方法的具体流程吗？

候选人：

嗯好的。

判断键值对数组table是否为空或为null，否则执行resize()进行扩容（初始化）

根据键值key计算hash值得到数组索引

判断table[i]==null，条件成立，直接新建节点添加

如果table[i]==null ,不成立

4.1 判断table[i]的首个元素是否和key一样，如果相同直接覆盖value

4.2 判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对

4.3 遍历table[i]，链表的尾部插入数据，然后判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，遍历过程中若发现key已经存在直接覆盖value

插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold（数组长度*0.75），如果超过，进行扩容。

面试官：好的，刚才你多次介绍了hsahmap的扩容，能讲一讲HashMap的扩容机制吗？

候选人：

好的

在添加元素或初始化的时候需要调用resize方法进行扩容，第一次添加数据初始化数组长度为16，以后每次每次扩容都是达到了扩容阈值（数组长度 * 0.75）

每次扩容的时候，都是扩容之前容量的2倍；

扩容之后，会新创建一个数组，需要把老数组中的数据挪动到新的数组中

没有hash冲突的节点，则直接使用 e.hash & (newCap - 1) 计算新数组的索引位置

如果是红黑树，走红黑树的添加

如果是链表，则需要遍历链表，可能需要拆分链表，判断(e.hash & oldCap)是否为0，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上

面试官：好的，刚才你说的通过hash计算后找到数组的下标，是如何找到的呢，你了解hashMap的寻址算法吗？

候选人：

这个哈希方法首先计算出key的hashCode值，然后通过这个hash值右移16位后的二进制进行按位异或运算得到最后的hash值。

在putValue的方法中，计算数组下标的时候使用hash值与数组长度取模得到存储数据下标的位置，hashmap为了性能更好，并没有直接采用取模的方式，而是使用了数组长度-1 得到一个值，用这个值按位与运算hash值，最终得到数组的位置。

面试官：为何HashMap的数组长度一定是2的次幂？

候选人：

嗯，好的。hashmap这么设计主要有两个原因：

第一：

计算索引时效率更高：如果是 2 的 n 次幂可以使用位与运算代替取模

第二：

扩容时重新计算索引效率更高：在进行扩容是会进行判断 hash值按位与运算旧数组长租是否 == 0

如果等于0，则把元素留在原来位置，否则新位置是等于旧位置的下标+旧数组长度

面试官：好的，我看你对hashmap了解的挺深入的，你知道hashmap在1.7情况下的多线程死循环问题吗？

候选人：

嗯，知道的。是这样

jdk7的的数据结构是：数组+链表

在数组进行扩容的时候，因为链表是头插法，在进行数据迁移的过程中，有可能导致死循环

比如说，现在有两个线程

线程一：读取到当前的hashmap数据，数据中一个链表，在准备扩容时，线程二介入

线程二也读取hashmap，直接进行扩容。因为是头插法，链表的顺序会进行颠倒过来。比如原来的顺序是AB，扩容后的顺序是BA，线程二执行结束。

当线程一再继续执行的时候就会出现死循环的问题。

线程一先将A移入新的链表，再将B插入到链头，由于另外一个线程的原因，B的next指向了A，所以B->A->B,形成循环。

当然，JDK 8 将扩容算法做了调整，不再将元素加入链表头（而是保持与扩容前一样的顺序），尾插法，就避免了jdk7中死循环的问题。

面试官：好的，hashmap是线程安全的吗？

候选人：不是线程安全的

面试官：那我们想要使用线程安全的map该怎么做呢？

候选人：我们可以采用ConcurrentHashMap进行使用，它是一个线程安全的HashMap

面试官：那你能聊一下ConcurrentHashMap的原理吗？

候选人：好的，请参考《多线程相关面试题》中的ConcurrentHashMap部分的讲解

面试官：HashSet与HashMap的区别？

候选人：嗯，是这样。

HashSet底层其实是用HashMap实现存储的, HashSet封装了一系列HashMap的方法. 依靠HashMap来存储元素值,(利用hashMap的key键进行存储), 而value值默认为Object对象. 所以HashSet也不允许出现重复值, 判断标准和HashMap判断标准相同, 两个元素的hashCode相等并且通过equals()方法返回true.

面试官：HashTable与HashMap的区别

候选人：

嗯，他们的主要区别是有几个吧

第一，数据结构不一样，hashtable是数组+链表，hashmap在1.8之后改为了数组+链表+红黑树

第二，hashtable存储数据的时候都不能为null，而hashmap是可以的

第三，hash算法不同，hashtable是用本地修饰的hashcode值，而hashmap经常了二次hash

第四，扩容方式不同，hashtable是当前容量翻倍+1，hashmap是当前容量翻倍

第五，hashtable是线程安全的，操作数据的时候加了锁synchronized，hashmap不是线程安全的，效率更高一些

在实际开中不建议使用HashTable，在多线程环境下可以使用ConcurrentHashMap类
p的数组长度一定是2的次幂？

候选人：

嗯，好的。hashmap这么设计主要有两个原因：

第一：

计算索引时效率更高：如果是 2 的 n 次幂可以使用位与运算代替取模

第二：

扩容时重新计算索引效率更高：在进行扩容是会进行判断 hash值按位与运算旧数组长租是否 == 0

如果等于0，则把元素留在原来位置，否则新位置是等于旧位置的下标+旧数组长度

面试官：好的，我看你对hashmap了解的挺深入的，你知道hashmap在1.7情况下的多线程死循环问题吗？

候选人：

嗯，知道的。是这样

jdk7的的数据结构是：数组+链表

在数组进行扩容的时候，因为链表是头插法，在进行数据迁移的过程中，有可能导致死循环

比如说，现在有两个线程

线程一：读取到当前的hashmap数据，数据中一个链表，在准备扩容时，线程二介入

线程二也读取hashmap，直接进行扩容。因为是头插法，链表的顺序会进行颠倒过来。比如原来的顺序是AB，扩容后的顺序是BA，线程二执行结束。

当线程一再继续执行的时候就会出现死循环的问题。

线程一先将A移入新的链表，再将B插入到链头，由于另外一个线程的原因，B的next指向了A，所以B->A->B,形成循环。

当然，JDK 8 将扩容算法做了调整，不再将元素加入链表头（而是保持与扩容前一样的顺序），尾插法，就避免了jdk7中死循环的问题。

面试官：好的，hashmap是线程安全的吗？

候选人：不是线程安全的

面试官：那我们想要使用线程安全的map该怎么做呢？

候选人：我们可以采用ConcurrentHashMap进行使用，它是一个线程安全的HashMap

面试官：那你能聊一下ConcurrentHashMap的原理吗？

候选人：好的，请参考《多线程相关面试题》中的ConcurrentHashMap部分的讲解

面试官：HashSet与HashMap的区别？

候选人：嗯，是这样。

HashSet底层其实是用HashMap实现存储的, HashSet封装了一系列HashMap的方法. 依靠HashMap来存储元素值,(利用hashMap的key键进行存储), 而value值默认为Object对象. 所以HashSet也不允许出现重复值, 判断标准和HashMap判断标准相同, 两个元素的hashCode相等并且通过equals()方法返回true.

面试官：HashTable与HashMap的区别

候选人：

嗯，他们的主要区别是有几个吧

第一，数据结构不一样，hashtable是数组+链表，hashmap在1.8之后改为了数组+链表+红黑树

第二，hashtable存储数据的时候都不能为null，而hashmap是可以的

第三，hash算法不同，hashtable是用本地修饰的hashcode值，而hashmap经常了二次hash

第四，扩容方式不同，hashtable是当前容量翻倍+1，hashmap是当前容量翻倍

第五，hashtable是线程安全的，操作数据的时候加了锁synchronized，hashmap不是线程安全的，效率更高一些

在实际开中不建议使用HashTable，在多线程环境下可以使用ConcurrentHashMap类

标签：key,面试题,Java,HashMap,复杂度,链表,线程,数组,集合
From： https://blog.csdn.net/m0_68998179/article/details/142203801

黑马面试集合(ArrayList, HashMap)篇笔记整理,结尾附Java的集合相关高频面试题及答案

集合

数据结构

算法复杂度分析

时间复杂度分析

常见复杂度表示形式

常见复杂度

一

二

三

四

总结

空间复杂度

总结

List

数组

数组如何获取其他元素的地址值?

为什么数组索引从0开始呢? 假如从1开始不行吗?

操作数组的时间复杂度(查找)

操作数组的时间复杂度(插入、删除)

总结

ArrayList源码分析

成员变量

构造方法

添加和扩容操作(第一次添加数据)

添加和扩容操作(第2至10次添加数据)

添加和扩容操作(第11次添加数据)

ArrayList底层的实现原理是什么

ArrayList list = new ArrayList(10)中的list扩容几次

如何实现数组和List之间的转换

单向链表

单向链表时间复杂度分析

查询

插入/删除操作

双向链表

双向链表时间复杂度分析

查询

增删操作

单双向链表总结

ArrayList和LinkedList的区别是什么?

总结

HashMap

二叉树

介绍

分类

二叉搜索树

时间复杂度分析

总结

红黑树

特质

时间复杂度

总结

散列表

散列表(Hash Table)

散列冲突

链表法(拉链)

时间复杂度

总结

HashMap实现原理

HashMap的JDK1.7和JDK1.8有什么区别?

总结

HashMap的put方法的具体流程

HashMap源码分析

常见属性

添加数据

面试官: HashMap的put方法的具体流程

HashMap的扩容机制

源码分析-扩容

面试官: 讲一讲HashMap的扩容机制

HashMap源码分析–动画演示

HashMap的寻址算法

为何HashMap的数组长度一定是2的次幂?

总结

HashMap在1.7情况下的多线程死循环问题

参考回答

HashSet与HashMap的区别

HashTable与HashMap的区别

真实面试还原

Java常见的集合类

List

`ArrayList list = new ArrayList(10)`中的`list`扩容几次

HashMap的`put`方法的具体流程

面试官: HashMap的`put`方法的具体流程