集合篇(上)

WARNING

本文主要取自🐔鸡翅老哥

一切为了方便自己背诵, 于是摘要过来

难免会有大量源码的存在，但是这些详细内容其实多看看就明白了，背的时候主要背总结

介绍一下常见的list的实现类

List 是平常使用非常多的一个集合类型，是一个有序的 Collection。常见的有以下几种:

ArrayList：最常用的 List 实现类，线程不安全，基于数组实现，排列有序，可重复,支持快速随机访问。插入或删除中间元素时需要复制和移动数组，效率低。适合随机查找和遍历，不适合频繁插入删除。实现了 RandomAccess 接口，支持快速随机访问；实现了 Serializable 接口，支持序列化传输。
扩容策略：新容量的计算公式为:newCapacity= oldCapacity+(oldCapacity>>1)，这实际上是将原容量增加50%(即乘以1.5)
LinkedList：基于双向链表，线程不安全，适合频繁插入和删除操作，随机访问和遍历速度较慢。除了 List 接口方法，还 * 提供操作表头和表尾* 的方法，可作为栈、队列、双端队列使用。
Vector：与 ArrayList 类似，基于数组实现，虽然线程安全，但实现同步需要很高的花费，效率低。扩容时容量翻倍，已过时，一般不推荐使用。

ArrayList初始容量是多少

ArrayList 是 Java 中的动态数组类，在添加或删除元素时自动调整大小。默认初始容量是 10，即创建 ArrayList 实例时如果没有指定容量参数，内部数组的初始长度为 10。超过这个容量时，会扩容为原来的 1.5 倍。

ArrayList<String> list = new ArrayList<>(); // 默认初始容量为 10

如果知道将要存储的元素数量，建议指定初始容量来提高性能，避免频繁扩容和数组复制。

ArrayList<String> list = new ArrayList<>(50); // 指定初始容量为 50

自 JDK 1.7 起，ArrayList 初始化时为一个空数组，第一次插入元素时会触发懒加载机制，将容量设为 10。JDK 8 对此进行了优化，节省了内存。

java

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

ArrayList是如何扩容的

ArrayList 的扩容机制 是 Java 集合框架的一个重要概念，它允许 ArrayList 在需要时自动增加内部数组的大小以容纳更多元素。主要步骤如下：

初始容量与扩容因子：ArrayList 的默认初始容量是 10，扩容因子为 1.5，即容量会增长为当前容量的 1.5 倍。
扩容触发条件：当添加新元素且元素数量超过当前容量时触发扩容操作。
扩容策略：通过计算 newCapacity = oldCapacity + (oldCapacity >> 1) 将容量增加 50%。若新容量大于 Integer.MAX_VALUE - 8，则设为 Integer.MAX_VALUE。
(因为数组的长度是一个int类型，其最大值是Integer.MAX VALUE，但ArrayList需要预留一些空间用于内部操作)
扩容过程：
- 创建一个新数组，长度为新计算的容量。
- 将原数组的元素复制到新数组中。
- 更新 ArrayList 的内部引用为新数组，并将新元素添加到数组末尾。
性能影响：扩容涉及内存分配与元素复制，会对性能产生影响。因此，预估元素数量并设置合适的初始容量可以减少扩容次数，提高性能。

扩容源码

java

private void grow(int mincapacity){
    //overflow-conscious code
    int oldcapacity = elementData.length;
    int newCapacity = oldcapacity + (oldcapacity >> 1);
    if(newcapacity - mincapacity < 0)newcapacity = mincapacity;
    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);
}

之所以扩容是 1.5 倍，是因为 1.5 可以充分利用移位操作，减少浮点数或者运算时间和运算次数

ArrayList添加和删除元素为什么慢

ArrayList 添加与删除操作慢 主要是由于其基于数组的实现，数组在插入和删除元素时需要移动其他元素以保持连续性和顺序性。相比链表， ArrayList 的插入和删除操作时间复杂度为 O(n)，而链表（如 LinkedList）的为 O(1)。

添加元素

尾部添加：
- 情况 1：若容量未满，直接在尾部添加元素，时间复杂度为 O(1)。
- 情况 2：若容量已满，则触发扩容，扩容后复制元素，时间复杂度为 O(n)，其中 n 为当前元素数量。
指定位置插入：
- 插入时，需要将目标位置后的元素向后移动，时间复杂度为 O(n)。最坏情况是在头部插入，移动所有元素。

