Java集合

Java中HashMap的原理

HashMap是基于哈希表的一种数据结构。，用于存储键值对。其核心是将键的哈希值映射到数组的索引位置上，然后通过链表+数组（Java8之后变化链表+数组+红黑树）来处理哈希冲突。

HashMap使用键的 hashcode()方法来计算哈希值，并通过 indexOf方法在JDK1.7之后移除了该方法，改为 (n-1)&hash直接确定元素在数组中的存储的位置。哈希值是经过一定扰动的，防止哈希值分布不均匀，从而减少冲突。

HashMap的默认初始容量为16，负载因子为0.75。也就是说，当存储的元素超过16*0.75=12个时，HashMap会触发扩容，容量乘2并重新分配元素的位置。这种扩容是比较耗时的操作，频繁扩容会影响性能。

    // 默认初始容量 - 必须是 2 的幂次方。
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 即 16

    // 最大容量，如果构造函数中通过参数隐式指定了更高的值，则使用此最大容量。
    // 必须是小于等于 1 << 30 的 2 的幂次方。
    static final int MAXIMUM_CAPACITY = 1 << 30;

    // 构造函数中未指定时使用的负载因子。
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 在向存储单元添加元素时，存储单元使用树结构而不是链表结构的存储单元计数阈值。
    // 当向存储单元添加元素，且该存储单元至少有此数量的节点时，存储单元将转换为树结构。
    // 该值必须大于 2，并且应该至少为 8，以与移除元素时转换回普通存储单元的假设相匹配。
    static final int TREEIFY_THRESHOLD = 8;

    // 在调整大小操作期间将（拆分的）存储单元转换为非树结构存储单元的存储单元计数阈值。
    // 应该小于 TREEIFY_THRESHOLD，并且最多为 6，以与移除元素时的收缩检测相匹配。
    static final int UNTREEIFY_THRESHOLD = 6;

    // 存储单元可以树化的最小表容量。
    // （否则，如果存储单元中有太多节点，表将进行扩容。）
    // 应该至少是 4 * TREEIFY_THRESHOLD，以避免扩容和树化阈值之间的冲突。
    static final int MIN_TREEIFY_CAPACITY = 64;

通过上面变量的定义可以思考一下一下几个问题：

  • DEFAULT_INITIAL_CAPACITY初始容量为啥必须是2的幂次方
  • DEFAULT_LOAD_FACTOR负载因子为啥选择0.75？同时扩容为啥是2倍？
  • TREEIFY_THRESHOLD为啥链表转换为红黑树的阈值默认是8？是怎么从链表转换到红黑树的。

HashMap的结构

 static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;

            return o instanceof Map.Entry<?, ?> e
                    && Objects.equals(key, e.getKey())
                    && Objects.equals(value, e.getValue());
        }
    }

从原码上看，HashMap是由Node组成的一个单向链表，因为Node结构中只要next指向后继节点。那么我们可以用图来表示一个完成初始化的HashMap数组。（在JDK1.8之前，HashMap的节点是由Entry组成的，原理结构和Node是一致的）

image-20251031084239631

通过上面我们又可以思考几个问题。

  1. 为啥用链表+数组

    数组的使用：

    使用数组可以快速索引，HashMap内部使用数组来存储元素，数组的每个元素称为一个桶。使用数组的主要优点是可以通过计算元素的哈希值，将其映射到数组的一个索引位置，从而实现快速查找、插入和删除的操作。

    同时对于一个给定的键值对 (key,value)，通过 hash(key)%array.length可以得到该键值对对应存储在数组的那个位置。在实际的Java实现中，为了提高性能，使用 hash(key)&(array.length-1)来计算索引。因为HashMap的容量总是2的幂次方，这种方式等价于取模运算，而且效率高。这就回答了上面为啥HashMap的容量总是2的幂次方的问题。

    链表的使用：

    由于哈希函数的特性，不同的键可能产生相同的哈希值，或者不同的哈希值映射到数组的同一个索引位置，这就是hash冲突。为了解决哈希冲突，HashMap在每个数组元素中使用链表来存储这些映射到相同索引位置的键值对。

    当发生哈希冲突的时候，新插入的元素会添加到该桶的链表的末尾。查找时，就会先找到这个桶，然后遍历这个链表。

    链表的操作是线性的，时间复杂度是O(n)当哈希冲突少的时候链表成都较短，性能影响不大。

    当发生hash冲突的时候，hashmap的结构如下：

    image-20251031085837546

