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

九月九日忆八股

article 2025/3/1 0:32:32

集合

1.集合转Map

使用 java.util.stream.Collectors 类的 toMap() 方法转为 Map 集合
注意：当 value 为 null 时会抛 NPE 异常

class Person {
    private String name;
    private String phoneNumber;
     // getters and setters
}

List<Person> bookList = new ArrayList<>();
bookList.add(new Person("jack","18163138123"));
bookList.add(new Person("martin",null));
// 空指针异常
bookList.stream().collect(Collectors.toMap(Person::getName, Person::getPhoneNumber));

原因：toMap() 方法 ，其内部调用了 Map 接口的 merge() 方法，该方法方法会先调用 Objects.requireNonNull() 方法判断 value 是否为空。

集合遍历

不要在 foreach 循环里进行元素的 remove/add 操作。remove 元素请使用 Iterator 方式，如果并发操作，需要对 Iterator 对象加锁。

  • foreach 语法底层其实还是依赖 Iterator 。不过， remove/add 操作直接调用的是集合自己的方法，而不是 Iterator 的 remove/add方法
  • 这就导致 Iterator 莫名其妙地发现自己有元素被 remove/add ，然后，它就会抛出一个 ConcurrentModificationException 来提示用户发生了并发修改异常。这就是单线程状态下产生的 fail-fast 机制。
  • fail-fast 机制 ：多个线程对 fail-fast 集合进行修改的时候，可能会抛出ConcurrentModificationException。 即使是单线程下也有可能会出现这种情况，上面已经提到过。

解决方案

  • 使用普通的 for 循环
  • 使用 fail-safe的集合类。java.util包下面的所有的集合类都是 fail-fast 的，而java.util.concurrent包下面的所有的类都是 fail-safe 的。

集合去重

可以利用 Set 元素唯一的特性，可以快速对一个集合进行去重操作，避免使用 List 的 contains() 进行遍历去重或者判断包含操作。

// Set 去重代码示例
public static <T> Set<T> removeDuplicateBySet(List<T> data) {

    if (CollectionUtils.isEmpty(data)) {
        return new HashSet<>();
    }
    return new HashSet<>(data);
}

// List 去重代码示例
public static <T> List<T> removeDuplicateByList(List<T> data) {

    if (CollectionUtils.isEmpty(data)) {
        return new ArrayList<>();

    }
    List<T> result = new ArrayList<>(data.size());
    for (T current : data) {
        if (!result.contains(current)) {
            result.add(current);
        }
    }
    return result;
}

原因：

  • HashSet 的 contains() 方法底部依赖的 HashMap 的 containsKey() 方法，时间复杂度接近于 O（1）（没有出现哈希冲突的时候为 O（1））。有 N 个元素插入进 Set 中，那时间复杂度就接近是 O (n)。
  • ArrayList 的 contains() 方法是通过遍历所有元素的方法来做的，时间复杂度接近是 O(n)。List 有 N 个元素，那时间复杂度就接近是 O (n^2)。

集合转数组

  • 转为包装类型的数组可以直接使用toArray(T[] array)方法。传入的是类型完全一致、长度为 0 的空数组。toArray(T[] array) 方法的参数是一个泛型数组，如果 toArray 方法中没有传递任何参数的话返回的是 Object类 型数组。
  • 转为基本类型数组，就要使用stream流.
    例如arrayList转为int数组，如果使用上面的方法会发现int和Integer不匹配，所以通过steam进行拆箱再转为list
    int[] res = list.stream().mapToInt(Integer::intValue).toArray()

结合转数组

不推荐Arrays.asList()。

  • Arrays.asList()是泛型方法，传递的数组必须是对象数组，而不是基本类型。
  • 该方法返回的并不是 java.util.ArrayList ，而是 java.util.Arrays 的一个内部类,这个内部类并没有实现集合的修改方法或者说并没有重写这些方法。使用集合的修改方法: add()、remove()、clear()会抛出异常。

使用stream流

Integer [] myArray = { 1, 2, 3 };
List myList = Arrays.stream(myArray).collect(Collectors.toList());
//基本类型也可以实现转换（依赖boxed的装箱操作）
int [] myArray2 = { 1, 2, 3 };
List myList = Arrays.stream(myArray2).boxed().collect(Collectors.toList());

ArrayList源码