删除元素

尾部删除：
- 直接移除尾部元素，时间复杂度为 O(1)。
指定位置删除：
- 删除后需将该位置之后的元素向前移动，时间复杂度为 O(n)。最坏情况是在头部删除，移动所有元素。

总之，由于数组结构的特性，ArrayList 适合尾部操作而不适合频繁的中间插入或删除。

ArrayList是线程安全的吗

ArrayList 是线程不安全的，在多线程环境下同时进行操作时，可能会导致数据不一致。由于 ArrayList 基于数组实现，多个线程同时添加或删除元素时，数组的大小可能会发生变化，进而引发错误。

多线程操作问题：

例如，以下代码展示了 ArrayList 在添加元素时的逻辑：
java
```
elementData[size] = e;
size = size + 1;
```
1
2
- elementData[size] = e：在 elementData 数组的当前大小 size 位置放置新元素 e。
- size = size + 1：更新 size，使 ArrayList 包含新元素。
问题：如果两个线程同时向 ArrayList 添加元素，可能发生如下情况：
- 线程 A 执行 elementData[0] = eA，线程 B 也执行 elementData[0] = eB（线程 A 尚未更新 size，线程 B 看到的 size 仍为 0），导致 elementData[0] 被 eB 覆盖，eA 丢失。
- 两个线程最后都更新 size = 1，虽然有两个元素，但 size 错误。

解决方案：

使用 Collections.synchronizedList()：
- 通过 Collections.synchronizedList() 方法将 ArrayList 转换为线程安全的 List，在操作时加锁，保证线程安全，尽管会有性能损耗。
java
```
List<String> synchronizedList = Collections.synchronizedList(new ArrayList<>());
```
1
使用 CopyOnWriteArrayList：
- CopyOnWriteArrayList 是并发包中的线程安全实现，修改时会创建新数组，不影响其他线程读取，适合读操作远多于写操作的场景。
使用锁机制：
- 使用 Lock 或 Semaphore 等并发包中的显式锁，确保对 ArrayList 的操作线程安全。不过，锁的管理可能引发死锁问题。
使用线程安全集合：
- 例如 Vector 或 ConcurrentLinkedQueue，它们本身是线程安全的，适合多线程环境直接使用。

总的来说，为保证线程安全，可以选择适当的集合类或加锁机制来保护 ArrayList 的操作。

ArrayList如何保证线程安全

为了保证 ArrayList 的线程安全，常用的几种方式包括：

借助锁 (synchronized)

通过在访问 ArrayList 的代码块上使用 synchronized 关键字进行手动同步，确保同一时刻只有一个线程能够操作列表。这种方法要求所有访问 ArrayList 的代码块使用相同的锁。

java

List<String> list = new ArrayList<>();
synchronized(list) {
    Iterator<String> it = list.iterator();
    while (it.hasNext()) {
        String element = it.next();
        // 处理元素
    }
}

优点：操作简单，适合手动控制线程同步。

缺点：无法解决迭代时并发修改的问题，如果在迭代过程中修改集合，会抛出 ConcurrentModificationException。

使用 Collections.synchronizedList()

Collections.synchronizedList() 方法可以返回一个线程安全的列表，该列表在每个公共方法上都进行同步。适合在多线程环境下使用，但与手动同步类似，它也无法解决迭代过程中进行结构修改的问题。

java

List<String> list = Collections.synchronizedList(new ArrayList<>());

优点：通过标准库直接提供的线程安全包装，减少手动锁的复杂性。

缺点：迭代时仍需手动同步，无法避免结构性修改引发的并发问题。

使用并发集合 (CopyOnWriteArrayList)

CopyOnWriteArrayList 是 Java 并发包提供的线程安全集合类，其内部机制是每次修改（如添加或更新元素）都会复制整个底层数组。由于它的写操作会复制数组，因此读取操作不需要额外的同步，并且不会抛出 ConcurrentModificationException。

java

List<String> list = new CopyOnWriteArrayList<>();

优点：线程安全，迭代时不会因并发修改而抛出异常，读操作不需要加锁。

缺点：写操作性能较低，每次写入需要复制整个数组，适合读多写少的场景。