PUT方法

先看源码

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // 存储元素的数组和相关节点的引用，以及数组长度和索引
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 如果表为空或长度为 0，则进行扩容操作
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 根据哈希值计算元素在数组中的索引，如果该位置为空，则直接将元素作为新节点添加
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // 用于存储找到的已存在节点的引用，以及键的引用
        Node<K,V> e; K k;
        // 检查第一个节点是否与要插入的元素键相同
        if (p.hash == hash && ((k = p.key) == key || (key!= null && key.equals(k))))
            e = p;
        // 如果第一个节点是树节点，则调用树节点的插入方法
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 遍历链表查找元素或找到插入位置
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    // 将元素添加到链表末尾
                    p.next = newNode(hash, key, value, null);
                    // 检查是否需要将链表转换为树
                    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;
            }
        }
        // 如果找到已存在的元素映射
        if (e!= null) { 
            // 获取旧值
            V oldValue = e.value;
            // 如果允许替换或旧值为空，则替换为新值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    // 修改次数加 1
    ++modCount;
    // 如果元素数量超过阈值，进行扩容操作
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    // 表示插入新元素，返回 null
    return null;
}

image-20251031090107029

当链表的长度大于8的时候转换为红黑树结构如下图所示：

image-20251031090317271

详细从存储流程图

image-20251031090531336

是呀HashMap时有哪些提升性能的操作。

  1. 设置合理的初始容量

    在使用HashMap的适合可以预估HashMap存储的数据量大小，那么需要在创建时设置一个合适的初始容量，避免频繁扩容。

  2. 调整负载因子

    官方默认的负载因子是0.75

    可以根据引用场景来调整这个值。较低的负载因子可以减少冲突，提高查询效率，但会占用更多的内存。较高的负载因子则会减少内存的消耗。但可能增加冲突的概率，降低查找效率。

  3. 确保Hashcode均匀分布

    对应的Key的hashcode()方法生成的哈希值需要均匀分布，减少哈希冲突。避免使用质量不好的哈希函数，防止大量的键映射到同一个槽位上。

什么是哈希碰撞，如何解决哈希碰撞

Hash碰撞是指在使用哈希算法的时候，不同的输入数据通过哈希函数计算之后，得到了相同的哈希值。因为哈希值相同，所以这些键会被映射到哈希表的同一个位置，从而引发碰撞。

常见的几种方式解决哈希碰撞的方式

  1. 拉链法

    将哈希表的每个槽位变成一个链表。当多个键的哈希值相同的时候，把它们存在一个链表中。

  2. 开放寻址法

    如果出现碰撞就寻找下一个可用位置。

  3. 多重哈希

    在出现碰撞的时候使用第二个哈希函数计算新的索引位置，减少碰撞的概率。

Java的CpoyOnWriteArrayList和Collections.synchronizedList有啥区别？分别有啥优缺点。

CopyOnWriteArrayList：

是一个线程安全的List实现，特性就是写时复制。每次对List的修改操作(如 add,set,remove)都会复制创建一个新的底层数组。读操作不需要加锁，写操作需要加锁。

优点：

  • 读操作无锁：每次写操作都会复制一个新数组，所以读写之间不冲突，因此读操作不需要加锁，能够提供非常高效的并发读性能。

缺点：

  • 写操作的消耗巨大：每次写操作都会创建并复制新数组，且要将数据复制到新数组中，在写操作频繁的场景下性能较低。
  • 内存消耗大：每次写操作都会创建并复制新数组，在数据量大的情况下，同一时刻会存在两倍List大小的内存占用，开销比较大。

CopyOnWriteArrayList适合读多写少的场景。

Collections.sysnchronizedList:

