标签：扩容 Java HashMap ArrayList 链表数组集合节点

List

ArrayList和LinkedList有什么区别？

数据结构不同，ArrayList基于数组实现，LinkedList基于双向链表实现
使用场景不同，ArrayList用于查多写少的场景，LinkedList多用于写多查少的场景
1. 查询：
  1. ArrayList支持随机访问，可以通过下标直接获取元素，时间复杂度是O(1)
  2. LinkedList需要遍历链表，时间复杂度是O(n)
2. 增删：
  1. ArrayList需要把插入位置、删除位置之后的所有元素往前或往后移动，甚至可能触发扩容
  2. ArrayList只要找到修改的元素，改变前驱节点、后继节点的指向就可以了
内存占用：都有一些额外的消耗，但是具体不一样
1. ArrayList基于数组实现，是一块连续的内存空间，预先定义好数组长度后存在一定空间浪费
2. LinkedList的每个节点需要存储前驱节点和后继节点，会占用更多空间

ArrayList扩容机制

ArrayList基于数组实现，数组的容量在定义时就确定了，如果数组满了再插入就会有数组越界异常，所以ArrayList在执行插入前会先检查数组是否已满，如果是则触发扩容
ArrayList的扩容就是创建一个1.5倍的新数组，把原值拷贝过去

讲一下集合遍历过程中并发发生修改的失败机制（快速失败、安全失败）

快速失败（fail - fast）：
- A线程在使用迭代器遍历集合对象时，线程B对该对象进行修改，则会抛出并发修改异常（Concurrent Modification Exception）
- 举例：ArrayList
- 原理：遍历过程中使用一个modCount变量，集合如果在遍历期间内容发生变化，就会改变modCount的值。当迭代器使用hasNext()或next()方法遍历下一个元素之前，都会检测modCount是否为expectedModCount，不是的话则抛出异常，终止遍历。CAS有个弊端就是如果modCount修改后还是等于原值，就不会抛出异常。
安全失败（fail - safe）：
- 在遍历时先复制原有集合内容，在拷贝的集合上进行遍历
- 举例：CopyOnWriteArrayList

有哪几种实现ArrayList线程安全的方法？

使用CopyOnWriteArrayList代替ArrayList
使用Collections.synchronizedList包装ArrayList
自己实现同步机制控制ArrayList的读写
使用Vector代替ArrayList（不推荐，Vector时一个历史遗留类）

说一说CopyOnWriteArrayList

CopyOnWriteArrayList就是线程安全版的ArrayList，实现原理就是CopyOnWrite（写时复制）
CopyOnWriteArrayList是一种读写分离的并发策略
- 读的时候是没有锁的，性能较高
- 写的时候会加锁，然后将当前容器复制一份，在副本上执行写操作结束后再将对象引用指向新容器

// CopyOnWriteArrayList的add方法
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

Set

HashSet的底层实现

HashSet是基于HashMap实现，没什么好深究的

put方法

// HashSet成员变量
private transient HashMap<E,Object> map;

// add方法
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