选择方案的建议：

读多写少：CopyOnWriteArrayList 是一个很好的选择，因为它对读操作的性能影响最小。
写操作频繁：在写操作占比高的情况下，手动同步（如使用 synchronized）或者选择其他更高效的并发集合（如 ConcurrentLinkedQueue）可能是更好的选择。

根据你的应用场景，选择合适的线程安全策略，可以有效提高性能和保障数据一致性。

聊聊常见Set类都有哪几种

在 Java 中，Set 是一种不包含重复元素的集合，它继承自 Collection 接口。Set 用于存储无序的元素，且元素的值不能重复。对象的相等性是通过对象的 hashCode 值（基于对象的内存地址计算）来判断的。如果希望两个不同的对象被视为相等，就必须重写 Object 类的 hashCode 和 equals 方法。Java 中常见的 Set 实现类主要有三个：HashSet、LinkedHashSet 和 TreeSet。

`HashSet`

特点: 基于哈希表实现，提供快速的插入、删除和查找操作。不保证元素的顺序，允许存在一个 null 元素。不是线程安全的，需外部同步。
适用场景: 需要快速查找，不关心元素的顺序。
自定义对象: 必须重写 hashCode() 和 equals() 方法以确保对象的唯一性。

`LinkedHashSet`

特点: 基于哈希表和双向链表实现，又基于 LinkedHashMap 实现，维护元素的插入顺序。继承了 HashSet 的所有特性，并且维护插入顺序。不是线程安全的，需外部同步.
适用场景: 需要保持元素的插入顺序。
自定义对象: 和 HashSet 一样，需要重写 hashCode() 和 equals() 方法。

`TreeSet`

特点: 基于红黑树实现，提供元素的自然排序或自定义排序。不允许存在 null 元素。不是线程安全的，需外部同步。
适用场景: 需要对元素进行排序。
自定义对象: 必须实现 Comparable 接口并重写 compareTo() 方法，或提供自定义的 Comparator 对象。

选择建议

HashSet: 快速查找，顺序无关。
LinkedHashSet: 保持插入顺序。
TreeSet: 元素排序。

HashSet如何实现线程安全

HashSet 本身不是线程安全的。如果多个线程在没有同步的情况下访问 HashSet，可能会出现数据不一致。以下几种方法可以将HashSet 变为线程安全：

使用 Collections.synchronizedSet 通过 Collections.synchronizedSet 返回一个同步的集合包装器。迭代时必须手动同步。

java

Set<String> synchronizedSet = Collections.synchronizedSet(new HashSet<>());
synchronized(synchronizedSet) {
    Iterator<String> iterator = synchronizedSet.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
}

使用 ConcurrentHashMap.newKeySet（基于ConcurrentHashMap的Set实现）提供高并发性能，使用 ConcurrentHashMap 来实现线程安全的 Set。 ConcurrentHashMap提供了更细粒度的锁机制，在高并发环境下性能更好，
java
```
Set<String> concurrentSet = ConcurrentHashMap.newKeySet();
```
1
使用 CopyOnWriteArraySet 适合读多写少的场景，基于 CopyOnWriteArrayList 实现，在每次修改时都会复制整个底层数组，因此在写操作较少时性能较好。
java
```
Set<String> copyOnWriteArraySet = new CopyOnWriteArraySet<>();
```
1

手动同步 使用 synchronized 关键字同步访问 HashSet。

java

Set<String> hashSet = new HashSet<>();
synchronized(hashSet) {
    // 对 hashSet 的操作
}

选择方案：

读操作多：CopyOnWriteArraySet
并发多：ConcurrentHashMap.newKeySet
简单同步：Collections.synchronizedSet

java

