发表于 | 更新于 | 分类于
字数统计 | 阅读时长

👌java8的hashmap实现？

题目详细答案

在Java 8中，HashMap的实现进行了显著的优化，特别是在处理哈希冲突方面，引入了红黑树数据结构。这些改进旨在提高在高冲突情况下的性能。

数据结构

HashMap的底层结构仍然是基于数组和链表的组合，但在Java 8中，当链表长度超过一定阈值时，会将链表转换为红黑树，以提高操作效率。

存储过程

  1. 计算哈希值：首先，通过键的hashCode方法计算哈希值，然后对该哈希值进行扰动，以减少冲突。扰动的目的是为了使哈希值更加均匀地分布在数组中。
1
2
3
4
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
  1. 确定数组索引：通过哈希值与数组长度的减一值进行按位与运算，计算出数组的索引位置。
1
2
3
static int indexFor(int h, int length) {
    return h & (length - 1);
}
  1. 插入节点：

如果数组索引位置为空，直接插入新的节点。

如果不为空，则需要处理哈希冲突。

处理哈希冲突

在Java 8中，处理哈希冲突的方法有了显著改进：

  1. 链表：如果冲突的节点数较少（链表长度小于等于8），则使用链表存储。链表的插入操作在链表尾部进行，以保持插入顺序。
  2. 红黑树：如果链表长度超过8，长度大于 64HashMap会将链表转换为红黑树。红黑树是一种自平衡的二叉搜索树，其查找、插入和删除操作的时间复杂度为O(log n)，相比链表的O(n)更高效。
1
2
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    treeifyBin(tab, hash);

取值过程

在取值时，HashMap会先计算哈希值，然后找到对应的数组位置。如果该位置存储的是链表，则遍历链表查找；如果是红黑树，则在树中查找。

扩容

当HashMap中的元素数量超过一定阈值（通常是数组长度的0.75倍）时，会进行扩容。扩容时，HashMap会创建一个新的、更大的数组，并将旧数组中的所有元素重新哈希并放入新数组中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
void resize(int newCapacity) {
    Node<K,V>[] oldTable = table;
    int oldCapacity = oldTable.length;
    Node<K,V>[] newTable = (Node<K,V>[])new Node[newCapacity];
    // Rehashing elements to new table
    for (int j = 0; j < oldCapacity; ++j) {
        Node<K,V> e;
        if ((e = oldTable[j]) != null) {
            oldTable[j] = null;
            if (e.next == null)
                newTable[e.hash & (newCapacity - 1)] = e;
            else if (e instanceof TreeNode)
                ((TreeNode<K,V>)e).split(this, newTable, j, oldCapacity);
            else { // preserve order
                Node<K,V> loHead = null, loTail = null;
                Node<K,V> hiHead = null, hiTail = null;
                Node<K,V> next;
                do {
                    next = e.next;
                    if ((e.hash & oldCapacity) == 0) {
                        if (loTail == null)
                            loHead = e;
                        else
                            loTail.next = e;
                        loTail = e;
                    }
                    else {
                        if (hiTail == null)
                            hiHead = e;
                        else
                            hiTail.next = e;
                        hiTail = e;
                    }
                } while ((e = next) != null);
                if (loTail != null) {
                    loTail.next = null;
                    newTable[j] = loHead;
                }
                if (hiTail != null) {
                    hiTail.next = null;
                    newTable[j + oldCapacity] = hiHead;
                }
            }
        }
    }
    table = newTable;
}

Java 8中的HashMap通过引入红黑树来优化哈希冲突的处理。当链表长度超过一定阈值时转换为红黑树，从而在极端情况下提高查找和插入的效率。这些改进使得HashMap在大多数情况下能够提供更稳定和高效的性能。

/uxrna62kfc64guwy>

发表于 | 更新于 | 分类于
字数统计 | 阅读时长

👌jdk7的ConcurrentHashMap实现？

题目详细答案

在JDK 7中，ConcurrentHashMap的实现与JDK 8有所不同。JDK 7中的ConcurrentHashMap使用了分段锁（Segment Locking）来实现高并发性能。

主要结构

JDK 7中的ConcurrentHashMap由以下几个主要部分组成：

  1. Segment：分段锁的核心，每个Segment是一个小的哈希表，拥有独立的锁。
  2. HashEntry：哈希表中的每个节点，存储键值对。
  3. ConcurrentHashMap：包含多个Segment，每个Segment管理一部分哈希表。

Segment 类

Segment类是ReentrantLock的子类，它是ConcurrentHashMap的核心部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
static final class Segment<K,V> extends ReentrantLock implements Serializable {
    transient volatile HashEntry<K,V>[] table;
    transient int count;
    transient int modCount;
    transient int threshold;
    final float loadFactor;

    Segment(float lf, int threshold, HashEntry<K,V>[] tab) {
        this.loadFactor = lf;
        this.threshold = threshold;
        this.table = tab;
    }
}

HashEntry 类

HashEntry类是哈希表中的节点，存储键值对和指向下一个节点的指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
static final class HashEntry<K,V> {
    final K key;
    final int hash;
    volatile V value;
    volatile HashEntry<K,V> next;

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

ConcurrentHashMap 类

ConcurrentHashMap类包含多个Segment，每个Segment管理一部分哈希表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
    implements ConcurrentMap<K,V>, Serializable {

    final Segment<K,V>[] segments;
    transient Set<K> keySet;
    transient Set<Map.Entry<K,V>> entrySet;
    transient Collection<V> values;
    static final int DEFAULT_INITIAL_CAPACITY = 16;
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    static final int DEFAULT_CONCURRENCY_LEVEL = 16;
    static final int MAXIMUM_CAPACITY = 1 << 30;
    static final int MIN_SEGMENT_TABLE_CAPACITY = 2;
    static final int MAX_SEGMENTS = 1 << 16; // slightly conservative

    // Other fields and methods...
}

put 操作

put操作是ConcurrentHashMap的核心操作之一，以下是其简化版实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public V put(K key, V value) {
    Segment<K,V> s;
    if (value == null)
        throw new NullPointerException();
    int hash = hash(key);
    int j = (hash >>> segmentShift) & segmentMask;
    if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
         (segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
        s = ensureSegment(j);
    return s.put(key, hash, value, false);
}

final V put(K key, int hash, V value, boolean onlyIfAbsent) {
    HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value);
    V oldValue;
    try {
        HashEntry<K,V>[] tab = table;
        int index = (tab.length - 1) & hash;
        HashEntry<K,V> first = entryAt(tab, index);
        for (HashEntry<K,V> e = first;;) {
            if (e != null) {
                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 {
                if (node != null)
                    node.setNext(first);
                else
                    node = new HashEntry<K,V>(key, hash, first, value);
                int c = count + 1;
                if (c > threshold && tab.length < MAXIMUM_CAPACITY)
                    rehash(node);
                else
                    setEntryAt(tab, index, node);
                ++modCount;
                count = c;
                oldValue = null;
                break;
            }
        }
    } finally {
        unlock();
    }
    return oldValue;
}

get 操作

get操作是ConcurrentHashMap的另一个核心操作，以下是其简化版实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public V get(Object key) {
    Segment<K,V> s;
    HashEntry<K,V>[] tab;
    int h = hash(key);
    long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
    if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
        (tab = s.table) != null) {
        for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
                 (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
             e != null; e = e.next) {
            K k;
            if ((k = e.key) == key || (e.hash == h && key.equals(k)))
                return e.value;
        }
    }
    return null;
}

主要特点

