HashMap

底层原理见：Java集合进阶

1. HashMap简介

HashMap存储数据采用了哈希表的结构，底层使用一维数组+单向链表+红黑树进行key-value对的存储。
红黑树出现的时机：当某个索引位置i上的链表长度达到8，且数组长度超过64时，此索引位置上的元素要从单向链表改为红黑树。原因：红黑树进行put()/get()/remove()操作的时间复杂度为O(logn)，比单向链表的时间复杂度O(n)好。
红黑树退化成单向链表：如果索引i位置是红黑树，当不断删除元素的情况下，i处元素个数低于6时，红黑树会退化成单向链表。

HashMap结构

触发条件： 当HashMap中存储的键值对数量超过一个阈值时，就会触发扩容。这个阈值通常是当前容量 * 加载因子（loadFactor，默认0.75）
扩容过程：
- 创建新数组： 创建一个新的、更大的数组，通常是当前数组容量的两倍。
- 重新计算哈希与迁移（Rehashing）： 遍历旧数组中的每一个键值对，重新计算它们在新数组中的位置（因为数组长度变了，哈希映射的索引也会变），然后将它们放入新数组的对应位置。这个过程很重要，因为同一个元素在新旧数组中的桶（bucket）索引很可能不同。
目的：
- 减少哈希冲突： 通过扩大数组容量，使得键值对能更均匀地分布，从而减少哈希冲突，保持HashMap的查找、插入等操作的效率（接近O(1)）。
- 保持性能： 如果不扩容，当元素越来越多时，链表（或红黑树）会越来越长，性能会下降。

实现原理：
- HashMap基于hash表实现，计算键的hash值来确定存储位置。默认情况下，hashmap不保证元素的存储顺序，从java8之后，h链表过长会转化为红黑树。
- TreeMap基于红黑树实现，是一种自平衡二叉查找树，能够保持键的有序性，因此，TreeMap中的元素总是按照键的自然顺序或者创建时提供的Comparator进行排序。
性能特点：
- HashMap的插入、删除和查找操作的平均时间复杂度为O(1)，但在最坏情况下（例如大量哈希冲突）可能退化为O(n)。
- TreeMap的插入、删除和查找操作的时间复杂度为O(log n)，因为它需要维护红黑树的平衡性。

存储内容不同：
- HashSet存储的是不重复的单个元素。它主要用来快速检查某个元素是否存在于集合中。
- HashMap存储的是键值对（key-value pairs）。它用于根据键快速查找对应的值。
内部实现关系：
- HashSet实际上是基于HashMap实现的。每当你向HashSet添加一个元素时，实际上是将该元素作为HashMap的键存储，而值则是一个固定的常量对象（通常是一个私有的静态常量）。

线程安全性：
- HashMap是非线程安全的，多个线程同时访问时可能会导致数据不一致。如果需要在多线程环境下使用，可以通过Collections.synchronizedMap()方法将其包装为线程安全的版本，或者使用ConcurrentHashMap。
- Hashtable是线程安全的，所有的方法都使用synchronized关键字进行同步，确保在多线程环境下的安全性。但这种同步机制会带来性能开销。
null键和null值：
- HashMap允许一个null键和多个null值。
- Hashtable不允许null键或null值，尝试插入null会抛出NullPointerException。
性能：
- HashMap由于非线程安全，在单线程环境下通常比Hashtable性能更好。
- Hashtable由于同步机制，在多线程环境下性能较差。在需要线程安全的场景下，更推荐使用ConcurrentHashMap。
父类：
- HashMap继承自AbstractMap，实现了Map接口。
- Hashtable继承自Dictionary，也是实现了Map接口，但Dictionary是一个较早的类，已经被遗弃。
总结：
- Hashtable是一个遗留的线程安全类，性能较差。如果需要线程安全，推荐使用ConcurrentHashMap。如果不需要线程安全，使用HashMap。

JDK1.7之前： 哈希冲突时采用拉链法（链表存储），在链表过长时查询效率退化为O(n)。
JDK1.8及以后： 当单个桶内的链表长度超过阈值（默认8），并且当前HashMap的容量大于64时，链表会转换为红黑树，从而将查询效率提升到O(log n)。
- 当元素减少到6以下时，红黑树会退化回链表。
- 红黑树的引入显著提升了在高冲突情况下的性能。