import java.util.set;
import java.util.concurrent.ConcurrentHashMap;
public class ConcurrentHashSetExamplepublic{ 
    public static void main(string[]args{
        Set<String>concurrentSet=ConcurrentHashMap.newKeySet();
        //多线程环境下的操作示例
        Runnabletask=()->{
            for(inti=0;i<1000;i++){
                concurrentSet.add(Thread.currentThread().getName()+"_" + i);
            }};
        Thread thread1 =new Thread(task, "Thread1");
        Thread thread2 =new Thread(task, "Thread2");
        thread1.start();
        thread2.start();
        try{
            thread1.join();
            thread2.join();
        }catch(InterruptedExceptione){
            e.printstackTrace();
        }
        System.out.println("set size:"+ concurrentSet.size());
    }
}

介绍一下HashMap

HashMap 用于存储键值对，基于哈希表实现，提供快速的插入、删除和查找操作。HashMap 允许一个 null 键和多个 null 值，但不保证键值对的顺序，特别是它不保证顺序会随着时间的推移保持不变。

主要方法

put(K key, V value): 将指定值与键关联，如果键已存在，则替换旧值。
get(Object key): 返回指定键的值，键不存在则返回 null。
remove(Object key): 移除指定键的映射。
containsKey(Object key): 判断是否包含指定键。
containsValue(Object value): 判断是否包含指定值。
size(): 返回映射中的键值对数量。
isEmpty(): 如果映射为空，则返回 true。
clear(): 移除所有键值对。

内部工作原理

哈希函数: 使用 hashCode() 方法计算键的哈希值，并映射到数组索引。
数组和链表: 使用数组存储链表（Java 8 及以后版本可能使用树）。数组位置称为“桶”。
冲突处理: 哈希冲突时，键会存储在同一个桶的链表或树中。
再哈希: 元素数量超过负载因子（默认 0.75）时，进行再哈希，扩大数组并重新分配元素。

性能注意事项

初始容量和负载因子: 通过构造函数设置初始容量和负载因子，以优化性能。初始容量越大，减少再哈希次数；负载因子越小，减少冲突概率但增加空间开销。
哈希函数的质量: 良好的哈希函数应均匀分布键，减少冲突。

线程安全性

非线程安全: HashMap 不是线程安全的。如果需要线程安全的映射，可以使用：
- Collections.synchronizedMap()：包装 HashMap 以实现线程安全。
- ConcurrentHashMap：在高并发环境下性能更优。

java

// 使用 Collections.synchronizedMap
Map<String, Integer> synchronizedMap = Collections.synchronizedMap(new HashMap<>());

// 使用 ConcurrentHashMap
Map<String, Integer> concurrentMap = new ConcurrentHashMap<>();

HashMap怎么计算hashCode

HashMap 使用键的 hashCode() 方法来生成哈希值，并通过扰动函数和数组索引计算来优化性能和均匀分布。

调用 hashCode() 方法HashMap 首先调用键对象的 hashCode() 方法获取哈希码，这是由对象的内部状态计算出的整数值。
java
```
int hashCode = key.hashCode();
```
1
扰动函数 (Perturbation Function) 为了减少哈希冲突并均匀分布哈希值，HashMap 对哈希码进行额外处理。Java 8 及以后的 HashMap 实现使用扰动函数：
java
```
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
```
1
2
3
4
- 获取键的哈希码：h = key.hashCode()
- 右移 16 位：h >>> 16
- 异或运算：h ^ (h >>> 16)
这种处理方法将高位和低位哈希码混合，从而减少哈希冲突，优化哈希表的性能。
补充：
让我们逐步分析它的含义：
1. h >>> 16：这是一个无符号右移操作，将整数 h 的位右移16位，忽略符号位（即在高位补零）。这意味着 h 的高16位被移到低16位的位置，而原来的低16位被丢弃。
2. h ^ ...：然后对 h 和 h >>> 16 进行**按位异或（XOR）**操作。XOR 操作的特点是，当两个位相同则结果为 0，不同则结果为 1。
这个操作的目的是将整数的高位和低位混合，从而生成一个更具随机性的结果，避免在哈希表中出现太多冲突。
例子：
假设 h = 0x12345678（十六进制表示，等于十进制的305419896）：
1. h >>> 16 的结果是 0x00001234。
2. h ^ (h >>> 16) 结果就是 0x12345678 ^ 0x00001234 = 0x1234444C。
这种技巧通常用于 Java 的哈希表实现（如 HashMap），来减少哈希冲突并提高查找性能。
计算数组索引 处理后的哈希值用于确定键值对在哈希表中的位置。HashMap 使用哈希值对数组长度进行按位与操作计算索引：
java
```
int index = (n - 1) & hash;
```
1
- n 是哈希表数组的长度，通常是 2 的幂次方。
- (n - 1) 是全 1 的二进制数，使得按位与操作 & 能高效替代取模操作 %。

通过这些步骤，HashMap 实现了高效的哈希值计算和均匀分布，优化了性能和冲突处理。

为什么要使用扰动函数

扰动函数用于提高哈希码的质量，使其在哈希表中更均匀地分布，主要有以下两个目的：

减少哈希冲突 扰动函数通过混合哈希码的高位和低位，降低了哈希码的模式性，从而减少了哈希冲突的概率。
均匀分布 经过扰动后的哈希码能够在哈希表的桶中更均匀地分布，从而提高了哈希表的整体性能。

为什么HashMap的容量扩充时一定是2的幂次

在 HashMap 中，初始化容量时长度会自动调整为 2 的幂次，这样设计主要是为了优化性能和简化计算：

高效计算索引
HashMap 使用哈希值来确定键值对在哈希表中的位置。为了计算数组索引，HashMap 使用按位与操作代替取模运算。具体计算方式如下：
java
```
int index = (n - 1) & hash;
```
1
其中，n 是哈希表数组的长度。如果 n 是 2 的幂次（例如 16），则 n - 1 是 15（二进制为 1111）。这样 (n - 1) & hash 可以快速地对哈希值进行取模运算，而无需使用性能较低的取模操作 %。
减少哈希冲突
哈希冲突是指不同的键计算出相同的索引，导致它们存储在同一个桶中。将容量设置为 2 的幂次可以更均匀地分布哈希值，减少冲突。当容量为 2 的幂次时，哈希值的低位和高位都会均匀影响最终索引。扰动函数 hash = h ^ (h >>> 16) 通过将高位和低位混合，帮助减少冲突。
简化扩容过程
HashMap 在扩容时通常会将容量加倍。如果容量总是 2 的幂次，加倍后的容量仍然是 2 的幂次，这样可以简化扩容过程中的计算和重新哈希操作。
内存对齐和效率
计算机内存分配通常更高效地处理 2 的幂次大小的内存块。使用 2 的幂次长度可以更好地利用内存对齐，提高内存访问效率。

实现细节

当初始化 HashMap 时，指定的初始容量会被调整为大于或等于该值的最小 2 的幂次。例如，如果指定的初始容量是 10，HashMap 会将其调整为 16（2^4）。

具体实现如下：

java

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;
}

