【HashMap源码解析（一）（佬你不来看看？）】-阿里云开发者社区

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 。

【HashMap源码解析（一）（佬你不来看看？）】