是一个包装方法，可以将任何的List转换为线程安全的版本他会对每个访问方法进行同步，从而保证线程安全。

优点：

  • 方便：简单一个方法直接就把List变成线程安全的版本，非常方便。

缺点：

  • 并发低：读写操作都加锁，并发性能低

Java中有哪些集合？简单介绍

Java中的集合主要分为两大类：Collection接口和Map接口。前者存储对象的集合，后者存储的适合键值对。

Collection接口下又分为List、Set和Queue接口。每个接口都有它的实现类。以下是主要的集合类：

List接口

  • ArrayList：基于动态数组，查询速度快，插入、删除速度慢
  • LinkedList：基于双向链表，插入、删除速度快，查询速度慢
  • Vector：线程安全的动态数组，类似于ArrayList，但是开销过大。

Set接口

  • HashSet：基于哈希表，元素无序，不允许重复。
  • LinkedHashSet：基于哈希表和链表，维护插入顺序，不允许重复。
  • TreeSet：基于红黑树，元素有序，不允许重复。

Queue接口

  • PriorityQueue：基于优先级堆，元素按照自然顺序或指定比较器排序，
  • LinkedList：可以作为队列使用，支持FIFO操作。

Map接口

  • HashMap：基于哈希表，键值对无序，不允许键重复
  • LinkedHashMap：基于链表和哈希表，维护插入顺序，不允许有重复的键
  • TreeMap：基于红黑树，键值对有序，不允许键重复
  • Hashtable线程安全的哈希表，不允许键或值为null
  • ConcurrentHashMapL：线程安全的哈希表，适合高并发的场景，不允许键或者值为null。

数组和链表在Java中的区别

在存储结构方面：

数组是基于连续的内存块，大小是固定的，需要重新分配内存来改变数组的大小，内存使用紧凑但容易浪费空间。

链表是基于节点的结构，在内存中不需要连续的存储，可以动态的变化大小和插入删除节点，内存不连续但是可以动态扩展。

在访问速度方面：

数组可以支持O(1)时间的随机访问，可以通过索引直接访问任何元素。

而链表访问特定元素需要线性时间O(n),因为节点在内存中不一定是连续的，访问效率受限于链表的结构。

在操作方面：

数组适合需要快速随机访问且大小固定的场景，如实现缓存、表格等数据结构。

链表适合需要频繁插入和删除操作且大小不确定的场景，如队列、栈、链表等。

Java中List接口有哪些实现类？

List接口包含ArrayList、LinkedList、Vector、Stack、CopyOnWriteArrayList几个实现类。

最常见的是ArrayList和LinkedList，这两个都不是并发容器，线程都不安全，

ArrayList是基于动态数组实现，因此它的特性和数组是一致的，随机访问速度快，删除和插入相对笔记慢。

  • 随机访问时间复杂度是O(1)。
  • 插入和删除的(除了在首尾)时间复杂度为O(n)。

LinkedList是基于双向链表实现的，因此两端都能操作。特性就是正常的链表特性，两端插入和删除很快，但是随机访问需要遍历链表。

  • 随机访问的时间复杂度是O(n)，需要遍历链表
  • 插入和删除的时间复杂度是O(1)

Vector和ArrayList类似不过它所有方法都加了锁。同步开销大，性能较低。

CopyOnWriteArrayList也是基于动态数组，但所有的可变操作都会创建一个新的数组。所有它是线程安全的适合在多线程环境中频繁读取、很少修改的场景。

Java中的ArrayList的扩容机制是啥？

当ArrayList中的元素超过当前的容量的时候，会触发扩容机制。默认情况下，ArrayList的初始容量是10。

当发生扩容时，ArrayList会创建一个新的数组，其容量是原数组的1.5倍。然后把原数组的元素复制到新数组中，复制过程使用的适合Arrays.copyOf()方法实现的。