这个方法通过位移和按位或操作，将任意整数调整为大于或等于它的最小 2 的幂次。如果数字本身就是 2 的幂次（如 4），计算结果会是 8。为了解决这个问题，JDK 的工程师在计算前将所有用户传入的数减去 1。

HashMap的主要参数有哪些

以下是对HashMap关键概念的优化总结：

初始容量 (Initial Capacity)
HashMap创建时分配的桶数组的初始大小，默认为16。可以通过构造函数指定：
java
```
HashMap<K, V> map = new HashMap<>(initialCapacity);
```
1
负载因子 (Load Factor)
控制HashMap扩容的阈值，默认0.75。当条目数达到当前容量的75%时，HashMap会扩容。负载因子较低时，空间利用率下降，但冲突减少：
java
```
HashMap<K, V> map = new HashMap<>(initialCapacity, loadFactor);
```
1
阈值 (Threshold)
扩容的临界点，计算方式为初始容量乘以负载因子。当实际条目数超过此值时，HashMap会扩容。
桶 (Bucket)
HashMap使用数组存储链表或树（在Java 8及之后版本中，链表长度超限时转换为树）。每个数组元素称为一个桶，哈希值决定了键值对存储位置。

哈希函数 (Hash Function)

将键的哈希码转换为数组索引。使用扰动函数提高哈希码质量，减少冲突：

java

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

链表和树 (Linked List and Tree)
初期使用链表处理哈希冲突；当链表长度超过8时，转为红黑树以提高效率。
红黑树转换阈值 (Treeify Threshold)
链表长度超过此值时，转换为红黑树。默认值为8。
最小树化容量 (Minimum Treeify Capacity)
当容量小于此值时，即使链表长度超过Treeify Threshold，也不会将链表转换为红黑树，而是会先进行扩容。默认值是64。
扩容因子 (Resize Factor)
扩容时，容量加倍，新容量为旧容量的两倍。
迭代器 (Iterators)

