当前位置： 首页 > article >正文

Android第四次面试（Java基础篇）

article 2025/3/20 2:11:29

一、Java 中的 DCL 单例模式

  单例模式是设计模式中最常用的模式之一，其核心目标是确保一个类在程序中仅有一个实例，并提供全局访问点。在 Java 中，实现单例模式需要兼顾线程安全和性能优化。DCL（Double-Checked Locking，双重检查锁定）单例模式通过巧妙的锁机制，在保证线程安全的同时显著提升了性能，成为高并发场景下的首选方案。

DCL 单例模式实现代码

public class DCLSingleton {
    // 使用volatile保证可见性和禁止指令重排
    private static volatile DCLSingleton instance;

    // 私有构造函数，禁止外部实例化
    private DCLSingleton() {}

    // 双重检查锁定的核心方法
    public static DCLSingleton getInstance() {
        // 第一次检查：避免无意义的同步
        if (instance == null) {
            synchronized (DCLSingleton.class) { // 同步类锁
                // 第二次检查：确保唯一实例化
                if (instance == null) {
                    instance = new DCLSingleton();
                }
            }
        }
        return instance;
    }
}

代码解释

  1. volatile 关键字：instance 变量使用 volatile 修饰，它有两个重要作用。一是保证变量的可见性，即一个线程修改了该变量的值，其他线程能立即看到最新的值。二是禁止指令重排，避免在多线程环境下，new DCLSingleton() 操作可能出现的问题，如对象还未完全初始化就被其他线程使用。
  2. 私有构造函数：private DCLSingleton() 阻止了外部代码通过 new 关键字创建该类的实例。
  3. 双重检查锁：
    • 第一次检查 if (instance == null)：在没有进入同步块之前先检查 instance 是否为 null，如果不为 null 则直接返回实例，避免了每次调用 getInstance() 方法都进行同步操作，提高了性能。
    • 同步块 synchronized (DCLSingleton.class)：当多个线程同时通过第一次检查时，会进入同步块。
    • 第二次检查 if (instance == null)：在同步块内再次检查 instance 是否为 null，因为可能在第一个线程进入同步块创建实例的过程中，其他线程也通过了第一次检查并等待进入同步块。如果没有第二次检查，可能会创建多个实例。

具体扩展：

1. 第一次检查 if (instance == null)

  • 目的：提高性能。在单例模式中，getInstance() 方法可能会被频繁调用。如果每次调用都进行同步操作（即进入 synchronized 块），会带来较大的性能开销，因为同步操作涉及到线程的阻塞和唤醒，是比较耗时的。通过在进入同步块之前先检查 instance 是否为 null，如果不为 null，说明单例实例已经被创建，直接返回该实例，无需进行同步操作，这样就避免了不必要的同步开销，提高了程序的性能。
  • 多线程情况分析：在多线程环境下，多个线程可能同时调用 getInstance() 方法。由于此时还未进入同步块，多个线程可能都会通过这第一次检查，认为 instance 为 null，从而继续执行后续代码进入同步块。

2. 同步块 synchronized (DCLSingleton.class)

  • 目的：保证线程安全。当多个线程同时通过第一次检查后，为了避免多个线程同时创建单例实例，需要使用同步机制。这里使用 synchronized 关键字对 DCLSingleton 类进行加锁，确保同一时刻只有一个线程能够进入同步块执行后续代码。
  • 锁的范围：使用类级别的锁 DCLSingleton.class，这意味着所有线程在访问这个同步块时都需要竞争同一把锁。这样可以保证在同一时刻只有一个线程能够执行同步块内的代码，从而避免多个线程同时创建多个单例实例。

3. 第二次检查 if (instance == null)

  • 目的：防止创建多个实例。虽然通过第一次检查和同步块的机制，理论上可以保证单例实例的唯一性，但在多线程环境下仍存在一个问题。假设线程 A 和线程 B 同时通过了第一次检查，线程 A 先进入同步块创建了单例实例，然后线程 B 获得锁进入同步块。如果没有第二次检查，线程 B 会再次创建一个新的实例，这就破坏了单例模式的原则。因此，在同步块内再次检查 instance 是否为 null，如果为 null 才创建实例，这样就确保了单例实例的唯一性。
  • 多线程情况分析：当线程 A 进入同步块创建实例后，instance 不再为 null。此时线程 B 进入同步块，通过第二次检查发现 instance 不为 null，就不会再创建新的实例，而是直接跳过创建实例的代码。

二、Java HashMap 深度解析

  HashMap 是 Java 开发者最常用的数据结构之一，其底层基于哈希表实现，结合数组、链表和红黑树的特性，在大多数场景下都能提供高效的增删查操作。本文将深入剖析 HashMap 的工作原理、核心实现细节及优化策略，帮助读者理解其设计哲学与工程实践。

工作原理

