hashmap底层原理

HashMap 是 Java 中最常用的集合之一，它基于哈希表实现，可以提供快速的键值对查找和插入。下面是 HashMap 的底层原理：

1. 数据结构：HashMap 内部使用一个数组来保存元素，每一个元素都是一个键值对对象 Entry<K,V>，其中 K 和 V 分别表示键和值。每一个 Entry 对象包含一个 hash 值、一个键对象和一个值对象以及一个指向下一个 Entry 对象的指针。

2. 哈希函数：HashMap 使用的是 JDK 提供的默认哈希函数，即 key.hashCode()，它将 key 转换为一个整数，这个整数就是该 key 的哈希值。

3. 哈希冲突：由于哈希函数的不完美性，不同的 key 可能会产生相同的哈希值，这就是哈希冲突。当两个不同的 key 产生相同的哈希值时，HashMap 会在同一个桶中保存它们，这个桶中保存的是一个链表，每一个链表节点就是一个 Entry 对象，它包含了一个键值对和一个指向下一个 Entry 对象的指针。

4. 扩容：当 HashMap 中元素的数量超过了负载因子（默认为 0.75）乘以数组大小时，就需要对数组进行扩容。扩容操作会重新计算每个元素的哈希值，并将它们放到新的桶中。同时，为了减少哈希冲突，新数组的大小会是原数组大小的两倍，并且新数组中的每个桶都会是一个链表头节点。

5. 并发问题：HashMap 是非线程安全的，如果多个线程同时修改 HashMap，可能会导致链表出现环形结构，从而导致死循环。为了解决这个问题，Java 提供了一个线程安全的 ConcurrentHashMap 类，它使用了分段锁来保证线程安全。