提供键、值和条目的迭代器。迭代器是 快速失败（fail-fast） 的，若在迭代过程中结构被修改（除非通过迭代器的remove方法），会抛出ConcurrentModificationException。

版本 (ModCount)
内部版本号modCount用于跟踪结构修改次数，帮助检测并发修改。

解决Hash碰撞的方法

以下是关于哈希冲突解决方法的简洁优化总结：

链地址法 (Chaining)
描述: 使用链表（或在Java 8及以上版本中使用红黑树）存储碰撞的元素。
优点:
- 实现简单。
- 动态调整链表长度，无需提前知道元素数量。
缺点:
- 链表长度增加时查找效率下降。
- 需要额外的存储空间来存储链表指针。
示例:
java
```
class HashMapNode<K, V> {
    K key;
    V value;
    HashMapNode<K, V> next;
    HashMapNode(K key, V value) {
        this.key = key;
        this.value = value;
    }
}
```
1
2
3
4
5
6
7
8
9

开放地址法 (Open Addressing)

描述: 在哈希表中寻找空闲位置存储碰撞的元素，无需链表。

常见类型:

线性探测 (Linear Probing)

优点: 实现简单，无需额外存储空间。

缺点: 查找效率在哈希表接近满时下降（主群集问题）。

示例:

java

int hash = key.hashCode() % table.length;
while (table[hash] != null) {
    hash = (hash + 1) % table.length;
}
table[hash] = new Entry(key, value);

二次探测 (Quadratic Probing)

优点: 减少主群集问题。

缺点: 实现复杂，可能引发二次群集问题。

示例:

java

int hash = key.hashCode() % table.length;
int i = 1;
while (table[hash] != null) {
    hash = (hash + i * i) % table.length;
    i++;
}
table[hash] = new Entry(key, value);

双重散列 (Double Hashing)

优点: 减少群集问题，查找性能较好。

缺点: 实现复杂，需要设计两个有效的哈希函数。

示例:

java

int hash1 = key.hashCode() % table.length;
int hash2 = 1 + (key.hashCode() % (table.length - 1));
while (table[hash1] != null) {
    hash1 = (hash1 + hash2) % table.length;
}
table[hash1] = new Entry(key, value);

再哈希法 (Rehashing)
描述: 当发生冲突时，使用另一个哈希函数再次计算键的哈希值，直到找到空闲位置。
优点: 减少群集问题。
缺点: 实现复杂，需要多个有效的哈希函数。
分离链接法 (Separate Chaining with Linked List or Tree)
描述: 链表长度超过阈值时，转换为红黑树（Java 8及以上版本）。
优点:
- 高冲突情况下性能较好。
- 动态调整链表和树的长度。
缺点:
- 实现复杂。
- 需要额外的存储空间。
其他方法
- Cuckoo Hashing: 使用两个哈希表和两个哈希函数，如果插入时发生冲突，将原来的元素“踢出”并重新插入到另一个哈希表中。
- Hopscotch Hashing: 类似于线性探测，但在插入时调整元素位置，使查找路径更短。

链地址法适用于大多数情况，开放地址法在空间利用率上有优势但在高负载情况下性能可能下降。再哈希法和其他高级方法适用于特定的高性能需求场景。

HashMap的大小为什么是2的n次方大小呢?

在 JDK1.7 中，HashMap 整个扩容过程就是分别取出数组元素，一般该元素是最后一个放入链表中的元素，然后遍历以该元素为头的单向链表元素，依据每个被遍历元素的 hash 值计算其在新数组中的下标，然后进行交换。这样的扩容方式会将原来哈希冲突的单向链表尾部变成扩容后单向链表的头部。（因为1.7是头插法）

而在 JDK 1.8 中，HashMap 对扩容操作做了优化。由于扩容数组的长度是2倍关系，所以对于假设初始 tablesize=4 要扩容到8来说就是 0100 到 1000 的变化(左移一位就是2倍)，在扩容中只用判断原来的 hash 值在之前 tablesize=4 时的前一位是0还是1即可，0 的话索引不变，1的话索引变成原索引加上扩容前数组。

HashMap的负载因子初始值为什么是0.75

HashMap的负载因子（load factor）初始值设为0.75是一个经过权衡的选择，主要考虑了性能与内存使用之间的平衡。以下是主要原因：