guide链接

  1. 无参构造函数
    以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10。

    public boolean add(E e) {
//添加元素之前，先调用ensureCapacityInternal方法
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //这里看到ArrayList添加元素的实质就相当于为数组赋值
    elementData[size++] = e;
    return true;
}
//得到最小扩容量
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
          // 获取默认的容量和传入参数的较大值
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
	// 设计扩容grow函数
    ensureExplicitCapacity(minCapacity);
}
//判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // 当容量不足时扩容
    if (minCapacity - elementData.length > 0)
        //调用grow方法进行扩容，调用此方法代表已经开始扩容了
        grow(minCapacity);
}

著作权归所有
原文链接：https://javaguide.cn/java/collection/arraylist-source-code.html
```

  1. 参数为集合构造函数

    /**
 * 保存ArrayList数据的数组
 */
transient Object[] elementData; // non-private to simplify nested class access

public ArrayList(Collection<? extends E> c) {
    //将指定集合转换为数组
    elementData = c.toArray();
    //如果elementData数组的长度不为0
    if ((size = elementData.length) != 0) {
        // 如果elementData不是Object类型数据（c.toArray可能返回的不是Object类型的数组所以加上下面的语句用于判断）
        if (elementData.getClass() != Object[].class)
            //将原来不是Object类型的elementData数组的内容，赋值给新的Object类型的elementData数组
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // 其他情况，用空数组代替
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

  2. 扩容机制

        /**
     * 要分配的最大数组大小
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * ArrayList扩容的核心方法。
     */
    private void grow(int minCapacity) {
        // oldCapacity为旧容量，newCapacity为新容量
        int oldCapacity = elementData.length;
        //将oldCapacity 右移一位，其效果相当于oldCapacity /2，
        //我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
       // 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) `hugeCapacity()` 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，
       //如果minCapacity大于最大容量，则新容量则为`Integer.MAX_VALUE`，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 `Integer.MAX_VALUE - 8`。
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

扩容原因：调用add添加元素时会判断容量是否充足，不充足则扩容。

  • 根据add方法源码，添加元素是会生成最小容量需求变量minCapacity = size + 1

  • 通过ensureCapacityInternal得到最小容量，如果数组为空则minCapacity = Math.max(10, minCapacity);

  • ensureExplicitCapacity判断是否需要扩容，即minCapacity - elementData.length > 0是否成立

  • 以下为扩容逻辑grow

  • 创建变量oldCapacity = elementData.length

  • 创建扩容后数组大小变量newCapacity = oldCapacity + (oldCapacity >> 1);（初始扩容大小）

  • 然后检查新容量是否大于最小需要容量minCapacity ，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量（一次扩容可能还是无法满足）。

  • ArrayList中有一个常量MAX_ARRAY_SIZE表示数组的最大容量

  • 如果新容量newCapacity 大于 MAX_ARRAY_SIZE（可能扩容导致newCapacity 过大，也可能最小需求量就是大于 MAX_ARRAY_SIZE）执行hugeCapacity方法

  • hugeCapacity：如果minCapacity大于最大容量，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8。

  • 扩容核心：Arrays.copyOf用新数组替换原数组实现扩容

  1. Arrays.copyOf
    阅读源码的话，我们就会发现 ArrayList 中大量调用了这个方法
    （1）System.arraycopy() 方法

    public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

    （2）Arrays.copyOf()方法

        public static int[] copyOf(int[] original, int newLength) {
    	// 申请一个新的数组
        int[] copy = new int[newLength];
	// 调用System.arraycopy,将源数组中的数据进行拷贝,并返回新的数组
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

    （3）List的toArray方法

       /**
     以正确的顺序返回一个包含此列表中所有元素的数组（从第一个到最后一个元素）; 返回的数组的运行时类型是指定数组的运行时类型。
     */
    public Object[] toArray() {
    //elementData：要复制的数组；size：要复制的长度
        return Arrays.copyOf(elementData, size);
    }

HashMap源码

HashMap源码

  • loadFactor 加载因子
  • threshold
  • 4个构造函数（空、map参数、容量大小、容量大小+加载因子）
  • map参数构造函数中的putMapEntries方法
  • put方法
  • resize()扩容。HashMap的容量扩展原理：Java中的数组是不能自动扩展的。Hashmap的方法是用新数组替换原数组，重新计算原数组中的所有数据，插入新数组，然后指向新数组；如果数组在扩容前已经达到最大，则直接将阈值设置为最大整数返回。

map扩容和list扩容原理相同，都是用新数组替换原数组，对于list使用的时Object数组，map则使用Node<k,v>数组。

concurrentHashMap1.7

concurrentHashMap put方法先找到对应的Segment，然后调用Segment 的put方法存储对象。

concurrentHashMap put方法

/**
 * Maps the specified key to the specified value in this table.
 * Neither the key nor the value can be null.
 *
 * <p> The value can be retrieved by calling the <tt>get</tt> method
 * with a key that is equal to the original key.
 *
 * @param key key with which the specified value is to be associated
 * @param value value to be associated with the specified key
 * @return the previous value associated with <tt>key</tt>, or
 *         <tt>null</tt> if there was no mapping for <tt>key</tt>
 * @throws NullPointerException if the specified key or value is null
 */
public V put(K key, V value) {
    Segment<K,V> s;
    if (value == null)
        throw new NullPointerException();
    int hash = hash(key);
    // hash 值无符号右移 28位（初始化时获得），然后与 segmentMask=15 做与运算
    // 其实也就是把高4位与segmentMask（1111）做与运算
    int j = (hash >>> segmentShift) & segmentMask;
    if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
         (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
        // 如果查找到的 Segment 为空，初始化
        s = ensureSegment(j);
    return s.put(key, hash, value, false);
}

/**
 * Returns the segment for the given index, creating it and
 * recording in segment table (via CAS) if not already present.
 *
 * @param k the index
 * @return the segment
 */
@SuppressWarnings("unchecked")
private Segment<K,V> ensureSegment(int k) {
    final Segment<K,V>[] ss = this.segments;
    long u = (k << SSHIFT) + SBASE; // raw offset
    Segment<K,V> seg;
    // 判断 u 位置的 Segment 是否为null
    if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
        Segment<K,V> proto = ss[0]; // use segment 0 as prototype
        // 获取0号 segment 里的 HashEntry<K,V> 初始化长度
        int cap = proto.table.length;
        // 获取0号 segment 里的 hash 表里的扩容负载因子，所有的 segment 的 loadFactor 是相同的
        float lf = proto.loadFactor;
        // 计算扩容阀值
        int threshold = (int)(cap * lf);
        // 创建一个 cap 容量的 HashEntry 数组
        HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
        if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) { // recheck
            // 再次检查 u 位置的 Segment 是否为null，因为这时可能有其他线程进行了操作
            Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
            // 自旋检查 u 位置的 Segment 是否为null
            while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
                   == null) {
                // 使用CAS 赋值，只会成功一次
                if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
                    break;
            }
        }
    }
    return seg;
}

注意：判断Segment是否存在都是通过UnSafe.getObjectVolatile判断内存中是否真实存在。
put方法：

  1. 计算要 put 的 key 的位置，获取指定位置的 Segment下标u 。
  2. 如果指定位置的 Segment 为空，则初始化这个 Segment。
  3. 初始化Segment如下
  4. 根据Segment 数组下标u计算得到所在内存位置，判断 Segment 是否为null。
  5. 不为空则返回对应Segment，否则创建新的Segment，流程如下：
  6. 获取数组下标为0的 segment 里的 HashEntry<K,V> 初始化长度
  7. 获取0号 segment 里的 hash 表里的扩容负载因子，所有的 segment 的 loadFactor 是相同的
  8. 计算新segment 的扩容阀值
  9. 创建一个 容量与0号 segment 相同的 HashEntry 数组
  10. 再次检查 u 位置的 Segment 是否为null，因为这时可能有其他线程进行了操作。不为空则返回，否则继续
  11. 创建一个Segment ，new Segment<K,V>(lf, threshold, tab)
  12. 自旋检查u 位置的 Segment 是否为null， 使用CAS 将HashEntry数组赋值给Segment ，只会成功一次
  13. 返回segment对象，执行后续put操作

**segment数组中主要包含三个元素：加载因子、扩容阀值、HashEntry数组 （用于存放key value）。**即元素的实际存储是通过segment.put方法存入HashEntry 数组。

segment put方法

final V put(K key, int hash, V value, boolean onlyIfAbsent) {
    // 获取 ReentrantLock 独占锁，获取不到，scanAndLockForPut 获取。
    HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value);
    V oldValue;
    try {
        HashEntry<K,V>[] tab = table;
        // 计算要put的数据位置
        int index = (tab.length - 1) & hash;
        // CAS 获取 index 坐标的值
        HashEntry<K,V> first = entryAt(tab, index);
        for (HashEntry<K,V> e = first;;) {
            if (e != null) {
                // 检查是否 key 已经存在，如果存在，则遍历链表寻找位置，找到后替换 value
                K k;
                if ((k = e.key) == key ||
                    (e.hash == hash && key.equals(k))) {
                    oldValue = e.value;
                    if (!onlyIfAbsent) {
                        e.value = value;
                        ++modCount;
                    }
                    break;
                }
                e = e.next;
            }
            else {
                // first 有值没说明 index 位置已经有值了，有冲突，链表头插法。
                if (node != null)
                    node.setNext(first);
                else
                    node = new HashEntry<K,V>(hash, key, value, first);
                int c = count + 1;
                // 容量大于扩容阀值，小于最大容量，进行扩容
                if (c > threshold && tab.length < MAXIMUM_CAPACITY)
                    rehash(node);
                else
                    // index 位置赋值 node，node 可能是一个元素，也可能是一个链表的表头
                    setEntryAt(tab, index, node);
                ++modCount;
                count = c;
                oldValue = null;
                break;
            }
        }
    } finally {
        unlock();
    }
    return oldValue;
}

由于 Segment 继承了 ReentrantLock，所以 Segment 内部可以很方便的获取锁，put 流程就用到了这个功能。

  1. tryLock() 获取锁，获取不到使用 scanAndLockForPut 方法继续获取。

  2. 计算 put 的数据要放入的 index 位置，然后获取这个位置上的 HashEntry

  3. 遍历 put 新元素，为什么要遍历？因为这里获取的 HashEntry 可能是一个空元素，也可能是链表已存在，所以要区别对待。

    如果这个位置上的 HashEntry 不存在：
    （1）如果当前容量大于扩容阀值，小于最大容量，进行扩容。
    （2）直接头插法插入。
    如果这个位置上的 HashEntry 存在：
    （1）判断链表当前元素 key 和 hash 值是否和要 put 的 key 和 hash 值一致。一致则替换值
    （2）不一致，获取链表下一个节点，直到发现相同进行值替换，或者链表表里完毕没有相同的。没有相同的节点则需要插入新节点，判断当前容量是否大于扩容阀值，小于最大容量，进行扩容。直接链表头插法插入。

  4. unlock()释放锁，如果替换返回旧值，否则返回 null.

这里面的scanAndLockForPut操作就是不断的自旋 tryLock() 获取锁。当自旋次数大于指定次数时，使用 lock() 阻塞获取锁。在自旋时顺表获取下 hash 位置的 HashEntry。

扩容 rehash

扩容实际是对Segment中的HashEntry进行扩容。
ConcurrentHashMap 的扩容只会扩容到原来的两倍。老数组里的数据移动到新的数组时，位置要么不变，要么变为 index+ oldSize，参数里的 node 会在扩容之后使用链表头插法插入到指定位置。

ConcurrentHashMap -1.8

ConcurrentHashMap -1.8 源码解析


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

相关文章：

  • iOS 项目嵌入Flutter 运行
  • Linux 入门教程｜｜Shell 教程｜｜Shell 数组｜｜Shell 运算符
  • BCSP-玄子JAVA开发之JAVA数据库编程CH-06_MySQL数据库企业开发技术
  • Springboot生成二维码
  • 系统分析师每日练习错题知识点1
  • 软件测试方法上篇（等价类、边界值、因果图）
  • windows下iis安装pdo_sqlsrv扩展
  • 【实战】19.Axios 封装与使用
  • 【C语言】深度理解指针(下)
  • 基于chatGPT设计卷积神经网络
  • 【网络】https协议
  • 使用stm32实现电机的PID控制
  • Android 反编译-回编译
  • python机器学习课程——决策树全网最详解超详细笔记附代码
  • Mac和Windows如何控制node版本
  • YOLOv7训练自己的数据集(手把手教你)
  • C++STL详解(八)-- set,map,multiset,multimap的介绍与使用
  • （5）惯性推算失控保护
  • 误删文件夹但是回收站没有找到怎么恢复
  • JVM类加载机制