Java集合

Arraylist与LinkedList区别

可以从它们的底层数据结构、效率、开销进行阐述。

	ArrayList	LinkedList
底层结构	数组	双向链表
访问效率	快	较慢，需要遍历
增删效率	较慢，需要移动	快
存储空间	少	较大，链表比数组需要额外存储引用

Arrays.sort或者Collections.sort的底层实现

Collections.sort底层调用了Arrays.sort

Arrays.sort() 针对不同数据类型和数组长度，选择不同的排序算法，核心是「快速排序 + 归并排序 + 插入排序」的组合策略，遵循 “小数据用插入，大数据看类型” 的原则。

基本类型数组（int/long/char 等）

双轴快速排序（Dual-Pivot QuickSort）

• 为什么不用归并排序：基本类型无需考虑稳定性，快速排序空间效率更高（原地排序）；

引用类型数组（Object/String/ 自定义类）：

TimSort（归并排序 + 插入排序）

以下是 TimSort.sort 方法的一些主要特点和实现原理：

1. 数据特性利用：
   TimSort 充分利用了现实世界数据的特性，特别是数据通常部分有序的特点。它首先会将待排序的数组或集合拆分成多个已排序或近似排序的分区（称为“run”）。
2. 分区排序：
   对于每个分区，如果其长度小于某个阈值（通常是 32），TimSort 会使用二分插入排序对其进行排序。这是因为对于小数组，插入排序通常比归并排序更快。如果分区长度大于阈值，TimSort 会尝试使用更高效的排序算法（通常是归并排序的一个变种）进行排序。
3. 合并排序：
   一旦所有的分区都被排序，TimSort 会使用一个高效的合并过程来将这些分区合并成一个完全有序的数组。这个过程类似于归并排序中的合并步骤，但它通过一些优化技巧来减少不必要的比较和复制操作。
4. 稳定性：
   TimSort 是一个稳定的排序算法，这意味着具有相等值的元素在排序后保持它们原来的相对顺序。这对于某些应用（如排序包含复杂对象的列表）来说是非常重要的。
5. 性能优化：
   TimSort 的设计旨在在各种情况下都提供高效的性能，特别是在处理部分有序或包含小规模子数组的数据时。通过结合插入排序和归并排序的优点，并利用数据的局部有序性，TimSort 能够在多种情况下实现接近线性对数时间复杂度（O(n log n)）的性能。

HashMap是什么，原理是什么

HashMap存储的是存在映射关系的键值对，存储在被称为哈希表（数组+链表或红黑树（JDK>7后））的数据结构中。通过计算key的hashCode值来确定键值对在数组中的位置，假如产生碰撞，则使用链表或红黑树。而为了避免hashcode碰撞，就涉及了元素的分布策略和动态扩容

分布策略

1、HashMap的底层数组长度始终保存为2的次幂

2、hash算法使用了key哈希值的高位

3、通过与操作对数组长度取模，如index = 31 & (16-1) = 15

动态扩容

1、HashMap长度默认为16，loadFactor负载因子默认为0.75

2、threshold：阈值容量 = loadFactor * capacity，每当hashmap的数组长度超过threshold时，hashmap就会进行扩容一倍，避免因为数组太满导致过多的hash碰撞

3、扩容过程：由于底层数组的长度始终为2的次幂，也就是说每次扩容，长度值都会扩大一倍，数组长度length的二进制表示在高位会多出1bit。而扩容时，该length值将会参与位于操作来确定元素所在数组中的新位置。所以，原数组中的元素所在位置要么保持不动，要么就是移动2次幂个位置，比如容量从16扩容为32时，hash=31的下标从15移动到31，hash=15的下标还是原来的15不移动。

线程不安全

扩容时可能会产生死锁：多线程扩容时链表JDK7头插法并发扩容时，可能产生闭环

jdk8后，改用了尾插法，避免了闭环问题，但还是存在其他并发问题，所以多线程环境下，要使用ConcurrentHashMap

Java8 HashMap

1、Hash表 = 数组 + 链表 + 红黑树

2、数组扩容时，高低位搭配，不可能形成闭环。if((e.hash & oldCap) == 0) 判断是否需要移动元素，hash值在oldCap的最高位=1，则扩容后下标=扩容前大小+原下标，否则=原下标。

3、链表转红黑树：链表长度大于8并且数组的长度大于64，会把链表转换成红黑树；当链表长度小于等于6时恢复为链表

链表转红黑树

1、TreeNodes占用空间是普通Nodes的两倍，所以只有当Entry链包含足够多的节点且数组长度足够大时才会转成TreeNodes以追求查询速度log2N。

2、且正常来说如果hashcode的离散性好的话，value会均匀分布在数组中而很难达到长度为8的地步，理想情况下我们可以看到，一个map中链表长度达到8个元素的概率为0.00000006，几乎是不可能事件。

3、所以当出现了碰撞度比较高的离散算法时，才会使用到红黑树

PUT过程