  1. 分段锁：ConcurrentHashMap将整个哈希表分成多个Segment，每个Segment是一个独立的小哈希表，拥有自己的锁。这样不同的线程可以并发地访问不同的Segment，显著提高并发性能。
  2. 高效并发：通过细粒度的锁机制，ConcurrentHashMap在高并发环境下表现出色，避免了全表锁的性能瓶颈。
  3. 线程安全：所有的操作都在锁的保护下进行，确保了线程安全性。

JDK 7中的ConcurrentHashMap通过分段锁机制实现高并发性能。每个Segment是一个独立的小哈希表，拥有自己的锁，允许多个线程并发地访问不同的Segment。这种设计在高并发环境下显著提高了性能，同时保证了线程安全性。

/krsz9bcuq049gs4t>

发表于 | 更新于 | 分类于
字数统计 | 阅读时长

👌jdk7的hashmap实现？

题目详细答案

HashMap在 JDK 7 中的实现其实并不复杂，它主要依靠两个数据结构：数组和链表。

首先，HashMap内部有一个数组，这个数组用来存储所有的键值对。每个数组的元素其实是一个链表的头节点。也就是说，如果两个或多个键计算出来的哈希值相同，它们会被存储在同一个数组位置的链表中。

当我们往HashMap里放一个键值对时，HashMap会先根据键的hashCode计算出一个哈希值，然后用这个哈希值决定键值对应该放在数组的哪个位置。如果那个位置是空的，键值对就直接放进去；如果那个位置已经有其他键值对了（也就是发生了哈希冲突），HashMap会把新的键值对放到那个位置的链表上。

举个例子吧，假设我们有一个HashMap，我们要往里面放一个键值对(“apple”, 1)。HashMap会先计算”apple”的哈希值，然后用这个哈希值决定应该把它放到数组的哪个位置。假如计算出来的位置是 5，如果数组的第 5 个位置是空的，它就直接放进去；如果已经有其他键值对了，比如(“banana”, 2)，它就会把(“apple”, 1)加到(“banana”, 2)的链表上。

取值的时候也类似。假设我们要取”apple”对应的值，HashMap会先计算”apple”的哈希值，然后找到数组的对应位置，再沿着链表找到”apple”对应的节点，最后返回它的值。

需要注意的是，HashMap不是线程安全的。如果多个线程同时修改HashMap，可能会导致一些奇怪的问题，比如死循环。所以在多线程环境下，建议使用ConcurrentHashMap。

总结一下，HashMap在 JDK 7 中主要是通过数组和链表来存储数据，使用哈希值来决定存储位置，并通过链表来解决哈希冲突。它的设计让我们在大多数情况下能够快速地存取数据，但在多线程环境下需要小心使用。

JDK 7 中的HashMap底层实现方式主要基于数组和链表。它通过哈希函数将键映射到数组中的索引位置，从而实现快速的查找和存储操作。

数据结构

HashMap主要由以下几部分组成：

数组（table）：存储HashMap的核心数据结构。每个数组元素是一个链表的头节点。

链表（Entry）：处理哈希冲突的结构。当多个键的哈希值映射到同一个数组索引时，这些键值对会被存储在该索引位置的链表中。

Entry 类

在 JDK 7 中，HashMap使用一个内部类Entry来表示键值对。Entry类的定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
static class Entry<K, V> implements Map.Entry<K, V> {
    final K key;
    V value;
    Entry<K, V> next;
    final int hash;

    Entry(int h, K k, V v, Entry<K, V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }

    public final K getKey() {
        return key;
    }

    public final V getValue() {
        return value;
    }

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

    public final boolean equals(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry e = (Map.Entry) o;
        Object k1 = getKey();
        Object k2 = e.getKey();
        if (k1 == k2 || (k1 != null && k1.equals(k2))) {
            Object v1 = getValue();
            Object v2 = e.getValue();
            if (v1 == v2 || (v1 != null && v1.equals(v2)))
                return true;
        }
        return false;
    }

    public final int hashCode() {
        return (key == null ? 0 : key.hashCode()) ^
               (value == null ? 0 : value.hashCode());
    }

    public final String toString() {
        return getKey() + "=" + getValue();
    }
}

存储过程

当向HashMap中存储一个键值对时，主要步骤如下：

  1. 计算哈希值：通过键的hashCode()方法计算哈希值，并进一步处理以减少冲突。
  2. 确定数组索引：通过哈希值计算数组索引位置。
  3. 插入节点：如果数组索引位置为空，则直接插入。如果不为空，则需要处理哈希冲突。

处理哈希冲突

在 JDK 7 中，HashMap通过链表法处理哈希冲突。当多个键的哈希值映射到同一个数组索引时，这些键值对会被存储在该索引位置的链表中。插入时，新节点会被插入到链表的头部。

代码示例

以下是put方法的简化版本，展示了HashMap的存储过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K, V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key.hashCode()) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K, V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

取值过程

取值时，通过键计算哈希值和数组索引，然后在链表中查找对应的键值对。

1
2
3
4
5
6
7
8
9
10
11
12
13
public V get(Object key) {
    if (key == null)
        return getForNullKey();
    int hash = hash(key.hashCode());
    for (Entry<K, V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }
    return null;
}

/yafahumkqtgcnav4>

发表于 | 更新于 | 分类于
字数统计 | 阅读时长

👌jdk8的hashmap的put过程？

题目详细答案

put方法的实现

1
2
3
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

put方法调用了putVal方法。这里的hash(key)是计算键的哈希值。

计算哈希值

hash方法用于计算键的哈希值并进行扰动处理，以减少冲突。

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

putVal方法的实现

putVal方法是HashMap中实际执行插入操作的核心方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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
                        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;
}

详细步骤解析

  1. 初始化表：如果哈希表还没有初始化或长度为0，则进行初始化（扩容）。
