[TOC]



### `HashMap` 的设计理念

`HashMap` 是 Java 集合框架中非常重要的一个类，它的设计旨在提供高效的键值对存储和检索机制。以下是 `HashMap` 的设计理念及其关键特性：

#### 1. **高效的键值对存储和检索**
- **哈希表**：`HashMap` 基于哈希表实现，通过哈希函数将键转换为数组索引，从而实现快速的存储和检索。哈希表的核心思想是将键值对存储在一个数组中，通过哈希函数计算键的哈希码，再将哈希码转换为数组索引。
- **平均时间复杂度 O(1)**：在理想情况下，`HashMap` 的 `get` 和 `put` 操作的时间复杂度为 O(1)，因为哈希函数可以快速计算出键的索引位置。

#### 2. **解决哈希冲突**
- **链地址法**：当多个键的哈希码相同或哈希码不同但索引位置相同（即哈希冲突）时，`HashMap` 使用链地址法来解决冲突。具体来说，每个数组槽位（bucket）实际上是一个链表（或红黑树），所有哈希码相同的键值对都会被链接到同一个链表中。
- **红黑树优化**：当链表的长度超过一定阈值（默认为8）时，链表会转换为红黑树，以提高查找效率。红黑树是一种自平衡二叉搜索树，能够在 O(log n) 时间内完成查找、插入和删除操作。

#### 3. **动态扩容**
- **负载因子**：`HashMap` 有一个负载因子（默认为0.75），用于控制数组的扩容。当实际存储的元素数量达到数组容量与负载因子的乘积时，`HashMap` 会自动扩容，通常是原容量的两倍。扩容操作涉及重新计算所有键的哈希码并将它们重新分配到新的数组中。
- **扩容策略**：扩容操作虽然会带来一定的性能开销，但它确保了 `HashMap` 在大多数情况下都能保持高效的性能。

#### 4. **允许 `null` 键和 `null` 值**
- **`null` 键**：`HashMap` 允许一个 `null` 键，这意味着你可以将 `null` 作为键存储在 `HashMap` 中。`HashMap` 特别处理了 `null` 键的情况，将其存储在数组的第一个槽位（索引为0）。
- **`null` 值**：`HashMap` 允许多个 `null` 值，这意味着你可以将 `null` 作为值存储在 `HashMap` 中。

#### 5. **非线程安全**
- **单线程环境**：`HashMap` 是为单线程环境设计的，不支持多线程并发访问。在多线程环境下，`HashMap` 可能会出现数据不一致、死循环等问题。
- **线程安全的替代方案**：如果需要在多线程环境中使用，可以使用 `ConcurrentHashMap` 或者使用 `Collections.synchronizedMap` 方法包装 `HashMap`。

#### 6. **迭代器**
- **迭代顺序**：`HashMap` 不保证键值对的迭代顺序，特别是当进行插入、删除或扩容操作时，迭代顺序可能会改变。
- **快速失败**：`HashMap` 的迭代器实现了快速失败机制，如果在迭代过程中检测到集合被修改（除了迭代器自身的 `remove` 方法），会抛出 `ConcurrentModificationException` 异常。