1、数组[i]对象是否存在，不存在则直接创建节点并插入

2、存在，判断key值是否存在，不存在则直接插入

3、存在，直接覆盖

4、插入后根据数组 size++ > threshold？判断是否需要扩容

5、第二三步插入时，判断是否需要将链表转化为红黑树

线程不安全

HashTable

​ 既然HashMap是线程不安全的，那我每次put/get操作时都用锁进行控制不就好了？HashTable确实是这么做的，给get/put操作加上了synchronized关键字。但是这样会导致效率低下，在多线程环境下进行读写操作时，其他操作都会被阻塞。所以基本上不推荐使用HashTable。

ConcurrentHashMap-线程安全

java7

ConcurrentHashMap = Segement数组（继承ReentrantLock）+ HashEntry数组 + 链表，分段锁：每次锁一个segement，锁粒度较大

java8

ConcurrentHashMap = Node数组 + 链表/红黑树，bucket桶锁：synchronized第一个节点，相当于锁一个链表，锁粒度小，并且通过CAS的算法插入每个链表的第一个阶段，从而达到并发，锁的粒度较小，灵活。

红黑树的由来

二叉树：一个节点最多有2个子节点

二叉搜索树：有顺序的二叉树：左节点 < 父节点 < 右节点，二叉搜索树高度不确定，检索稳定性差。如果 1,2,3,4,5,6 则二叉搜索树降级为链表，时间复杂度 O(N)。

平衡二叉树：任意一个节点，左子树高度 与 右子树高度的差不超过1，但是维护平衡二叉树这一特性比较复杂，时间复杂度 O(N)。

红黑树：通过「颜色规则 + 旋转 / 重新着色」，强制让树保持 “近似平衡”—— 任意节点到叶子的最长路径 ≤ 2× 最短路径，保证增删改查的时间复杂度稳定在O(log n)。

​ 红黑树给二叉搜索树加了 “颜色家规”，一旦违反家规，就通过 “掰树枝（旋转）” 或 “换颜色” 来修正，确保树不会长得太歪。

红黑树

规则编号	规则内容	规则的作用
1	每个节点要么是红色，要么是黑色	基础约束，给节点加 “颜色标签”
2	根节点必须是黑色	避免根节点为红导致的顶层冲突
3	所有叶子节点（NIL 空节点）都是黑色	统一 “路径终点”，方便计算路径长度（空节点是逻辑上的叶子，不是实际存储数据的节点）
4	如果一个节点是红色，它的两个子节点必须都是黑色	禁止 “连续红节点”，限制路径中红节点的数量
5	从任意节点到其所有叶子节点的路径中，黑色节点的数量都相同（称为 “黑高”）	保证所有路径的 “基础长度（黑节点数）” 一致，最长路径最多是 “黑 + 红交替”，最短路径是 “全黑”

关键推论：

由规则 4+5 可推出：最长路径 ≤ 2× 最短路径（近似平衡）。

比如：黑高 = 3（路径有 3 个黑节点），最短路径是 “黑 - 黑 - 黑”（长度 3），最长路径是 “黑 - 红 - 黑 - 红 - 黑”（长度 5 ≤ 2×3）。

红黑树也是动态树，寻找过程复杂度也趋近LogN，插入过程也是，先查找，然后通过红黑特殊规则调整和旋转（该过程比平衡二叉树快也是LogN维度）

用java手写实现简单HashMap

public class MyHashMap<K,V> {

    public Node<K,V>[] table;
    int capacity;
    int size = 0;
    private static final int DEFAULT_CAPACITY = 16;
    private static final float EXPAND_FACTOR = 0.75f;

    public MyHashMap() {
        this.capacity = DEFAULT_CAPACITY;
        table = new Node[capacity];
    }

    public V get(K key){
        Node<K, V> mapNode = table[getHashCode(key) % capacity];
        if(Objects.nonNull(mapNode)){
            while(mapNode != null){
                if(Objects.equals(mapNode.key, key)){
                    return mapNode.value;
                }
                mapNode = mapNode.next;
            }
        }
        return null;
    }
    public void put(K key, V value){
        if(size >= capacity * EXPAND_FACTOR){
            resize();
        }
        int index = getHashCode(key) % capacity;
        Node<K, V> node = table[index];
        if(Objects.isNull(node)){
            table[index] = new Node<K,V>(key,value);
            size++;
            return;
        }
        Node<K,V> pre = node;
        while(node != null){
            if(node.key.equals(key)){
                node.value = value;
                return;
            }else{
                pre = node;
                node = node.next;
            }
        }
        pre.next = new Node<K,V>(key,value);
        size++;
    }

    private static <K> int getHashCode(K key) {
        if(key == null){
            return 0;
        }
        return key.hashCode();
    }

    public int size(){
        return size;
    }