1
2
if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
  1. 计算索引：通过哈希值和数组长度计算出索引位置。
1
2
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
  1. 插入新节点：如果索引位置为空，直接插入新节点。
  2. 处理哈希冲突：如果索引位置不为空，需要处理冲突。

检查是否存在相同的键：如果找到相同的键，替换其值。

红黑树处理：如果当前节点是红黑树节点，则调用putTreeVal方法插入。

链表处理：如果当前节点是链表节点，遍历链表插入新节点。

  1. 转换为红黑树：如果链表长度超过阈值（8）且数组长度大于 64，则将链表转换为红黑树。
1
2
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    treeifyBin(tab, hash);
  1. 更新节点值：如果存在相同的键，更新其值。
1
2
3
4
5
6
7
if (e != null) { // existing mapping for key
    VoldValue= e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    afterNodeAccess(e);
    return oldValue;
}
  1. 调整大小：插入新节点后，增加元素数量。如果超过阈值，则进行扩容。
1
2
++modCount;if (++size > threshold)
    resize();
  1. 插入后的处理：进行一些插入后的处理操作。
1
afterNodeInsertion(evict);

/cvh030rky8ki5bhi>

发表于 | 更新于 | 分类于
字数统计 | 阅读时长

👌linkedHashMap为什么能用来做LRUCache？

题目详细答案

LinkedHashMap 能用来做 LRU 缓存的关键原因在于它可以维护访问顺序，并且通过重写removeEldestEntry方法，可以轻松实现缓存的自动清理。

关键特性

访问顺序：LinkedHashMap提供了一个构造方法，可以指定是否按照访问顺序来维护键值对的顺序。当accessOrder参数设置为true时，LinkedHashMap将根据每次访问（get或put操作）来调整顺序，把最近访问的键值对移到链表的末尾。

自动清理：通过重写removeEldestEntry方法，可以在插入新键值对时自动移除最老的键值对（即链表头部的键值对），从而实现缓存的自动清理。

实现 LRU 缓存的步骤

  1. 创建一个LinkedHashMap实例，并将accessOrder参数设置为true。
  2. 重写removeEldestEntry方法，以便在缓存大小超过预定义的最大容量时自动移除最老的键值对。

代码 Demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxCapacity;

    // 构造函数，初始化最大容量和访问顺序
    public LRUCache(int maxCapacity) {
        super(maxCapacity, 0.75f, true);
        this.maxCapacity = maxCapacity;
    }

    // 重写removeEldestEntry方法，当大小超过最大容量时移除最老的键值对
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxCapacity;
    }

    public static void main(String[] args) {
        // 创建一个容量为3的LRU缓存
        LRUCache<String, Integer> cache = new LRUCache<>(3);

        // 插入键值对
        cache.put("A", 1);
        cache.put("B", 2);
        cache.put("C", 3);

        // 访问键"A"（使其成为最近使用的）
        cache.get("A");

        // 插入新键值对"D"，导致最老的键值对"B"被移除
        cache.put("D", 4);

        // 打印缓存内容
        System.out.println(cache); // 输出: {C=3, A=1, D=4}
    }
}

解释

构造方法：LRUCache构造方法中调用了LinkedHashMap的构造方法，并将accessOrder参数设置为true，以便按照访问顺序维护键值对的顺序。

removeEldestEntry 方法：重写了removeEldestEntry方法，当缓存的大小超过maxCapacity时返回true，从而移除最老的键值对。

使用示例：在主方法中创建了一个LRUCache实例，插入了几个键值对，并通过访问键 “A” 来改变其顺序。然后插入一个新键值对 “D”，导致最老的键值对 “B” 被移除。

/rv2p9mfn43gmr2qn>

发表于 | 更新于 | 分类于
字数统计 | 阅读时长

👌linkedhashmap如何保证有序性？

题目详细答案

LinkedHashMap通过维护一个双向链表来保证有序性。这个双向链表记录了所有插入的键值对的顺序。根据构造方法中的参数设置，LinkedHashMap可以按插入顺序或访问顺序来维护这些键值对的顺序。

具体实现原理

  1. 双向链表：LinkedHashMap在内部维护了一个双向链表。每个节点对应一个键值对，并且包含指向前一个节点和后一个节点的引用。通过这个链表，LinkedHashMap可以快速地遍历所有键值对，保持其有序性。
  2. 插入顺序：默认情况下，LinkedHashMap按照键值对插入的顺序来维护顺序。每次插入新键值对时，它会将新节点添加到链表的末尾。
  3. 访问顺序：如果在构造方法中将accessOrder参数设置为true，LinkedHashMap将按照访问顺序来维护键值对的顺序。每次访问（get或put操作）一个键值对时，它会将对应的节点移动到链表的末尾。

