HashMap源码解析（一）（佬你不来看看？😘）
🎊专栏【Java】
🍔喜欢的诗句：关山难越，谁悲失路之人。 萍水相逢，尽是他乡之客。
🎆音乐分享【Counting Stars 】
欢迎并且感谢大家指出问题🥰
1.先来了解一下HashMap
HashMap是Java集合框架中的一种数据结构，它实现了Map接口。HashMap通过键值对的方式存储和管理数据。HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK（Java DevelopmetKit）版本的更新， jdk8 针对 HashMap 的 hash碰撞 以及 查询效率 问题进行了优化，例如：引入红黑树的数据结构和扩容的优化等。那我们一起来了解它 come on baby 。
1.1HashMap常用方法以及特点
在HashMap中，每个键(key)都是唯一的，它们对应着一个值(value)。当你插入一个键值对时，HashMap会根据键的哈希值来确定存储位置，并将键值对存储在该位置上。这样，当你想要获取某个键对应的值时，HashMap会通过哈希值快速定位到相应的存储位置，从而提高访问效率。
以下是HashMap的一些特点和常用方法：
- 特点：
- 允许存储null键和null值。
- 键值对无序存储，不保证插入顺序。
- 使用哈希表实现，提供快速的查找、插入和删除操作。
- 初始容量和负载因子可调，可以根据实际需求进行优化。
- 常用方法：
- put(K key, V value)：插入键值对到HashMap中。
- get(Object key)：根据键获取对应的值。
- remove(Object key)：根据键删除对应的键值对。
- containsKey(Object key)：判断HashMap是否包含指定的键。
- containsValue(Object value)：判断HashMap是否包含指定的值。
- size()：返回HashMap中键值对的数量。
- clear()：清空HashMap中的所有键值对。
需要注意的是，HashMap不是线程安全的，如果在多线程环境下使用HashMap，需要进行适当的同步操作或考虑使用线程安全的Map实现类，如ConcurrentHashMap。
HashMap在Java编程中广泛应用，它提供了高效的存储和查找机制，适用于需要快速访问和更新数据的场景。
2.数据结构部分
由上面结构图可知，为了解决当hash碰撞过于频繁，而链表的查询效率(时间复杂度为O(n))过低
时，当 链表 的长度达到一定值(默认是8)时，将链表转换成 红黑树 (时间复杂度为O(lg n))，极大的提高了查询效率。
static class Node<K,V> implements Map.Entry<K,V> { // hash值 final int hash; // 键 final K key; // 值 V value; // 链表下一个节点 Node<K,V> next; // 构造方法 Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } // 获取键 public final K getKey() { return key; } // 获取值 public final V getValue() { return value; } // 重写toString方法 public final String toString() { return key + "=" + value; } // 计算hashCode值 public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } // 重新设置当前的值 public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } // 比较两个entry public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }
可以看到，这个Node<K,V>[]是HashMap的一个内部类，他既是HashMap底层数组的组成元素，又是每个单向链表的组成元素。它其中包含了数组元素所需要的key与value，以及链表所需要的指向下一个节点的引用域next。
3.源码分析
3.1成员属性
3.2接下来是和红黑树相关的（在jdk1.8中，如果链表过长就会转变成一个红黑树）
我们主要来看看loadFactor属性，loadFactor表示Hash表中元素的填满程度。
/**
- 默认初始大小:
- 默认初始大小:16。
- 大小必须为2的指数。
- 这里的16,采用的1左移4位实现
/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/*
- 最大容量:
- 构造函数的参数隐式指明时使用该值
- 必须是2的指数,且小于等于1<<30（即2的30次方）
/
static final int MAXIMUM_CAPACITY = 1 << 30;
/*
- 负载因子： 默认值为0.75f
- 0.75 是对时间和空间效率的一个平衡选择，建议大家不要修改。
- 除非在时间或者空间上比较特殊的情况下。
- 例如：
- 如果内存空间很多而又对时间效率要求很高，可以降低负载因子
- 如果内存空间较少而又对时间效率要求不高，可以增加负载因子
- 注意：这个值可以大于1
/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
— 接下来是和红黑树相关的几个常量。在jdk1.8中，如果哈希表中的链表太长，就会转化为一个红黑树。-
–
/* - 使用树而不使用链表的阈值：
- 表示要转为红黑树的最小元素个数, 即8 。
/
static final int TREEIFY_THRESHOLD = 8;
/* - 使用链表而不使用树的阈值：
- 红黑树转化为链表的门限个数是 6。
/
static final int UNTREEIFY_THRESHOLD = 6;
/* - 可被树化的最小表容量：64
- 需要满足哈希桶的数量要达到 64。
- 需要是TREEIFY_THRESHOLD数量的4倍以上。
*/
static final int MIN_TREEIFY_CAPACITY = 64;
若加载因子设置过大，则填满的元素越多，无疑空间利用率变高了，但是冲突的机会增加了，冲突
的越多，链表就会变得越长，那么查找效率就会变得更低；
若加载因子设置过小，则填满的元素越少，那么空间利用率变低了，表中数据将变得更加稀疏，但
是冲突的机会减小了，这样链表就不会太长，查找效率变得更高。
举例说明
如果数组容量为100，加载因子设置为80，即装满了80个才开始扩容，但是在装的过程中，可能有
很多key对应相同的hash值，这样就会放到同一个链表中（因为没到80个不能扩容），这样就会导
致很多链表都变得很长，也就是说，不同的key对应相同的hash值比数组填满到80个更加容易出
现。
但是如果设置加载因子为10，那么数组填满10个就开始扩容了，10个相对来说是很容易填满的，而
且在10个内出现相同的hash值概率比上面的情况要小的多，一旦扩容之后，那么计算hash值又会
跟原来不一样，就不会再冲突了，这样保证了链表不会很长，甚至就一个表头都有可能，但是空间
利用率很低，因为始终有很多空间没利用就开始扩容。
因此，就需要在“减小冲突”和“空间利用率”之间寻找一种平衡，这种平衡就是数据结构中有名的“时-空”
矛盾的平衡。如果机器内存足够，并且想要提高查询速度的话可以将加载因子设置小一点；相反如果机
器内存紧张，并且对查询速度没什么要求的话可以将加载因子设置大一点。一般我们都使用它的默认
值，即0.75。
3.4构造方法
第一个构造函数中，指定了初始容量和加载因子，需要扩容的容量threshold 值由tableSizeFor方法得出：
我们可以看到，在构造 HashMap 的时候，如果我们指定了加载因子和初始容量的话就调用第一个构造
方法，否则就用默认的。默认的初始容量为 16 ， 加载因子为 0.75 。