#### 7. **内部类 `Entry`**
- **键值对封装**：`HashMap` 内部使用 `Entry` 类来封装键值对，每个 `Entry` 对象包含键、值、下一个 `Entry`（用于链地址法）和哈希码。
- **链表节点**：`Entry` 对象通过 `next` 字段链接成链表，形成链地址法所需的链表结构。

 [参考Gitee](https://gitee.com/MyCoder4j/wechat)
### 总结
`HashMap` 的设计理念是为了提供高效的键值对存储和检索机制，通过哈希表、链地址法和红黑树优化解决了哈希冲突问题，并通过动态扩容保持了高效的性能。尽管 `HashMap` 不支持多线程并发访问，但在单线程环境中表现非常出色。对于多线程环境，可以使用 `ConcurrentHashMap` 或其他线程安全的集合类。
### Java `HashMap` 详解

#### 概述
`HashMap` 是 Java 集合框架的一部分，它基于哈希表实现。`HashMap` 存储键值对（key-value pairs），并允许通过键快速检索值。`HashMap` 不保证映射的顺序，特别是在迭代过程中。此外，`HashMap` 允许一个 null 键和多个 null 值。

#### 内部结构
- **数组 + 链表/红黑树**：`HashMap` 内部维护了一个 `Entry<K,V>[] table` 数组，每个 `Entry` 实际上是一个单向链表的节点或者红黑树的节点。当哈希冲突发生时（即两个不同的键具有相同的哈希码），`HashMap` 使用链地址法解决冲突，即将具有相同索引的元素链接成一个链表。如果链表长度超过一定阈值（默认为8），则该链表会转换为红黑树，以提高查找效率。
- **负载因子**：`HashMap` 有一个负载因子（默认为0.75），用于控制数组的扩容。当实际存储的元素数量达到数组容量与负载因子的乘积时，`HashMap` 会自动扩容，通常是原容量的两倍。

#### 方法
- `put(K key, V value)`：将指定的键值对存入 `HashMap`。
- `get(Object key)`：返回指定键所映射的值；如果此映射不包含该键的映射关系，则返回 `null`。
- `remove(Object key)`：移除此映射中指定键的映射关系（如果存在）。
- `containsKey(Object key)`：如果此映射包含指定键的映射关系，则返回 `true`。
- `containsValue(Object value)`：如果此映射将一个或多个键映射到指定值，则返回 `true`。
- `size()`：返回此映射中的键值对的数量。
- `isEmpty()`：如果此映射不包含键值对映射关系，则返回 `true`。

### 性能分析
- **时间复杂度**：
  - 平均情况下，`get` 和 `put` 操作的时间复杂度为 O(1)。
  - 在最坏的情况下（所有键都映射到同一个桶中），时间复杂度退化为 O(n)，其中 n 是桶中的元素数。
- **空间复杂度**：`HashMap` 的空间复杂度取决于其容量和负载因子。初始容量通常较小，但随着元素的增加，`HashMap` 会动态扩容，这会导致额外的空间开销。

### 线程不安全的原因
`HashMap` 在多线程环境下是不安全的，主要原因包括：
- **扩容问题**：当多个线程同时触发 `HashMap` 扩容时，可能会导致死循环。这是因为扩容操作涉及到重新计算哈希值并将元素重新分配到新的数组中，这个过程如果没有正确的同步机制，可能导致数据结构损坏。
- **数据一致性**：在多线程环境中，一个线程可能正在修改 `HashMap`，而另一个线程试图读取它，这可能导致数据不一致的问题。
- **竞态条件**：在没有适当的同步措施下，两个线程可能同时尝试添加同一个键，导致不明确的结果。

### 手写一个简单的 `HashMap`
下面是一个简化版的 `HashMap` 实现，仅用于教学目的。请注意，这个实现并不考虑线程安全性和所有边界条件，因此不适合在生产环境中使用。

```java
import java.util.*;

public class SimpleHashMap<K, V> {
    private static final int DEFAULT_CAPACITY = 16;
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    private Entry<K, V>[] table;
    private int size;
    private int threshold;
    private float loadFactor;

    public SimpleHashMap() {
        this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    public SimpleHashMap(int capacity, float loadFactor) {
        if (capacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " + capacity);
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);

        this.loadFactor = loadFactor;
        this.threshold = (int) (capacity * loadFactor);
        this.table = new Entry[capacity];
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public V get(Object key) {
        int hash = hash(key);
        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 != null && key.equals(k))))
                return e.value;
        }
        return null;
    }

    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        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;
    }

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

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

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

    private V putForNullKey(V value) {
        for (Entry<K, V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }

    private void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == Integer.MAX_VALUE) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable);
        table = newTable;
        threshold = (int) (newCapacity * loadFactor);
    }

    private void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K, V> e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    Entry<K, V> next = e.next;
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }

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

    private static int indexFor(int h, int length) {
        return h & (length - 1);
    }

    private 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 K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public 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();
        }

        void recordAccess(SimpleHashMap<K, V> m) {}
    }
}
```

这个实现包含了基本的 `put` 和 `get` 方法，并且能够处理 `null` 键的情况。它也实现了简单的扩容逻辑。但是，这个实现并没有考虑线程安全性，也没有实现所有的 `Map` 接口方法。在实际应用中，应该使用 JDK 提供的标准 `HashMap` 类。