代码 Demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapOrderExample {
    public static void main(String[] args) {
        // 插入顺序
        LinkedHashMap<String, Integer> insertionOrderMap = new LinkedHashMap<>();
        insertionOrderMap.put("A", 1);
        insertionOrderMap.put("B", 2);
        insertionOrderMap.put("C", 3);

        System.out.println("插入顺序:");
        for (Map.Entry<String, Integer> entry : insertionOrderMap.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }

        // 访问顺序
        LinkedHashMap<String, Integer> accessOrderMap = new LinkedHashMap<>(16, 0.75f, true);
        accessOrderMap.put("A", 1);
        accessOrderMap.put("B", 2);
        accessOrderMap.put("C", 3);

        // 访问某些元素
        accessOrderMap.get("A");
        accessOrderMap.get("C");

        System.out.println("访问顺序:");
        for (Map.Entry<String, Integer> entry : accessOrderMap.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

解释

插入顺序：

创建一个LinkedHashMap实例insertionOrderMap。

插入键值对 “A”、”B” 和 “C”。

遍历并打印键值对，顺序与插入顺序一致。

访问顺序：

创建一个LinkedHashMap实例accessOrderMap，并将accessOrder参数设置为true。

插入键值对 “A”、”B” 和 “C”。

访问键 “A” 和 “C”（通过get操作）。

遍历并打印键值对，顺序按照最近访问的顺序排列。

内部机制

节点结构：LinkedHashMap的每个节点不仅包含键和值，还包含指向前一个节点和后一个节点的引用。这使得它可以高效地维护顺序。

操作调整：在每次插入或访问键值对时，LinkedHashMap会调整链表中节点的位置，以确保顺序的正确性。例如，在访问顺序模式下，每次访问一个键值对时，它会将对应的节点移动到链表的末尾。

通过这些机制，LinkedHashMap能够高效地维护键值对的有序性，无论是按插入顺序还是访问顺序。

/sgl9ep03rn5cwda1>

发表于 | 更新于 | 分类于
字数统计 | 阅读时长

👌为什么String, Interger这样的wrapper类适合作为键？

题目详细答案

不可变性

String和Integer等包装类都是不可变的对象。一旦创建，这些对象的状态就不能被改变。不可变性是一个重要的特性，因为它保证了对象在其生命周期内的哈希码（hash code）不会改变。

如果一个对象在作为键的过程中其哈希码发生了改变，那么在哈希表中查找该键时将无法找到正确的位置，导致数据结构无法正常工作。不可变对象避免了这一问题。

合理的hashCode()实现

String和Integer类都提供了高质量的hashCode()方法，这些方法能够有效地分布哈希值，减少哈希冲突。具体来说：

String的hashCode()方法是基于字符串内容计算的，使用了一个高效的算法。

Integer的hashCode()方法直接返回其内部存储的整数值。

合理的equals()实现

String和Integer类都提供了正确且高效的equals()方法，这些方法能够准确地比较两个对象的内容是否相等。这对于哈希表等数据结构来说是至关重要的，因为在哈希表中查找键时需要依赖equals()方法来判断两个键是否相等。

内存效率

虽然包装类相对于原始类型有一些额外的内存开销，但这些类通常经过了优化，能够在大多数情况下提供足够的性能和内存效率。例如，Integer类使用了对象池来缓存常用的整数值（-128 到 127），从而减少了内存消耗和对象创建的开销。

发表于 | 更新于 | 分类于
字数统计 | 阅读时长

👌为什么hashMap的容量扩容时一定是2的幂次?

题目详细答案

在HashMap中，初始化设置长度时，容量自动转成 2 的幂次长度，这样设计有几个重要原因，主要是为了优化性能和简化计算。

高效计算索引

HashMap使用哈希值来确定键值对在哈希表中的位置。为了计算数组索引，HashMap使用按位与操作代替取模运算。具体来说，HashMap通过以下方式计算索引：

1
int index= (n - 1) & hash;

其中n是哈希表数组的长度。假设n是 2 的幂次，比如 16（2^4），则n - 1是 15（1111 二进制）。这样，(n - 1) & hash操作可以快速地对哈希值进行取模运算，而不需要使用性能较低的取模操作%。

例如，如果n是 16（2^4）：

  • n - 1是 15（1111 二进制）
  • 按位与操作(n - 1) & hash只保留哈希值的低 4 位，这相当于对 16 取模。

这种方式不仅计算快速，而且代码简洁。

减少哈希冲突

在哈希表中，哈希冲突是一个主要问题。哈希冲突发生时，不同的键计算出的索引相同，导致它们被存储在同一个桶中。通过将容量设置为 2 的幂次，哈希表能够更均匀地分布哈希值，减少冲突。

具体来说，当容量是 2 的幂次时，哈希值的低位和高位都能均匀地影响最终索引。这是因为扰动函数hash = h ^ (h >>> 16)将高位和低位混合在一起，使得哈希值的分布更均匀。

假设我们有一个HashMap，其容量为 10（不是 2 的幂次），并且我们有一组键，它们的哈希值分别为：

  • 键 A 的哈希值：35
  • 键 B 的哈希值：45
  • 键 C 的哈希值：55

（1）使用非 2 的幂次容量

如果容量为 10，我们计算索引的方法是取模运算：

  • 键 A 的索引：35 % 10 = 5
  • 键 B 的索引：45 % 10 = 5
  • 键 C 的索引：55 % 10 = 5

可以看到，这些不同的键在取模运算后都映射到同一个索引 5，导致了哈希冲突。

（2）使用 2 的幂次容量

现在假设我们将容量设置为 16（2^4），并使用按位与操作来计算索引：

  • 键 A 的索引：35 & (16 - 1) = 35 & 15 = 3
  • 键 B 的索引：45 & (16 - 1) = 45 & 15 = 13
  • 键 C 的索引：55 & (16 - 1) = 55 & 15 = 7

在这种情况下，这些键映射到不同的索引（3、13 和 7），没有发生哈希冲突。

简化扩容

HashMap在需要扩容时，通常会将容量加倍。如果容量总是 2 的幂次，那么加倍后的容量仍然是 2 的幂次，这样可以简化扩容过程中的计算和重新哈希操作。

内存对齐和效率

计算机内存分配通常更高效地处理 2 的幂次大小的内存块。使用 2 的幂次长度可以更好地利用内存对齐，提高内存访问效率。

实现细节

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

具体实现如下：

1
2
3
4
5
6
7
8
9
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。

/yfxseowdd8g5hm0e>

发表于 | 更新于 | 分类于
字数统计 | 阅读时长

👌为什么hashmap多线程会进入死循环？

题目详细答案

HashMap在多线程环境中可能会进入死循环，主要是由于其非线程安全的设计导致的。

并发修改导致的链表环

在HashMap中，当发生哈希冲突时，使用链地址法（链表）来存储冲突的键值对。如果多个线程同时对HashMap进行修改（例如插入或删除操作），可能会导致链表结构被破坏，形成环形链表。这种情况下，当遍历链表时，会陷入死循环。

原因分析

当两个或多个线程同时修改HashMap，例如在同一个桶中插入元素，可能会导致链表的指针被错误地更新。例如，一个线程正在将一个新的节点插入链表中，而另一个线程正在重新排列链表的顺序。这种竞争条件可能导致链表中出现环形结构。

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.HashMap;
import java.util.Map;

public class HashMapInfiniteLoop {
    public static void main(String[] args) {
        final Map<Integer, Integer> map = new HashMap<>();

        // 创建两个线程同时对 HashMap 进行插入操作
        Thread t1 = new Thread(() -> {
            for (int i = 0; i < 10000; i++) {
                map.put(i, i);
            }
        });

        Thread t2 = new Thread(() -> {
            for (int i = 10000; i < 20000; i++) {
                map.put(i, i);
            }
        });

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

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

        // 遍历 HashMap，可能会陷入死循环
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " : " + entry.getValue());
        }
    }
}

在上述代码中，两个线程同时对HashMap进行插入操作，可能会导致链表结构被破坏，形成环形链表，从而在遍历时陷入死循环。

扩容导致的并发问题

HashMap在容量达到一定阈值时会进行扩容（rehash），即重新分配桶数组，并重新哈希所有键值对。如果在扩容过程中，有其他线程同时进行插入操作，可能会导致重新哈希过程中的数据不一致，进而引发死循环。

原因分析

扩容过程中，HashMap会创建一个新的、更大的桶数组，并将所有旧的键值对重新哈希并放入新的桶中。如果在这个过程中有其他线程插入新的键值对，可能会导致旧桶和新桶的数据结构不一致，进而引起死循环。

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.HashMap;
import java.util.Map;

public class HashMapResizeInfiniteLoop {
    public static void main(String[] args) {
        final Map<Integer, Integer> map = new HashMap<>(2);

        // 创建两个线程同时对 HashMap 进行插入操作
        Thread t1 = new Thread(() -> {
            for (int i = 0; i < 10000; i++) {
                map.put(i, i);
            }
        });

        Thread t2 = new Thread(() -> {
            for (int i = 10000; i < 20000; i++) {
                map.put(i, i);
            }
        });

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

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

        // 遍历 HashMap，可能会陷入死循环
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " : " + entry.getValue());
        }
    }
}