Java中HashMap和Hashtable有啥区别

  1. 线程安全性：
    • HashMap：非线程安全，多线程环境下会产生数据不一致的问题。
    • Hashtable：线程安全，内部大量的方法都使用了 synchronized关键字进行修饰。保证了多线程的安然性。
  2. 性能差异：
    • HashMap：由于没有线程同步的开销，因此单线程环境下性能由于Hashtable。
    • Hashtable：由于方法有同步锁的缘故，性能低于HashMap。由于使用的是全局锁的方法。使得即使是不同的操作，也会被串行化。
  3. 允许空值：
    • HashMap允许一个null键或者多个null值
    • Hashtable不允许null值和nuill键，插入null键或者null值会直接抛异常。
  4. 继承结构：
    • HashMap：继承自AbstractMap，是Map接口的实现类。
    • Hashtable：继承自Dictionary（已废弃），后来实现了Map接口。是一种比较古老的类，在Java2之后逐渐被替代。
  5. 迭代器类型：
    • HashMap：使用的是快速失败的 Iterator在迭代过程中如果Map进行结构性修改，直接抛异常。并发修改异常。
    • Hashtable：使用的是弱一致性的 Enumerator虽然也不建议在迭代过程中修改Map，但不会抛出异常。

Java中的HashSet和HashMap有啥区别？

HashSet：是基于HashMap实现的集合类，不允许有重复的元素，用于存储一组无序的唯一元素。

HashMap：基于哈希表的数据结构，存储的是键值对，键必须唯一，值可以重复。

实际上HashSet内部就是使用的HashMap来实现，HashSet的元素实际上存储在HashMap的键中，而所有的值都是一个常量对象。因此HashSet仅操作HashMap的键部分。

Java中HashMap的扩容机制是如何的

HashMap的扩容基于的是负载因子。默认情况下，负载因子是0.75。这意味着当HashMap存储的元素超过容量的75%的时候。会触发扩容的操作。

例如：初始容量是16，负载因子是0.75。则扩容阈值为16*0.75=12当存入第13个数字的时候，HashMap会触发扩容。

当触发扩容的时候，HashMap的容量会扩大为当前容量的2倍。例如，容量从16增加到32，从32增加到64等。

扩容时，HashMap需要将所有的元素重新分配到哈希桶中，这个过程叫做rehashing。即每个元素的存储位置的会根据新容量的大小重新计算，并移动到新数组中。

rehashing细节

按照我们的思维，每一个元素的都应该重新利用hash计算索引位置一个一个般进去。

在1.7的时候是这样的，然而在1.8的时候做了优化关键点在于数组的长度是2的次方，且扩容为2倍。因此数据的长度是2的n次方，索引假设以前的数组长度16的二进制是010000，那么数组长度为32的二进制表示就是100000。它们之间的差别在于高位多了一个1,而我们通过key的hash值定位其数组位置所采用的方式 （数组长度-1）&hash。我们拿16和32举例：

16-1=15,二进制为001111

32-1=31,二进制为011111

所以重点在key的hash值的从右往左数的第五位是否为1如果是1说明要需要搬迁到新位置，而且新位置的下标就是原下标+16（原数组大小），如果是0说明吃不到新数组长度的高位那就还是在原位置。不需要搬迁。

所以，我们刚好拿老数组的长度010000来判断高位是否为1，这样只有两种情况，要么是1要么0。

image-20251104084831375

为啥Java的HashMap在扩容的时候采用的是2的n次方

HashMap采用的是2的n次方作为容量，主要是提高哈希值的分布均匀和哈希计算的效率。

HashMap通过 （n-1）&hash来计算元素存储的位置，这种位运算只有在数组容量为2的n次方才能确保索引均匀分布。位运算的效率高于取模运算（hash%n），提高了索引的计算速度。

而且当HashMap扩容时，通过容量为2的n次方，扩容时只需要通过简单的位运算判断是否需要迁移，这减少来重新计算索引的开销从而提升来rehash的效率。

为啥HashMap的默认负载因子是0.75

HashMap的默认负载因子是0.75，是为了在时间空间复杂度的一个合理平衡。负载因子为0.75时，避免过多扩容的同时，也保证了不会出现过多的哈希冲突，确保查找和插入操作效率。维持良好的性能表现。

负载因子过小：会让HashMap频繁扩容，增加空间占用空间利用率低，但查询效率高。