HashMap 的核心工作原理可以概括为：通过哈希函数将键（key）映射到数组的某个位置，当发生哈希冲突时，使用链表或红黑树来处理。其工作流程主要包含以下几个步骤：

  1. 初始化：在创建 HashMap 对象时，会初始化一个数组（也称为哈希桶），默认初始容量为 16，负载因子为 0.75。负载因子表示当数组中元素数量达到容量的一定比例时，会进行扩容操作。

  2. 插入元素：当调用 put(key, value) 方法插入键值对时，首先会计算键的哈希值，然后根据哈希值找到对应的数组位置。如果该位置为空，直接将键值对存储在该位置；如果该位置已经有元素，说明发生了哈希冲突，此时会根据具体情况处理。在 JDK 8 及以后的版本中，如果链表长度达到 8 且数组长度达到 64，会将链表转换为红黑树，以提高查找效率；如果红黑树节点数量小于 6，会将红黑树转换回链表。

  3. 查找元素：当调用 get(key) 方法查找元素时，同样会先计算键的哈希值，然后根据哈希值找到对应的数组位置。如果该位置只有一个元素，直接比较键是否相等；如果该位置是链表或红黑树，会在链表或红黑树中查找键对应的元素。

  4. 扩容：当数组中元素数量达到容量乘以负载因子时，会触发扩容操作。扩容时会创建一个新的数组，容量为原来的 2 倍，然后将原数组中的元素重新哈希到新数组中。

具体计算过程

1. 计算哈希值

HashMap 中使用 hash() 方法计算键的哈希值，该方法会对键的 hashCode() 方法返回的值进行二次哈希，以减少哈希冲突的概率。具体代码如下：

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

这里 key.hashCode() 是键对象的哈希码，h >>> 16 是将哈希码右移 16 位，然后进行异或运算。这样做的目的是将哈希码的高位和低位进行混合，使得哈希值更加均匀地分布在数组中。

2. 计算数组索引

计算出哈希值后，需要根据哈希值计算数组的索引位置。HashMap 中使用以下公式计算数组索引：

index = (n - 1) & hash

 其中 n 是数组的长度，hash 是键的哈希值。由于数组长度通常是 2 的幂次方，n - 1 的二进制表示中低位都是 1，通过与哈希值进行按位与运算，可以确保计算出的索引值在数组的有效范围内。

3. 处理数组位置的元素
  • 位置为空：若该位置为空，就直接把键值对存储在这个位置。
  • 位置已有元素（发生哈希冲突）：这时候要依据具体情形处理。
    • JDK 8 之前：采用链表来处理哈希冲突。新插入的元素会被添加到链表的头部，查找时需要遍历链表，时间复杂度为 O(n)，其中 n 是链表的长度。
    • JDK 8 及以后：引入了红黑树来优化链表过长时的查找性能。
      • 链表转换为红黑树：当链表长度达到 8 并且数组长度达到 64 时，链表会被转换为红黑树。红黑树是一种自平衡的二叉搜索树，其查找、插入和删除操作的时间复杂度为 O(logn)，在处理大量数据时性能优于链表。
      • 红黑树转换为链表：当红黑树的节点数量小于 6 时，红黑树会被转换回链表。这是为了避免在数据量较小时，红黑树的维护开销过大。

以下是简化版的 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;
    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
                        // 链表长度达到 8，转换为红黑树
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        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;
}
  • 性能优化：在数据量较小的时候，链表的插入和删除操作比较简单，开销较小；而当数据量增大，链表长度变长时，查找效率会显著下降，此时转换为红黑树可以将查找时间复杂度从 O(n) 降低到 O(logn)，提高整体性能。
  • 空间与时间的平衡：红黑树的维护需要额外的空间和操作，在数据量较小时，使用链表可以减少空间开销；当数据量达到一定程度时，使用红黑树可以在时间复杂度上获得更好的表现。

总结：

  HashMap 基于哈希表，底层由数组、链表（JDK7）和红黑树（JDK8+）组成，通过哈希值快速定位存储位置。通过key.hashCode()与高位异或运算生成哈希值，结合数组长度（2 的幂）的位运算确定索引。冲突元素存入链表，当链表长度≥8 且数组长度≥64 时转为红黑树，提升查找效率至 O (log n)。容量不足时（元素数超过阈值），数组扩容为原来的 2 倍，重新分配哈希桶并迁移元素。 合理设置初始容量和负载因子（默认 0.75），避免哈希冲突，多线程场景使用 ConcurrentHashMap。

扩展内容：

ConcurrentHashMap 的优势

1. 线程安全
  • 传统 HashMap 问题：HashMap 是非线程安全的，在多线程环境下进行读写操作可能会导致数据不一致、死循环等问题，例如在扩容时可能会形成环形链表。
  • ConcurrentHashMap 解决方案：ConcurrentHashMap 是线程安全的，它允许多个线程同时进行读写操作，不会出现数据不一致的问题。这使得开发者在多线程环境中无需额外的同步机制，降低了编程复杂度。