在上述代码中，HashMap初始容量设置为 2，两个线程同时插入大量元素，可能会导致扩容过程中数据不一致，从而引发死循环。

解决方案

使用线程安全的数据结构

在多线程环境中，使用ConcurrentHashMap代替HashMap。ConcurrentHashMap通过分段锁机制来保证线程安全，并发性能更好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.concurrent.ConcurrentHashMap;
import java.util.Map;

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

        Thread t1 = new Thread(() -> {
            for (int i = 0; i < 10000; i++) {
                map.put(i, i);
            }
        });

        Thread t2 = new Thread(() -> {
            for (int i = 10000; i < 20000; i++) {
                map.put(i, i);
            }
        });

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

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

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " : " + entry.getValue());
        }
    }
}

外部同步

如果必须使用HashMap，可以在外部进行同步，确保同时只有一个线程对HashMap进行修改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.HashMap;
import java.util.Map;

public class SynchronizedHashMapExample {
    public static void main(String[] args) {
        final Map<Integer, Integer> map = new HashMap<>();

        Thread t1 = new Thread(() -> {
            synchronized (map) {
                for (int i = 0; i < 10000; i++) {
                    map.put(i, i);
                }
            }
        });

        Thread t2 = new Thread(() -> {
            synchronized (map) {
                for (int i = 10000; i < 20000; i++) {
                    map.put(i, i);
                }
            }
        });

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

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

        synchronized (map) {
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                System.out.println(entry.getKey() + " : " + entry.getValue());
            }
        }
    }
}

通过使用ConcurrentHashMap或外部同步，可以避免HashMap在多线程环境中出现死循环的问题。

/dhuaw13mlcgfpa9k>

发表于 | 更新于 | 分类于
字数统计 | 阅读时长

👌为什么要使用扰动函数？

题目详细答案

扰动函数的目的是为了提高哈希码的质量，使其在哈希表中更均匀地分布。具体来说：

减少哈希冲突：通过将高位和低位混合，扰动函数减少了哈希码的模式性，降低了哈希冲突的概率。

均匀分布：扰动后的哈希码更加均匀地分布在哈希表的桶中，从而提高了哈希表的性能。

示例 Demo

假设我们有一个键对象，其hashCode()返回值为123456。我们可以通过哈希函数计算其哈希值：

  1. 调用hashCode()方法：
1
int h = 123456;
  1. 扰动函数计算：
1
int hash = h ^ (h >>> 16);
  1. 具体计算步骤：
    • h >>> 16 = 123456 >>> 16 = 1（右移 16 位）
    • hash = 123456 ^ 1 = 123457（异或运算）

最终，哈希值为123457。

/ntmpkg1lprz393fp>

发表于 | 更新于 | 分类于
字数统计 | 阅读时长

👌什么是HashTable?

题目详细答案

Hashtable 是遗留类，很多映射的常用功能与 HashMap 类似，不同的是它承自 Dictionary 类，并且是线程安全的，任一时间只有一个线程能写 Hashtable，并发性不如 ConcurrentHashMap，因为 ConcurrentHashMap 引入了分段锁。Hashtable 不建议在新代码中使用，不需要线程安全的场合可以用 HashMap 替换，需要线程安全的场合可以用 ConcurrentHashMap 替换。

与其他集合类的比较

Hashtable vs. HashMap：

Hashtable是线程安全的，而HashMap不是。

Hashtable不允许键或值为null，而HashMap允许一个null键和多个null值。

在现代 Java 编程中，HashMap更常用，因为它在大多数情况下性能更好，并且可以通过外部同步来实现线程安全。

Hashtable vs. ConcurrentHashMap：

ConcurrentHashMap是 Java 5 引入的一种改进的哈希表实现，专为高并发环境设计。

ConcurrentHashMap提供了更细粒度的锁机制，允许更高的并发性和更好的性能。

总的来说，Hashtable是一种较早的哈希表实现，适用于需要线程安全的简单场景。然而，在现代 Java 开发中，通常推荐使用ConcurrentHashMap或通过外部同步来使用HashMap，以获得更好的性能和灵活性。

/bgy4pz59q8ffzxwo>

发表于 | 更新于 | 分类于
字数统计 | 阅读时长

👌什么是LinkedHashMap?

题目详细答案

LinkedHashMap是 Java 集合框架中的一个类，它继承自HashMap，并且具有哈希表和链表的双重特性。LinkedHashMap通过维护一个双向链表来记录键值对的插入顺序或访问顺序，从而提供了一种有序的映射。

基本特点

  1. 有序性：LinkedHashMap保证了键值对的顺序，可以是插入顺序（默认）或访问顺序（可选）。
  2. 哈希表和链表结合：LinkedHashMap通过哈希表实现快速的键值对查找，同时通过双向链表维护顺序。
  3. 允许null键和值：LinkedHashMap允许一个null键和多个null值。
  4. 线程不安全：LinkedHashMap不是线程安全的，如果需要在多线程环境中使用，需要通过外部同步机制来保证线程安全。

与其他集合类的比较

LinkedHashMap vs. HashMap：

LinkedHashMap保证键值对的顺序（插入顺序或访问顺序），而HashMap不保证顺序。

LinkedHashMap通过维护链表来记录顺序，因此在插入和删除操作上可能略慢于HashMap。

LinkedHashMap vs. TreeMap：

LinkedHashMap保证插入顺序或访问顺序，而TreeMap保证键的自然顺序或比较器的顺序。

LinkedHashMap基于哈希表实现，操作的平均时间复杂度为 O(1)，而TreeMap基于红黑树实现，操作的时间复杂度为 O(log n)。

适用场景

LinkedHashMap适用于需要保持键值对的插入顺序或访问顺序的场景：

实现 LRU（最近最少使用）缓存。

需要按插入顺序遍历键值对。

需要在保持顺序的同时快速查找键值对。

/ttdsl1h3wbwte5u4>