负载因子过大：会增加哈希冲突的概率，查询效率低，但空间利用率高。

为啥Java8对HashMap进行来红黑树的改动

在JDK1.8之前，HashMap使用链表来解决哈希冲突。当哈希冲突较多的时候，链表中的元素增多，查找、插入和删除的时间复杂度从O(1)变为O(n)

因此在JDK1.8的时候引入来红黑树，当链表的长度超过一定阈值的时候，默认为8时，链表会转换为红黑树，避免性能急剧下降。当链表的长度降到6一下的时候，红黑树又会退化为链表，保持简单高效。

红黑树是一种平衡二叉树，插入、删除、查找的时间负载度都是O（log n）,在元素多的情况下，效率是优于链表的。

链表到红黑树的转换机制

  • 如果某个桶中的元素数量大于等于8，且数组的长度大于等于64的时候，链表会转换为红黑树；
  • 如果数组的长度小于64，则选择扩容而不是转换为红黑树。

Java8的HashMap除了红黑树还要哪些改动？

  • 改进来哈希函数的计算：在JDK1.8中优化来扰动函数，使得哈希值分布更加均匀，减少了哈希冲突的发生。通过生成哈希值时使用来扰动函数，确保了哈希值高地位都能参与到桶的选择中。
  • 扩容机制优化：JDK1.8改进了扩容时候的元素迁移机制。在扩容过程中。不在对每个元素重新取模计算索引。而是根据原数组的长度的高位来判断元素是留在原位置还是迁移到新数组中。这一改动减少了不必要的计算，提升来扩容的效率。
  • 头插法变尾插法：头插法的好处是在插入的时候不需要遍历链表，直接替换头结点即可，但是缺点是在扩容的时候会出现逆序。而逆序在多线程操作下可能出现环，产生死循环，于是改为了尾插法。但是改为尾插法后还是可能出现环，但是这个是红黑树的问题，索引多线程环境下就不该使用HashMap。

Java中的LinkedHashMap是什么

LinkedHashMap是Java集合的框架的一个实现类，它继承自HashMap，且保留了键值对的插入顺序或者访问顺序。

它内部维护了一个双向链表来记录元素的插入顺序或者访问顺序，

使用场景：

  • 缓存实现：可以根据访问顺序移除最久未使用的元素，常用LRU缓存
  • 数据存储：需要保持元素插入顺序的场景。

Java中的TreeMap是啥

TreeMap内部是通过红黑树实现的，可以让key实现Comparable接口或者自定义实现一个comparator传入构造函数，这样塞入的节点就会根据你定义的规则进行排序。

基本特性：

  • 数据结构：TreeMap是基于红黑树实现的，红黑树是一种自平衡的二叉搜索树，能够保证基本操作（插入、删除、查找）的时间空间复杂度为O(log n)。
  • 键的有序性：TreeMap的键是有序的，默认是按自然排序（键的Comparable）排序，也可以通过构造时提供Comparator来自定义排序。
  • 不允许null键：TreeMap不允许键为null，值可以为null。

Java中的IdentityHashMap是什么？

IdentityHashMap是Java中的一个Map的实现类，和普通HashMap不同，它使用的引用相等性作为键的比较方式。换句话说，它使用==来比较键值，而不是equals()方法。因此只要当两个键引用相同时才被认为是相同的键。

使用场景：

  • 对象身份区分：适用于需要基于对象身份进行区分的场景，比如需要追踪对象示例，而不是逻辑上的值相等性。
  • 特殊缓存：有时候用于构建缓存或者映射结构，确保即使两个对象内容相同，但只要它们是不同的实例，就会被当作不同的键。

Java中的WeekHashMap是啥？

WeeakHashMap是Java中的一个特殊的Map实现，它使用弱引用作为键，弱引用允许垃圾回收器在没有其他强引用指向该对象的时候回收它的内存。因此，当一个键不再被其他对象引用的时候，WeakHashMap会自动删除于该键相关联的条目。

常用于缓存的实现。当缓存中的键不再被其他地方引用的时候，可以自动删除相应的缓存条目，节省内存，防止内存泄露。