目录
1、 HashMap原理分析
1.1、 HashMap继承体系
1.2、Node数据结构分析
1.3、底层储存结构
1.3.1、put方法分析
1.4、hash碰撞
1.4.1、key值的唯一性
1.4.2、hash碰撞
1.5、链化
2、HashMap源码分析
2.1、HashMap构造方法源码分析
2.1.1、public HashMap(int initialCapacity, float loadFactor)
2.1.2、 public HashMap(int initialCapacity)
2.1.3、public HashMap()
2.1.4、public HashMap(Map m)
2.2、put源码
2.3、resize
2.4、get方法
2.5、remove方法
2.6、replace
1、 HashMap原理分析 1.1、 HashMap继承体系
HashMap继承体系源码
public class HashMap extends AbstractMap
implements Map, Cloneable, Serializable HashMap内部类Node的源码
//静态内部类 实现了Map.Entry这个接口 K key,V value 泛型
static class Node implements Map.Entry {
final int hash;//存放经过HashMap内的hash函数处理后的k的hash值
final K key;//存放Key值
V value;//存放Value值
Node next;//可能是红黑树或链表 由树化条件处理后决定
Node(int hash, K key, V value, Node next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }//返回key值
public final V getValue() { return value; }//返回value值
public final String toString() { return key + "=" + value; }
public final int hashCode() {//返回Node的hashCode 保证了key唯一性
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {//重写equal如果key和value完全一致就返回true
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;
}
} Map.Entry接口
interface Entry {
K getKey();
V getValue();
V setValue(V value);
boolean equals(Object o);
int hashCode();
//后面几个方法主要为实现排序这里不再解释
public static , V> Comparator> comparingByKey() {
return (Comparator> & Serializable)
(c1, c2) -> c1.getKey().compareTo(c2.getKey());
}
public static > Comparator> comparingByValue() {
return (Comparator> & Serializable)
(c1, c2) -> c1.getValue().compareTo(c2.getValue());
}
public static Comparator> comparingByKey(Comparator cmp) {
Objects.requireNonNull(cmp);
return (Comparator> & Serializable)
(c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
}
public static Comparator> comparingByValue(Comparator cmp) {
Objects.requireNonNull(cmp);
return (Comparator> & Serializable)
(c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());
}
} 当Node数组长度达到且超过64时，且链表长度达到8时，再插入一个元素时，就会升级成红黑树。
1.3.1、put方法分析如果我们插入一个键值对，它经过put方法，总共要经过5个步骤：
- map.put(1,2)
- 获取键值1的hash值
- 经过hash值扰动函数，使此hash值更散列
- 构造Node对象
- 经过路由寻址算法计算出数组的索引即存放的位置（(数组的长度-1)&key经过扰动后hash值）
既然说到了hash碰撞就在扯一下HashMap是如何保证key的唯一性的。
1.4.1、key值的唯一性从底层源码中我们可以知道HashMap重写了hashCode和equals方法,通过这两个方法来保证了key的唯一性。下面分析下源码。
//hashcode方法
public final int hashCode() {
//通过把key和value的hashCode异或 如果key和value有一个不一样返回的hashCode就不一样
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
//equals方法
public final boolean equals(Object o) {
if (o == this)//如果是基本数据类型比较到这里就可以返回true
return true;
//如果为false 有两种情况
//1、基本数据类型 2、引用数据类型 所以说不确定是否为false还是true
if (o instanceof Map.Entry) {//o判断o是否为实现Map.Entry接口
Map.Entry e = (Map.Entry)o;
if (Objects.equals(key, e.getKey()) &&//如果key和value完全一致则返回true
Objects.equals(value, e.getValue()))
return true;
}
return false;
}由于在路由寻址时，是根据key的hashCode来计算数组的索引的，是通过hashCode值随机取的索引总会有相同的时候，这时候就被称为hash碰撞。
//通过让key和key的右移16的值异或这样就能保证前16位也能参与路由寻址
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//路由寻址是通过key的经过hash扰动函数处理的hash值与数组长度-1 进行与运算
所谓链化就是数组里存放不再是单纯的一个继承object的数据类型了，而是一个链表和红黑树，这样的结构，结合了数组和链表的优点，组成的散列表的数据结构。下面来说，HashMap是如何判断在什么时候才进行链化。
在HashMap中有几个静态常量参数先介绍下
//默认数组容量 2^4
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大数组容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//用来计算阈值的一个默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//树化时链表长度也要达到8
static final int TREEIFY_THRESHOLD = 8;
//扩容的默认阈值
static final int UNTREEIFY_THRESHOLD = 6;
//最小树化(转成红黑树)数组的容量
static final int MIN_TREEIFY_CAPACITY = 64;当出现hash碰撞时，就会开始链表化了。还有一个词叫树化，也就是转为红黑树，达到树化所需要的条件就是数组容量达到64或超过64，且链表长度超过8时，就会开始树化了。
2、HashMap源码分析 2.1、HashMap构造方法源码分析 2.1.1、public HashMap(int initialCapacity, float loadFactor)//初始化Node数组容量 初始化负载因子
public HashMap(int initialCapacity, float loadFactor) {
//如果传进来的initialCapacity小于0 则返回一个错误
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//如果initialCapacity大于MAXIMUM_CAPACITY MAXIMUM_CAPACITY直接赋给initialCapacity
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//如果loadFactor小于0 或是NaN 抛出异常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);//扩容阈值
} public HashMap(int initialCapacity) {
//调用上个构造函数
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; //无参直接用默认的负载因子 数组采用延迟初始化
}//参数是map集合或其子类
public HashMap(Map m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;//负载因子默认0.75f
putMapEntries(m, false);
}
//evit这个参数 如果table处于创建阶段就是false 否则就是true
final void putMapEntries(Map m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // table还未初始化
float ft = ((float)s / loadFactor) + 1.0F;//初始化table的容量也就是长度
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY); //超出默认最大容量就直接用MAXMUM_CAPACITY
if (t > threshold)//计算新的阈值
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
for (Map.Entry e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
/*
*在HashMap中数据是存储在哈希表中的，实际上就是一个一维数组，而哈希表的大小总是是二的整数幂，这是
*因为在HashMap的resize()方法也就是扩容中，对于其所形成的链表的移动是以当前哈希表数组的下标值加上
*原来数组长度作为扩容后的数组下标，那么其最大取值就是原来数组的两倍大小，又因为其默认的初始大
*小16，故该哈希表的大小总是2的整数幂。所以在HashMap中给出了一个计算大于等于当前数值的最小二的整次
*方的方法，以方便其计算容量和其他 *** 作
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1; //>>>右移 右移一位相当除以2 |= 位运算 1 1 为1，1 0也为1，0 0也为0
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}//调用putVal
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//计算新的hash
static final int hash(Object key) {
int h;
//让原hashCode和右移16位后的hashCode进行异或运算 这样能保证高16为也能参与运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// onlyIfAbsent true 不需要改变存在的value evict ture则是不需要初始化
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//tab一个临时Node数组 保存table的指向数组的地址 p保存当前通过路由寻址找到的索引下的结点的地址
//n保存Node数组的长度 i保存路由寻址的索引
Node[] tab; Node p; int n, i;
//如果table为初始化 或length为0 则调用resize进行扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果当前索引下为null直接把新节点放到这里
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//不是空就需要判断当前节点下是链表，还是红黑树
Node e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))//当前位置key正好与新结点的key相同则只需要替换value
e = p;
else if (p instanceof TreeNode)//判断是不是红黑树
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {//不是红黑数就是链表了
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {//等于null说明走到最后一个元素了
p.next = newNode(hash, key, value, null);
//看看当前链表长度达没达到树化条件达到掉用treeifyBin看数组长度是否达到树化的标准达到就可以树化了
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))//找到相同的key就直接替换value
break;
p = e;
}
}
if (e != null) { // 替换value
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)//onlyIfAbsent 如果当前位置已存在一个值，是否替换，false是替换，true是不替换
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;//每修改一次数组就加一次
if (++size > threshold)如果size超过阈值就进行扩容
resize();
afterNodeInsertion(evict);//是为了LinkHashMap服务的这里不再解释
return null;
} final Node[] resize() {
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;//旧的数组容量
int oldThr = threshold;//旧的阈值
int newCap, newThr = 0;//新的数组容量和阈值
if (oldCap > 0) {//如果旧容量大于0说明已经初始化过了
if (oldCap >= MAXIMUM_CAPACITY) {//如果超过默认最大容量 直接把阈值设为int最大取值范围
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)//新容量在原来的基础上扩大两倍
newThr = oldThr << 1; // 阈值也扩大两倍
}
else if (oldThr > 0) //就数组容量等于0也就是未初始化 直接把旧阈值赋给新容量
newCap = oldThr;
else { // 如果阈值也没有就直接使用默认容量 阈值=默认负载因子*默认容量
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {//如果阈值还未初始化 在进行下面 *** 作
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//上面操作就是为了确定新容量和新的负载因子
//那下面就是开始扩容了
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap];//创建一个上面确定好新容量的新数组
table = newTab;//让table指向新数组
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {//很明显通过for循环一个一个复制结点
Node e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;//让旧数组的指向为null 防止oof
if (e.next == null)//如果只有e一个节点
newTab[e.hash & (newCap - 1)] = e;//通过路由算法重新找索引防止e
else if (e instanceof TreeNode)//如果是红黑树结构 就把链式结构复制过去 然后调用结点中的treeif方法构建红黑树
((TreeNode)e).split(this, newTab, j, oldCap);
else { //链表结构
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {
//使用的尾插法 但分两种情况 因为原本计算索引时 是用oldcap-1 & hash 所以最高位一定是0开头因
//此最高位可以不用考虑，但扩容之后就需要计算最高位了，所以就需要归并成两种情况。
//一种是与原数组位置一样，另外一种则是原下标加上原来数组的长度。公式就不推导了。
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
} //get方法就很明显了调用getNode找到此节点如果不存在就返回null，存在就返回value
public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e; int n; K k;
//通过key的经过扰动之后hash经路由算法(n - 1) & hash计算索引
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//下面显而易见3种情况1、正好头节点就是我们要找的2、是链表结构3、是红黑树结构
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
//第一种情况
return first;
if ((e = first.next) != null) {
//第三种红黑树
if (first instanceof TreeNode)
return ((TreeNode)first).getTreeNode(hash, key);
do {
//第二种链表
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
} //跟上面get方法基本没啥区别
public V remove(Object key) {
Node e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node[] tab; Node p; int n, index;
//既然要删除当然要先找到要删除的位置 找节点当然跟getNode没什么太大区别
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;//保存node节点的父节点
} while ((e = e.next) != null);
}
}
//找到之后就要开始删除了 也分三种情况 1、node正好是处于红黑树里的结点2、node是链表结构且位于头节点3、node不是头结点
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
} 红黑树这里不讲其原理，要讲的话内容太多了。
2.6、replace//下面两种基本差不多
@Override
public boolean replace(K key, V oldValue, V newValue) {
Node e; V v;
//如果传进来的oldvalue与找到的value相等就替换否则返回false
if ((e = getNode(hash(key), key)) != null &&
((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
e.value = newValue;
afterNodeAccess(e);
return true;
}
return false;
}
//找到就替换
@Override
public V replace(K key, V value) {
Node e;
if ((e = getNode(hash(key), key)) != null) {
V oldValue = e.value;
e.value = value;
afterNodeAccess(e);
return oldValue;
}
return null;
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）