发表于 | 更新于 | 分类于
字数统计 | 阅读时长

👌什么是TreeMap？

题目详细答案

基本特点

  1. 有序性：TreeMap保证了键的自然顺序（通过Comparable接口）或通过提供的比较器（Comparator）的顺序。
  2. 红黑树：TreeMap内部使用红黑树数据结构来存储键值对，保证了插入、删除、查找等操作的时间复杂度为 O(log n)。
  3. 不允许null键：TreeMap不允许键为null，但允许值为null。
  4. 线程不安全：TreeMap不是线程安全的，如果需要在多线程环境中使用，需要通过外部同步机制来保证线程安全。

与其他集合类的比较

TreeMap vs. HashMap：

TreeMap保证键的有序性，而HashMap不保证顺序。

TreeMap基于红黑树实现，操作的时间复杂度为 O(log n)，而HashMap基于哈希表实现，操作的平均时间复杂度为 O(1)。

TreeMap不允许null键，而HashMap允许一个null键。

TreeMap vs. LinkedHashMap：

TreeMap保证键的自然顺序或比较器的顺序，而LinkedHashMap保证插入顺序或访问顺序。

TreeMap的操作时间复杂度为 O(log n)，而LinkedHashMap的操作时间复杂度为 O(1)。

适用场景

TreeMap适用于需要按键排序存储键值对的场景，例如：

实现基于范围的查询。

需要按顺序遍历键值对。

需要快速查找最小或最大键值对。

/angmwmt1ka8unn4o>

发表于 | 更新于 | 分类于
字数统计 | 阅读时长

👌什么是fail-fast机制？

题目详细答案

在Java集合框架中，fail-fast是一种机制，用于检测在遍历集合时的结构性修改，并立即抛出异常以防止不一致状态。fail-fast迭代器在检测到集合在迭代过程中被修改后，会抛出ConcurrentModificationException异常。

工作原理

fail-fast迭代器通过在遍历集合时维护一个修改计数器（modification count）来工作。每当集合结构发生变化（如添加或删除元素）时，这个计数器就会增加。当创建迭代器时，它会保存当前的修改计数器值。在每次调用next()方法时，迭代器会检查当前的修改计数器值是否与保存的值一致。如果不一致，说明集合在迭代过程中被修改了，迭代器会立即抛出ConcurrentModificationException。

代码 Demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.*;

public class FailFastExample {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");

        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            String element = iterator.next();
            System.out.println(element);
            // 在迭代过程中修改集合
            if (element.equals("B")) {
                list.add("D"); // 这将引发 ConcurrentModificationException
            }
        }
    }
}

在上面的代码中，当迭代器遍历到元素 “B” 时，集合被修改（添加了新元素 “D”），因此迭代器将抛出ConcurrentModificationException。

注意事项

快速失败并不保证：fail-fast机制并不能保证在所有情况下都能检测到并发修改。它是尽力而为的检测机制，不能依赖于它来实现并发安全。如果需要并发安全的集合，可以使用java.util.concurrent包中的并发集合类。

避免并发修改：在遍历集合时，避免在外部修改集合。可以使用迭代器的remove方法来安全地移除元素。

使用remove方法

为了避免ConcurrentModificationException，可以使用迭代器的remove方法来移除元素：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;

public class SafeRemovalExample {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");

        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            String element = iterator.next();
            System.out.println(element);
            // 使用迭代器的 remove 方法安全地移除元素
            if (element.equals("B")) {
                iterator.remove();
            }
        }

        System.out.println("After removal: " + list);
    }
}

在这个示例中，使用iterator.remove()方法安全地移除了元素 “B”。

发表于 | 更新于 | 分类于
字数统计 | 阅读时长

👌什么是fail-safe机制？

题目详细答案

fail-safe机制是与fail-fast机制相对的一种并发处理机制。在 Java 集合框架中，fail-safe迭代器在检测到集合在遍历过程中被修改时，不会抛出异常，而是允许这种修改继续进行。fail-safe迭代器通常是通过在遍历时使用集合的副本来实现的，这样即使原集合被修改，迭代器也不会受到影响。

工作原理

fail-safe迭代器在遍历集合时，实际上是遍历集合的一个副本。因此，任何对原集合的修改都不会影响到迭代器正在遍历的副本。这种机制保证了遍历操作的安全性，但也意味着迭代器不能反映集合的实时变化。

代码 Demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.Iterator;
public class FailSafeExample {
    publicstaticvoidmain(String[] args) {
        CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");

        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            Stringelement= iterator.next();
            System.out.println(element);
            // 在迭代过程中修改集合
            if (element.equals("B")) {
                list.add("D"); // 不会引发 ConcurrentModificationException
            }
        }

        System.out.println("After modification: " + list);
    }
}

在上面的代码中，使用CopyOnWriteArrayList作为集合。CopyOnWriteArrayList是一个典型的fail-safe集合类，它在每次修改时都会创建集合的一个副本，因此迭代器不会检测到并发修改，不会抛出ConcurrentModificationException。

主要特点

  1. 不抛异常：fail-safe迭代器在检测到集合被修改时，不会抛出ConcurrentModificationException异常。
  2. 副本遍历：fail-safe迭代器遍历的是集合的一个副本，而不是原集合。这意味着对原集合的修改不会影响迭代器的遍历。
  3. 线程安全：fail-safe集合类（如CopyOnWriteArrayList、ConcurrentHashMap等）通常是线程安全的，适用于并发环境。

常见的fail-safe集合类

CopyOnWriteArrayList，ConcurrentHashMap，ConcurrentLinkedQueue，ConcurrentSkipListMap，ConcurrentSkipListSet

注意事项

  1. 性能开销：由于fail-safe机制通常需要创建集合的副本，因此在修改频繁的场景下，性能开销较大。适用于读多写少的场景。
  2. 一致性问题：由于迭代器遍历的是集合的副本，因此它不能反映集合的实时变化。如果需要实时一致性，fail-safe机制可能不适用。

发表于 | 更新于 | 分类于
字数统计 | 阅读时长

👌介绍一下HashMap？

题目详细答案

HashMap主要是用于存储键值对。它是基于哈希表实现的，提供了快速的插入、删除和查找操作。从安全角度，HashMap不是线程安全的。如果多个线程同时访问一个HashMap并且至少有一个线程修改了它，则必须手动同步。

HashMap允许一个 null 键和多个 null 值。

HashMap不保证映射的顺序，特别是它不保证顺序会随着时间的推移保持不变。

HashMap提供了 O(1) 时间复杂度的基本操作（如 get 和 put），前提是哈希函数的分布良好且冲突较少。