性能与内存使用的平衡
- 查找性能: HashMap的查找操作时间复杂度接近O(1) 。如果负载因子过高，会导致链表较长，查找时间增加。负载因子为0.75时，哈希表在达到75%满时扩容，这有助于保持链表较短，确保高效的查找操作。
- 内存使用: 较低的负载因子（如0.5）会导致更频繁的扩容，从而占用更多的内存来存储未使用的桶。0.75的负载因子在保持查找性能的同时，能有效节约内存。
扩容频率
- 较高负载因子（如1.0）: 减少扩容频率，但可能导致较长的链表和更多的哈希碰撞，从而影响查找性能。
- 较低负载因子（如0.5）: 增加扩容频率，减少碰撞，但会导致空间浪费。
- 0.75: 这是一个折中的选择，能够平衡较少的哈希碰撞和扩容的频率，优化性能和内存使用。
实际应用中的经验
- 通用性: 0.75被证明是一个有效的默认值，能够在大多数情况下提供良好的性能和合理的内存使用。
- 经验验证: 在实际应用中，这个默认值经过大量实践验证，是一个在性能和内存使用之间的有效折中。
负载因子的灵活性
- 可调整性: 尽管默认负载因子是0.75，开发者可以根据具体需求调整。例如：
  java
```
Map<Integer, String> map = new HashMap<>(initialCapacity, 0.5f);
```
  1
- 应用场景: 如果需要更高的查找性能但内存使用不是主要考虑因素，可以设置为0.5。

默认负载因子0.75在HashMap中经过深思熟虑，旨在平衡查找性能和内存使用。在大多数场景下，它能提供良好的性能表现，避免频繁扩容和过多的内存浪费。开发者可以根据具体需求调整负载因子，以适应不同的应用场景。

ElasticSearch

MQ

Redis

集合篇(上)

介绍一下常见的list的实现类

ArrayList初始容量是多少

ArrayList是如何扩容的

ArrayList添加和删除元素为什么慢

ArrayList是线程安全的吗

ArrayList如何保证线程安全

聊聊常见Set类都有哪几种

`HashSet`

`LinkedHashSet`

`TreeSet`

选择建议

HashSet如何实现线程安全

选择方案：

介绍一下HashMap

主要方法

内部工作原理

性能注意事项

线程安全性

HashMap怎么计算hashCode

为什么要使用扰动函数

为什么HashMap的容量扩充时一定是2的幂次

HashMap的主要参数有哪些

解决Hash碰撞的方法

HashMap的大小为什么是2的n次方大小呢?

HashMap的负载因子初始值为什么是0.75

集合篇(上) ​

介绍一下常见的list的实现类 ​

ArrayList初始容量是多少 ​

ArrayList是如何扩容的 ​

ArrayList添加和删除元素为什么慢 ​

ArrayList是线程安全的吗 ​

ArrayList如何保证线程安全 ​

聊聊常见Set类都有哪几种 ​

HashSet ​

LinkedHashSet ​

TreeSet ​

选择建议 ​

HashSet如何实现线程安全 ​

选择方案： ​

介绍一下HashMap ​

主要方法 ​

内部工作原理 ​

性能注意事项 ​

线程安全性 ​

HashMap怎么计算hashCode ​

为什么要使用扰动函数 ​

为什么HashMap的容量扩充时一定是2的幂次 ​

HashMap的主要参数有哪些 ​

解决Hash碰撞的方法 ​

HashMap的大小为什么是2的n次方大小呢? ​

HashMap的负载因子初始值为什么是0.75 ​

集合篇(上)

介绍一下常见的list的实现类

ArrayList初始容量是多少

ArrayList是如何扩容的

ArrayList添加和删除元素为什么慢

ArrayList是线程安全的吗

ArrayList如何保证线程安全

聊聊常见Set类都有哪几种

`HashSet`

`LinkedHashSet`

`TreeSet`

选择建议

HashSet如何实现线程安全

选择方案：

介绍一下HashMap

主要方法

内部工作原理

性能注意事项

线程安全性

HashMap怎么计算hashCode

为什么要使用扰动函数

为什么HashMap的容量扩充时一定是2的幂次

HashMap的主要参数有哪些

解决Hash碰撞的方法

HashMap的大小为什么是2的n次方大小呢?

HashMap的负载因子初始值为什么是0.75