HashMap(重点）

HashMap初始化

HashMap是Map的实现，默认加载因子是0.75，默认初始容量16，每次扩容容量是原来的2倍

为什么默认加载因子是0.75？

扩容是非常耗时的操作，加载因子0.75是时间和空间综合考虑后的一个结果
如果是0.5的话有一半内存空值，造成内存浪费
如果是1.0的话当发生扩容时，已经发生了太多哈希冲突，查找时间成本增加了

为什么HashMap的容量是2的倍数、扩容也是原来的2倍呢（这两个参数是相辅相成的）

为了方便哈希取余，提高取余计算的效率

	将元素映射到数组上面，是根据hash值对数组大小取余计算出来的
	而HashMap是用Hash值&(数组容量-1)，可以达到一样的效果
	这就是因为HashMap的大小是2的倍数，2的倍数意味着该数的二进制位只有一个是1，而n-1则全部是1
	如16是10000，15是01111，这样通过&与运算就可以得到和%取余一样的效果，并且效率高得多

扩容时扩容倍数也是2倍，所以在扩容时，只要看原来hash值新增的那一位是0还是1就可以了，是0的话下标不变，是1的话下标为原来下标+原数组容量，这样就将已经产生了hash碰撞的元素完美的转移到新的数组中去

如果初始化传一个容量参数为17的值，会怎么处理？

如果初始化时传的不是2的倍数，HashMap会向上寻找离得最近的2的倍数,"tableSizeFor"方法
如传进来是10，会但是HashMap实际容量会是16

// hashmap构造方法，tableSizeFor
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

// 计算过程是右移1、2、4、8、16，并和原来的数做或运算
// 这样就把二进制低位的各个位置都填上1，再加1就是2的倍数了
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

数据结构

概述

JDK1.7之前：数组 + 链表
JDK1.8之后：数组 + 链表 + 红黑树

拓展：jdk1.8相比之前主要有5点优化：

数据结构引入红黑树，极端情况下查找时间复杂度由O(n)降为O(log n)
链表插入方式变化：由头插法改为了尾插法，修复了扩容+多线程的场景下头插法可能产生环的情况
扩容计算下标优化，1.7需要重新hash计算下标，1.8仅需简单判断高位二进制码即可

红黑树数据结构是怎样的，为什么不用二叉树/平衡树？

红黑树本质上是一种二叉查找树，为了保持平衡，在二叉查找树的基础上增加了一些规则：

所有节点要么是红色，要么是黑色
根节点永远是黑色的
所有的叶子节点都是黑色的（指的是图中的null节点）
每个红色节点的两个子节点一定是黑色的
从任意的节点出发，到所叶子节点的路径，黑色节点数量相同

为什么不用二叉树?
二叉树添加数据时没有额外调整节点的操作，最坏的情况下相当于一个链表，时间复杂度为O(n)
为什么不用平衡二叉树?
平衡二叉树相比红黑树更加严格，为了保持平衡需要旋转的次数更多，增删性能不如红黑树
红黑树是怎么保持平衡的
红黑树通过两种方式来保持平衡：旋转和染色
旋转：当添加一个节点后如果一个子树变成3个节点的链表，通过左旋或右旋的方式将处于中间的节点浮到根节点
染色：当添加一个节点后如果出现连续的红色节点

扩容

HashMap扩容触发条件

当集合容量达到门槛，会进行扩容（门槛：当元素数量达到数组长度*负载因子）
当某节点因为冲突元素达到8时会数化，但如果容量小于64，会优先扩容，再考虑转换成红黑树

HashMap扩容流程 resize()

创建一个容量大小为原来两倍的数组
遍历旧数组，将元素逐个迁移到新数组中

// 由于扩容数组是2倍，下标计算结果会是原下标 或 原下标+原长度
newTab[e.hash & (newCap - 1)] = e;

为什么HashMap链表转红黑树阈值是8，而红黑树转链表阈值是6
- 红黑树节点的大小大概是普通节点大小的两倍，所以转红黑树是用空间换时间的策略，保证极端情况下的查找效率。
- 为什么树化阈值选8呢，与统计学有关。理想情况下使用随机哈希码，链表里的节点符合泊松分布，出现节点个数的概率是递减的，节点个数为8的情况，发生概率仅为0.00000006（亿分之6）
- 至于退化为什么阈值是6而不是8，这是避免发生碰撞时节点增减刚好处于8附近，就会不断在链表和红黑树之间不断转换，导致资源的浪费

操作流程

HashMap放入一个元素的流程

计算key的hashcode（使用扰动函数）
因为对象的hashcode一般会比较大，如果直接取模运算，高位二进制可能无法参与运算，这样处理后可以加大随机性，从而降低哈希冲突概率

static final int hash(Object key) {
    int h;
    // hashcode是一个32位的int类型数值，对Hash进行高16位和低16位进行异或操作
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

判断数组是否为空或者数组长度是否为0
1. 如果是的话需要先执行resize()扩容
计算数组下标：对Hash进行高16位和低16位进行异或操作，然后对数组长度做与运算，得到数组下标
插入元素流程：判断table[i]是否为空
1. table[i]为空，添加元素到数组
2. table[i]不为空，发生hash冲突，通过equals方法比较该桶内元素的值
  1. 如果equals为true，对value值进行覆盖写（如果是链表或红黑树里的元素也是一样，下不赘述）
  2. 如果不同，判断该节点是链表还是红黑树
3. 如果是红黑树，插入元素到红黑树
4. 如果是链表，尾插法插入元素
  1. 判断是否达到树化阈值
  2. 链表长度>8 并且数组长度≥64,链表转红黑树
添加元素后，流程结束前会判断容量是否超过阈值，如果是则resize()扩容

HashMap查询元素流程

计算key的hashcode，同样使用扰动函数让高16位也参与计算
计算数组的下标，获取节点
根据当前节点是链表还是红黑树，遍历查找对应的值

你能自己设计实现一个HashMap吗

本质上就是把一组数据存在一个数组里
通过散列函数计算应该存的数组下标
处理存在同个下标的冲突元素
整体设计：

数据结构：数组 + 链表 + 红黑树
散列函数计算数组下标：hashCode() + 除留余数法
冲突解决：拉链法
扩容：数组扩容后，节点重新hash获取新的下标

线程安全问题
HashMap是否线程安全，如何解决线程安全问题

HashMap没有用到锁，是线程不安全的
- 写写并发场景下可能产生覆盖写
- 读写并发场景下可能获取到null
解决方法：在多线程的场景下我们可以用ConcurrentHashMap或者HashTable。一般情况下我们会使用ConcurrentHashMap，因为ConcurrentHashMap使用的是分段锁会对单独的分片进行加锁，锁的粒度更细。而HashTable则是锁全表的，性能较差

ConcurrentHashMap的实现
1.7版本之前基于分段锁实现
在1.8之后是基于CAS + synchronized实现

JDK1.7分段锁实现

核心实现是一个Segment数组，继承于ReentrantLock，每个Segment里包含HashEntry的数组，HashEntry包含有key、value、下个节点指针 3个信息
实际上相当于每个Segment就是一个HashMap，默认Segment长度也是16，支持16个线程的并发写，Segment之间互不影响
put流程跟HashMap非常类似，只不过是先定位到Segment然后通过锁去操作保证线程安全
get流程也很简单，key通过hash定位到Segment，再遍历链表到具体元素
get操作不需要加锁，因为value是volatile修饰的
[图片]

JDK1.8 CAS + synchronized
put流程
[图片]

计算hash值，遍历node数组，如果node是空的话，通过CAS+自旋的方式初始化
暂时无法在飞书文档外展示此内容
如果当前数组位置是空则通过CAS自旋写入数据
暂时无法在飞书文档外展示此内容
如果hash == MOVED，说明需要扩容，执行扩容操作
暂时无法在飞书文档外展示此内容
如果都不满足，使用synchronized写入数据，与HashMap流程相同判断链表、红黑树
暂时无法在飞书文档外展示此内容

有序性问题
HashMap内部节点是否有序

HashMap是无序的，根据hash值随机插入。如果需要有序可以使用LinkedHashMap或者TreeMap
LinkedHashMap怎么实现排序
LinkedHashMap维护了一个双向链表，有头尾节点，同时数据结果除了继承HashMap的Node属性外，还有before、after用于标识前置节点和后继节点
[图片]

TreeMap怎么实现排序

TreeMap是按照Key的自然顺序或者Comparator的顺序进行排序，内部是通过红黑树来实现
key需要实现Comparatorble接口，或者自定义一个实现了Comparator的比较器，用于TreeMap的key排序

标签：扩容,Java,HashMap,ArrayList,链表,数组,集合,节点
From： https://www.cnblogs.com/dayu1995/p/18238649

Java 集合