HashMap主要方法

**put(K key, V value)**：将指定的值与该映射中的指定键关联。如果映射以前包含一个该键的映射，则旧值将被替换。

**get(Object key)**：返回指定键所映射的值；如果此映射不包含该键的映射，则返回 null。

**remove(Object key)**：如果存在一个键的映射，则将其从映射中移除。

**containsKey(Object key)**：如果此映射包含指定键的映射，则返回 true。

**containsValue(Object value)**：如果此映射将一个或多个键映射到指定值，则返回 true。

**size()**：返回此映射中的键值映射关系的数量。

**isEmpty()**：如果此映射不包含键值映射关系，则返回 true。

**clear()**：从此映射中移除所有键值映射关系。

代码 Demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.HashMap;
import java.util.Map;

public class HashMapExample {
    public static void main(String[] args) {
        // 创建一个 HashMap 实例
        Map<String, Integer> map = new HashMap<>();

        // 添加键值对
        map.put("apple", 1);
        map.put("banana", 2);
        map.put("orange", 3);

        // 访问元素
        System.out.println("Value for key 'apple': " + map.get("apple"));

        // 检查是否包含某个键或值
        System.out.println("Contains key 'banana': " + map.containsKey("banana"));
        System.out.println("Contains value 3: " + map.containsValue(3));

        // 移除元素
        map.remove("orange");

        // 遍历 HashMap
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
        }

        // 获取大小
        System.out.println("Size of map: " + map.size());

        // 清空 HashMap
        map.clear();
        System.out.println("Is map empty: " + map.isEmpty());
    }
}

内部工作原理

HashMap使用哈希表来存储数据。哈希表是基于数组和链表的组合结构。

  1. 哈希函数：HashMap使用键的hashCode()方法来计算哈希值，然后将哈希值映射到数组的索引位置。
  2. 数组和链表：HashMap使用一个数组来存储链表或树结构（Java 8 及以后）。每个数组位置被称为一个“桶”，每个桶存储链表或树。
  3. 冲突处理：当两个键的哈希值相同时，它们会被存储在同一个桶中，形成一个链表（或树）。这种情况称为哈希冲突。
  4. 再哈希：当HashMap中的元素数量超过容量的负载因子（默认 0.75）时，HashMap会进行再哈希，将所有元素重新分配到一个更大的数组中。

注意事项

初始容量和负载因子：可以通过构造函数设置HashMap的初始容量和负载因子，以优化性能。初始容量越大，减少再哈希的次数；负载因子越小，减少冲突的概率，但会增加空间开销。

哈希函数的质量：哈希函数的质量直接影响HashMap的性能。理想的哈希函数应尽可能均匀地分布键。

线程安全性

如前所述，HashMap不是线程安全的。如果需要线程安全的映射，可以使用Collections.synchronizedMap来包装HashMap，或者使用ConcurrentHashMap，后者在高并发环境下性能更好。

1
Map<String, Integer> synchronizedMap = Collections.synchronizedMap(newHashMap<>());

或者使用ConcurrentHashMap：

1
Map<String, Integer> concurrentMap = newConcurrentHashMap<>();

/iwe6pgyi65omsy8l>

发表于 | 更新于 | 分类于
字数统计 | 阅读时长

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

ArrayList 是最常用的 List 实现类，线程不安全，内部是通过数组实现的，继承了AbstractList，实现了List。它允许对元素进行快速随机访问。数组的缺点是每个元素之间不能有间隔，当数组大小不满足时需要增加存储能力，就要将已经有数组的数据复制到新的存储空间中。当从 ArrayList 的中间位置插入或者删除元素时，需要对数组进行复制、移动、代价比较高。因此，它适合随机查找和遍历，不适合插入和删除。排列有序，可重复，容量不够的时候，新容量的计算公式为：

newCapacity = oldCapacity + (oldCapacity >> 1)，这实际上是将原容量增加50%（即乘以1.5）。

ArrayList实现了RandomAccess接口，即提供了随机访问功能。RandomAccess是java中用来被List实现，为List提供快速访问功能的。在ArrayList中，我们即可以通过元素的序号快速获取元素对象，这就是快速随机访问。

ArrayList实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。

LinkedList（链表）

LinkedList 是用链表结构存储数据的，线程不安全。很适合数据的动态插入和删除，随机访问和遍历速度比较慢，增删快。另外，他还提供了 List 接口中没有定义的方法，专门用于操作表头和表尾元素，可以当作堆栈、队列和双向队列使用。底层使用双向链表数据结构。

LinkedList是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。

Vector（数组实现、线程同步）

Vector 与 ArrayList 一样，也是通过数组实现的，Vector和ArrayList用法上几乎相同，但Vector比较古老，一般不用。Vector是线程同步的，效率低。即某一时刻只有一个线程能够写 Vector，避免多线程同时写而引起的不一致性，但实现同步需要很高的花费，因此，访问它比访问 ArrayList 慢。默认扩展一倍容量。

/op8ey0ndh6st3bgz>

发表于 | 更新于 | 分类于
字数统计 | 阅读时长

👌如何确保函数不能修改集合？

题目详细答案

使用Collections.unmodifiableCollection方法

Java提供了Collections.unmodifiableCollection方法，可以将一个集合包装成一个不可修改的视图。对这个视图的修改操作将会抛出UnsupportedOperationException。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.*;

public class UnmodifiableCollectionExample {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));
        Collection<String> unmodifiableList = Collections.unmodifiableCollection(list);

        // 传递不可修改的集合给函数
        printCollection(unmodifiableList);

        // 尝试修改集合将抛出 UnsupportedOperationException
        // unmodifiableList.add("D"); // 这行代码会抛出异常
    }

    public static void printCollection(Collection<String> collection) {
        for (String item : collection) {
            System.out.println(item);
        }
    }
}

使用Collections.unmodifiable

对于特定类型的集合，如List、Set和Map，Java 提供了相应的不可修改视图方法：

Collections.unmodifiableList

Collections.unmodifiableSet

Collections.unmodifiableMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.*;