    public void remove(K key){
        int index = getHashCode(key);
        Node<K, V> mapNode = table[index];
        if(Objects.isNull(mapNode)){
            return;
        }
        Node<K,V> pre = null;
        while(mapNode != null){
            if(Objects.equals(mapNode.key, key)){
                if(pre == null){
                    table[index] = mapNode.next;
                }else{
                    pre.next = mapNode.next;
                }
                size--;
            }
            pre = mapNode;
            mapNode = mapNode.next;
        }
    }

    public static class Node<K,V>{
        private K key;
        private V value;
        private Node<K,V> next;

        public K getKey() {
            return key;
        }

        public void setKey(K key) {
            this.key = key;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }

        public Node<K,V> getNext() {
            return next;
        }

        public void setNext(Node<K,V> next) {
            this.next = next;
        }

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    public static void main(String[] args) {
        MyHashMap<Integer, Integer> map = new MyHashMap<>();
        System.out.println(map.get(1));
        System.out.println(map.get(2));
        System.out.println(map.get(3));
        map.put(1,2);
        map.put(2,3);
        map.put(3,4);
        map.put(1,1);
        System.out.println(map.get(1));
        System.out.println(map.get(2));
        System.out.println(map.get(3));
        System.out.println(map.size);
        System.out.println(map.size);
        map.put(17,4);
        map.put(4,4);
        map.put(5,4);
        map.put(6,4);
        map.put(7,4);
        map.put(8,4);
        map.put(9,4);
        map.put(10,4);
        map.put(11,4);
        map.put(12,4);
        map.put(14,4);
        map.put(13,4);
        map.put(15,4);
        map.put(16,4);
        System.out.println(map.capacity);
        System.out.println(map.get(1));
        System.out.println(map.get(0));
        map.put(null,1);
        map.remove(3);
        System.out.println(map.get(3));
        map.remove(null);
        System.out.println(map.get(null));
    }
    
    
    public void resize(){
        capacity = capacity * 2;
        Node<K,V>[] newTable = new Node[capacity];
        for (int i = 0; i < table.length; i++) {
            Node<K, V> node = table[i];
            while(node != null){
                Node<K, V> next = node.next;
                int newIndex = getHashCode(node.key) % capacity;
                node.next = newTable[newIndex];
                newTable[newIndex] = node;
                node = next;
            }
        }
        table = newTable;
    }
}

java8和java17的区别（java9-17新特性有哪些）

背景：

2020.9。JDK15 发布，宣布 ZGC 可用于生产，2021.9。JDK17 发布，宣布商用免费

zgc

低延迟：控制GC停顿时间在10ms内，对停顿时间敏感

大内存：可支持到TB级别的内存，适用于大规模、高并发的应用。

并发性：大部分工作都是并发完成的，包括标记、压缩、清理，减少了应用STW时间

内存碎片处理：使用基于指针压缩的内存管理，减少内存碎片，并通过并发压缩进一步优化内存利用。

新语法特性

1、密封类 Sealed Classes

密封类可以限制其他类可以继承。

使用场景：组件开发者写的接口，不希望组件使用者继承

public abstract sealed class Shape
    permits Circle, Rectangle {...} //只允许 CirCle 和 Rectangle 继承自己
 
public final class Circle extends Shape {...} // OK
public final class Rectangle extends Shape {...} // OK
public final class Triangle extends Shape {...} // Compile error
 
// No need for default case if all permitted types are covered
double area = switch (shape) {
    case Circle c    -> Math.pow(c.radius(), 2) * Math.PI
    case Rectangle r -> r.a() * r.b()
};

2、Record Classes

一种简洁且安全的方式来创建不可变(字段为final)的数据携带对象，无需手动编写get/equals/hashcode/toString方法

使用场景：任何需要用到不可变特性的地方，主要用户数据传输如DTO

3、空指针异常优化

​ 精准提示哪个变量为空（如 “Cannot invoke “String.length ()” because “str” is null”）

3、instanceof 增强

if (obj instanceof String s && s.length() > 5) {
    //注意，但 obj 为 String 类型时，变量 s 替代了 obj 变量。避免了丑陋的类型转换
    System.out.println("obj is a String with more than 5 characters: " + s.toUpperCase());
}

4、try with resources 增强

​ 无需在 try 括号内重新声明资源变量，直接引用外部已声明的、满足「有效 final」的变量，代码更简洁。

5、var 声明变量

​ 不能用于成员变量 / 方法参数，var list = new ArrayList() ，编译时自动推导确定var 是 ArrayList类型。

6、switch 增强

// Java8 手动break，不支持返回值，必须要有default
// Java 17 多行逻辑 + yield 返回, switch语句块支持返回值赋值给变量
String season = switch (month) {
    case 1, 2, 12 -> {
        System.out.println("月份：" + month); // 多行逻辑
        yield "冬季"; // 返回值（替代break）
    }
    case 3, 4, 5 -> {
        yield "春季";
    }
    default -> "未知";
};

7、接口可以定义私有方法

​ 接口私有方法是为了「在接口内部复用代码」，同时「不暴露内部逻辑」。