2. 高性能
  • 细粒度锁：在 JDK 7 及以前，ConcurrentHashMap 使用分段锁机制，将整个哈希表分成多个段（Segment），每个段相当于一个小的 HashMap，不同的段可以被不同的线程同时访问，从而提高了并发性能。在 JDK 8 及以后，采用了 CAS（Compare-And-Swap）和 synchronized 相结合的方式，锁的粒度进一步细化到节点级别，减少了锁的竞争，提高了并发度。
  • 并发操作：多个线程可以同时对不同的桶进行读写操作，大大提高了并发性能。例如，在高并发场景下，多个线程可以同时对不同的键值对进行插入、删除和查找操作，而不会相互阻塞。
3. 内存效率高
  • 减少锁的开销：由于采用了细粒度的锁机制，减少了锁的持有时间和范围，降低了锁的开销，从而提高了内存的使用效率。

ConcurrentHashMap 的工作原理

JDK 7 及以前的分段锁机制
  • 数据结构：ConcurrentHashMap 内部包含一个 Segment 数组，每个 Segment 继承自 ReentrantLock，相当于一个小的 HashMap。每个 Segment 包含一个 HashEntry 数组，用于存储键值对。
  • 并发控制：当进行读写操作时，首先根据键的哈希值找到对应的 Segment，然后对该 Segment 加锁。不同的 Segment 可以被不同的线程同时访问，从而实现了并发操作。例如，线程 A 对 Segment1 进行写操作，线程 B 可以同时对 Segment2 进行写操作，只要它们操作的是不同的 Segment。
JDK 8 及以后的 CAS 和 synchronized 机制
  • 数据结构：采用数组 + 链表 + 红黑树的结构，与 HashMap 类似。
  • 并发控制
    • CAS（Compare-And-Swap）：在插入或更新节点时，首先使用 CAS 操作尝试更新节点的值。CAS 是一种无锁算法，它通过比较内存中的值和预期值是否相等来决定是否更新，避免了锁的使用，提高了并发性能。例如，在插入一个新的节点时，首先使用 CAS 操作将新节点插入到指定的位置，如果 CAS 操作失败，说明有其他线程已经修改了该位置的值，此时再使用 synchronized 进行加锁操作。
    • synchronized：当 CAS 操作失败或需要对链表或红黑树进行操作时，使用 synchronized 对节点进行加锁。在 JDK 8 中，synchronized 进行了优化，锁的粒度细化到节点级别，减少了锁的竞争。例如，当多个线程同时对同一个链表进行操作时，只会对链表的头节点进行加锁，其他线程可以继续对其他链表进行操作。

示例代码

 

import java.util.concurrent.ConcurrentHashMap;

public class ConcurrentHashMapExample {
    public static void main(String[] args) {
        ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();

        // 插入元素
        map.put("apple", 1);
        map.put("banana", 2);

        // 获取元素
        Integer value = map.get("apple");
        System.out.println("Value of apple: " + value);

        // 并发操作示例
        Thread t1 = new Thread(() -> {
            map.put("cherry", 3);
        });

        Thread t2 = new Thread(() -> {
            Integer val = map.get("banana");
            System.out.println("Value of banana in thread 2: " + val);
        });

        t1.start();
        t2.start();

        try {
            t1.join();
            t2.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        System.out.println("Final map: " + map);
    }
}

 总结：ConcurrentHashMap 通过分段锁（JDK7）或 CAS+synchronized 细粒度锁（JDK8）实现线程安全，允许多线程并发读写，性能远超线程不安全的 HashMap。底层采用数组 + 链表 / 红黑树结构（类似 HashMap），通过哈希值定位节点，JDK8 后利用 CAS 无锁算法和节点级锁减少竞争，提升并发效率。适用于高并发场景（如分布式系统、缓存），提供线程安全的高效操作，避免 HashMap 的多线程问题，同时比 Hashtable 的全表锁更轻量。

 感谢观看！！！


http://www.kler.cn/a/591952.html

相关文章：

  • 机器学习——深入浅出理解朴素贝叶斯算法
  • Redis项目：短信验证码登录
  • 【JDK17】开源应用服务器大比对
  • logparser日志分析详解
  • ubuntu20.04安装mysql-workbench
  • DataWhale 大语言模型 - 模型详细配置
  • conda 的 envs_dirs 配置出错
  • 解决 ECharts 切换图表时的 Resize 问题
  • 博客图床 VsCode + PicGo + 阿里云OSS
  • SQLark中如何进行数据筛选与排序
  • 批量测试IP和域名联通性2
  • Seaborn 数据可视化指南：核心功能与实战技巧
  • Android wifi的开关Settings值异常分析
  • Type-C：智能家居的电力革命与空间美学重构
  • 前端vue3 setup，后端fastapi
  • 09.【C++】list链表（STL中的列表容器，C++封装的带头双向链表，可实现指定类型的增删查改，迭代器操作等功能）
  • Qt 中工具窗体与普通窗体在任务栏中的区别
  • 基于微信小程序的网上商城
  • jmeter-sample
  • MySQL日期转字符串，字符串转日期的函数