public class UnmodifiableSpecificCollectionsExample {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));
        List<String> unmodifiableList = Collections.unmodifiableList(list);

        Set<String> set = new HashSet<>(Arrays.asList("X", "Y", "Z"));
        Set<String> unmodifiableSet = Collections.unmodifiableSet(set);

        Map<String, Integer> map = new HashMap<>();
        map.put("One", 1);
        map.put("Two", 2);
        Map<String, Integer> unmodifiableMap = Collections.unmodifiableMap(map);

        // 传递不可修改的集合给函数
        printList(unmodifiableList);
        printSet(unmodifiableSet);
        printMap(unmodifiableMap);

        // 尝试修改集合将抛出 UnsupportedOperationException
        // unmodifiableList.add("D"); // 这行代码会抛出异常
        // unmodifiableSet.add("W"); // 这行代码会抛出异常
        // unmodifiableMap.put("Three", 3); // 这行代码会抛出异常
    }

    public static void printList(List<String> list) {
        for (String item : list) {
            System.out.println(item);
        }
    }

    public static void printSet(Set<String> set) {
        for (String item : set) {
            System.out.println(item);
        }
    }

    public static void printMap(Map<String, Integer> map) {
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

使用Collections.unmodifiableCollection递归包装嵌套集合

如果集合中包含嵌套集合（例如一个List中包含Set），你需要递归地将所有嵌套集合也包装成不可修改的视图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.*;

public class UnmodifiableNestedCollectionsExample {
    public static void main(String[] args) {
        List<Set<String>> listOfSets = new ArrayList<>();
        listOfSets.add(new HashSet<>(Arrays.asList("A", "B", "C")));
        listOfSets.add(new HashSet<>(Arrays.asList("X", "Y", "Z")));

        List<Set<String>> unmodifiableListOfSets = new ArrayList<>();
        for (Set<String> set : listOfSets) {
            unmodifiableListOfSets.add(Collections.unmodifiableSet(set));
        }
        Collection<List<Set<String>>> unmodifiableCollection = Collections.unmodifiableCollection(Collections.singletonList(unmodifiableListOfSets));

        // 传递不可修改的集合给函数
        printNestedCollection(unmodifiableCollection);

        // 尝试修改集合将抛出 UnsupportedOperationException
        // unmodifiableListOfSets.get(0).add("D"); // 这行代码会抛出异常
    }

    public static void printNestedCollection(Collection<List<Set<String>>> collection) {
        for (List<Set<String>> list : collection) {
            for (Set<String> set : list) {
                for (String item : set) {
                    System.out.println(item);
                }
            }
        }
    }
}

通过以上可以确保传递给函数的集合不会被修改，从而保证集合的不可变性。

发表于 | 更新于 | 分类于
字数统计 | 阅读时长

👌如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？

题目详细答案

当HashMap的大小超过了负载因子（load factor）定义的容量时，HashMap会进行扩容（resize）。

扩容的具体步骤

假设当前HashMap的容量是N，负载因子是L，当插入的键值对数量超过N * L时，HashMap会进行扩容。具体步骤如下：

  1. 计算新的容量： 新的容量通常是当前容量的两倍。假设当前容量是N，新的容量是2 * N。
  2. 创建新的桶数组： 根据新的容量创建一个新的桶数组。
  3. 重新哈希所有的键值对： 对旧桶数组中的所有键值对重新计算哈希值，并将它们放入新的桶数组中。这一步是必要的，因为哈希值是基于数组长度计算的，数组长度改变后，哈希值也需要重新计算。

代码 Demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.HashMap;
import java.util.Map;

public class HashMapResizeExample {
    public static void main(String[] args) {
        // 创建一个初始容量为4，负载因子为0.75的HashMap
        Map<Integer, String> map = new HashMap<>(4, 0.75f);

        // 插入一些键值对
        map.put(1, "one");
        map.put(2, "two");
        map.put(3, "three");
        // 触发扩容
        map.put(4, "four");

        // 打印扩容后的HashMap
        System.out.println(map);
    }
}

在上述代码中，当插入第四个键值对时，HashMap的大小超过了4 * 0.75 = 3，因此会触发扩容，容量从 4 增加到 8。

扩容的具体实现

在 Java 的HashMap实现中，扩容的具体代码在resize方法中。以下是resize方法的简化版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void resize() {
    // 计算新的容量
    int newCapacity = oldCapacity * 2;

    // 创建新的桶数组
    Node<K,V>[] newTable = (Node<K,V>[])new Node[newCapacity];

    // 重新哈希所有的键值对
    for (Node<K,V> node : oldTable) {
        while (node != null) {
            Node<K,V> next = node.next;
            int hash = node.hash % newCapacity;
            node.next = newTable[hash];
            newTable[hash] = node;
            node = next;
        }
    }

    // 替换旧的桶数组
    table = newTable;
}

注意事项

性能影响：扩容是一个相对昂贵的操作，因为它需要重新哈希并移动所有现有的键值对。因此，在设计HashMap时，应尽量选择合适的初始容量和负载因子，以减少扩容次数。

线程安全：默认的HashMap是非线程安全的。如果在多线程环境中使用HashMap，需要使用Collections.synchronizedMap或使用ConcurrentHashMap。

内存消耗：扩容会临时占用更多的内存，因为需要同时维护旧的和新的桶数组。因此，在内存受限的环境中需要谨慎使用。

发表于 | 更新于 | 分类于
字数统计 | 阅读时长

👌拉链法导致的链表过深问题为什么用红黑树？

题目详细答案

在JDK 8中，HashMap采用红黑树来解决拉链法导致的链表过深问题，主要是为了提高在高冲突情况下的性能。

拉链法中的链表过深问题

在传统的拉链法中，当多个键的哈希值冲突时，这些键会被存储在同一个桶（bucket）中，形成一个链表。如果链表过长，查找、插入和删除操作的时间复杂度会退化为O(n)，其中n是链表中的元素个数。这种情况下，HashMap的性能会显著下降。

红黑树的优势

红黑树是一种自平衡的二叉搜索树，具有以下特性：

  1. 自平衡：红黑树通过颜色属性（红色和黑色）和一系列的旋转操作，保证树的高度近似平衡。其高度不会超过2 * log(n)，其中n是树中的节点数。
  2. 高效的查找、插入和删除：红黑树的查找、插入和删除操作的时间复杂度为O(log n)，远优于链表在最坏情况下的O(n)。

为什么选择红黑树

  1. 性能优化：在链表长度较短时，链表操作的性能是可以接受的。然而，当链表长度超过一定阈值（JDK 8中为8）时，链表操作的性能会显著下降。此时，将链表转换为红黑树，可以将操作的时间复杂度从O(n)降低到O(log n)，显著提高性能。
  2. 平衡性：红黑树通过自平衡机制，保证树的高度始终保持在一个较低的水平，避免了链表过长导致的性能问题。
  3. 空间效率：虽然红黑树比链表占用更多的空间（因为需要存储颜色和指针信息），但在链表长度较长时，性能的提升通常会超过空间开销的增加。

实现细节

在JDK 8的HashMap中，当链表长度超过阈值（8）时，会将链表转换为红黑树。

1
2
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    treeifyBin(tab, hash);

treeifyBin方法将链表转换为红黑树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}