一、HashMap数据存储结构
HashMap底层就是一个哈希表，即一个数组加链表结构，在java8中如果链表长度达到8则转化为红黑树结构，具体操作过程后面会讲到，先看看最终存储元素后HashMap的结构，Entry为HashMap内部维护的一个静态内部类，在java8改名为Node
数据存储方式
下面先来看看静态内部类Node，它其实就是一个单向链表的节点类，hash存储key对应的hash值，key和value即存储保存在HashMap中的key-value键值对，next是一个指向下一Node节点的引用
static class Node<K,V> implements Map.Entry<K,V> {
//key对应的hash值
final int hash;
//用户存储的key
final K key;
//用户存储的value
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;
}
//getter&toString方法
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
//hashCode方法
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
//setter方法
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
//equals方法
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;
}
}
二、HashMap源码中几个重要属性
1、首先看几个静态常量
//默认初始容量，必须是2的幂，如果使用默认构造方法，则Node数组的默认长度则为该值
//至于长度为什么必须是2的幂，后面讲put方法时会讲到
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//Node数组的最大容量，如果使用有参构造且指定容量大于该值，则使用该值，扩容时当容量
//达到该值时不在扩容，因为int最大值为1<<31-1，非2的幂，所以最大值只能设置到1<<30
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认加载因子，HashMap实际存储元素个数为Node数组容量*加载因子，当数组容量达到上面
//的最大值时，实际容量理论上为无限大
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//链表转换红黑树的阀值，当hash冲突导致链表长度达到此值时转换为红黑树，此为java8的优化
static final int TREEIFY_THRESHOLD = 8;
//红黑树转链表的阀值，在HashMap扩容时，如果红黑树长度小于等于此值时，红黑树拆分为链表
static final int UNTREEIFY_THRESHOLD = 6;
//此处需注意，java8之前是当Node节点数超过HashMap实际容量(即数组容量*加载因子)时扩容，
//而在java8中，当数组容量还没达到下面这个值时，只要链表长度达到树化阀值也就是8即扩容
static final int MIN_TREEIFY_CAPACITY = 64;
2、HashMap中的属性值
//定义Node数组
transient Node<K,V>[] table;
//定义Node节点的Set集合(从上面看的到Node实现了Map.Entry<K,V>接口)，遍历的时候用的多
transient Set<Map.Entry<K,V>> entrySet;
//定义HashMap中Node节点的数量，也即key-value键值对数量
transient int size;
//定义HashMap结构变化的次数，put，remove等方法就会改变此值
transient int modCount;
//定义HashMap的实际容量(Node数组*加载因子)
int threshold;
//定义加载因子
final float loadFactor;
三、HashMap的几个构造函数
HashMap一共四个构造函数，下面分别讲一下：
1、默认构造方法
//默认构造方法就是把加载因子赋值为默认值，即0.75
//但后面会看到，虽然没有显示初始化Node数组容量，但默认容量为16
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
2、单参数构造方法
//此构造方法会指定初始化Node数组容量，加载因子还是默认值0.75，然后调用自己的双参构造
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
3、双参数构造方法
//此构造方法接收两个参数，初始数组容量和加载因子
public HashMap(int initialCapacity, float loadFactor) {
//初始容量小于0，报错
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//初始容量大于给定的最大值，则直接赋予给定的最大值
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//加载因子小于等于0或者为非数字，报错
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
//将加载因子赋给定义的属性
this.loadFactor = loadFactor;
//给定义的实际容量赋值，这里有个疑问，实际容量不是等于initialCapacity*loadFactor吗？
//首先tableSizeFor()方法是求大于等于给定值的最小2的幂，此方法等下讲，超级高明的实现
//然后因为所有构造方法都没有初始化上面的table，所以第一次put就会调用resize方法，然后
//重新初始化threshold ，此时threshold就符合数组容量*加载因子的规则了
//具体put及resize方法请参看我的相关文章
this.threshold = tableSizeFor(initialCapacity);
}
HashMap源码之put方法
HashMap源码之resize方法
下面看看tableSizeFor()方法:
//此方法返回大于等于给定值的最小2的幂，例如:tableSizeFor(10)=16，tableSizeFor(20)=32
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
下面以10为例讲一下这个方法：
首先int n = 10 - 1，则n=9，下面看看9的二进制数
1001 -------9
0100 -------无符号右移一位后
1101 -------上面两个值|(或)运算后
0011 -------上面的值再无符号右移两位
1111 -------上面两个值|(或)运算后
后面的几步右移4，8，16后的值都是0000，或运算后都为1111
所以最后n的二进制数为1111，即为15，最后小于默认最大值，所以n+1之后等于16，即2的4次幂
此方法就是把给定值的二进制数最高位右边的所有位数变为1，然后加1，则必为2的幂
例如有一个数：11010001000110001011101110 对应十进制：54813422
经过tableSizeFor()几波右移或运算后得到：11111111111111111111111111，然后+1
得到：100000000000000000000000000 即2的26次幂
开头先-1是为了防止要操作的数本身就是2的幂，然后得出来的就直接是此值的两倍了，如果本身值比较大，那这个值最终作为Node数组的长度就太浪费空间了
4、直接传入Map集合的构造方法
//此构造方法传入一个Map集合，设置加载因子为默认值，然后调用putMapEntries()
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
下面来看看putMapEntries()方法:
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
//定义int值s等于传进来的Map的Node节点数量
int s = m.size();
//判断Map集合是否是空，是空不做任何处理，那样的话，上面的构造方法等同于默认构造
if (s > 0) {
//如果初始的table为null，则走这里
if (table == null) { // pre-size
//用s除以加载因子，得出预测装入s数量元素需要的Node数组大小，+1.0补精度
float ft = ((float)s / loadFactor) + 1.0F;
//如果上步得出的ft大于默认最大数组长度，则直接赋予最大值，不然等于ft的int值
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
//如果最终得出的值t大于本来的threshold，则要对t使用tableSizeFor()方法
//得出得值再赋予threshold
if (t > threshold)
threshold = tableSizeFor(t);
}
//如果初始的table不为null，并且传进来的集合元素个数大于此集合的实际容量，则直接扩容
else if (s > threshold)
resize();
//最后循环传入的Map集合，依次调用putVal方法将元素插入现在的Map中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
//putVal()方法将在讲put方法的时候讲到
putVal(hash(key), key, value, false, evict);
}
}
}
注意:
HashMap构造方法传入的初始化数组长度值initialCapacity是为Node数组的初始化长度，虽然在构造方法各处都使用了this.threshold = tableSizeFor(initialCapacity)，并且在tableSizeFor()方法中并没有使用initialCapacity*loadFactor，但在第一次添加元素时会初始化，具体的在讲put方法时会说明
网友评论