在学习源码之前我们先来看看下面几个概念
1、什么是散列表？
- 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
2、hash碰撞 感觉比较好的一篇文章
- 原因： 产生hash碰撞是因为通过hash计算的key值可能一样，故而造成几个值下标一样。
- 解决：
1、开放寻址(Open Addressing)法：开放寻址法把所有的元素都存放在散列表中 （线性探测、二次探测、双重散列）
2、链接(Chaining)法：
3、红黑树 里边的旋转不错
- 红黑树是一个平衡的二叉树，但不是一个完美的平衡二叉树
-
性质
1、 节点是红色或黑色
2、 根节点是黑色
3、 每个叶节点（NIL节点，空节点）是黑色的。
4、 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5、 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
红黑树.png
HashMap——源码分析
个人理解：在JDK1.8之前，HashMap采用数组+链表实现，使用链表处理冲突，同一hash值的节点都存储在一个链表里。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。而JDK1.8中，HashMap采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。
HashMap结构图.png
HashMap变量说明
- int threshold; // 阈值，等于加载因子*容量，当实际大小超过阈值则进行扩容
- 链表节点 长度小于阈值时使用
static class Node<K,V> implements Map.Entry<K,V> {
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; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
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) {
if (o == this)
return true;
if (o instanceof Map.Entry) { //注意 判断相等不仅要判断value相同还要key相同
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
- 红黑树节点 长度超过阈值时使用
static final class TreeNode<K,V> extends LinkedHashMap.LinkedHashMapEntry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
//还有好多关于红黑树操作的方法。。。
}
HashMap 构造函数
- 使用默认初始化大小(16)和默认加载因子(0.75)
- 使用初始化容量和默认加载因子(0.75)
- 根据初始化容量和加载因子构建一个空的HashMap
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
- 用已有的Map构造一个新的HashMap
HashMap 添加
public V put(K key, V value) {
//计算key的hash值调用putval添加
return putVal(hash(key), key, value, false, true);
}
/**
*onlyIfAbsent：是否修改
*evict：是否处于创建状态
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; //数组中的头
Node<K,V> p;//确定插入节点在tab位置中的头
int n, i;
//确定节点在数组中的插入位置
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//待插入位置不存在 直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else { //待插入位置存在 则进行插入 判断是链表插入还是红黑树插入 判断是否要将链表转换为红黑树等操作
Node<K,V> e;//插入的节点
K k;
////比较原来元素与待插入元素的 hash 值和 key 值 相同 直接赋值（都是一样的key那就要么修改value要么不变撒 先保存下来呗）
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
////原来元素是红黑树节点，直接调用红黑树的插入方法:putTreeVal
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {//寻找合适的位置
p.next = newNode(hash, key, value, null);//，找到最后了发现有位置了创建它的新节点
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 超过了阈值 变成红黑树吧
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
//又找到一模一样的了 那就 要么修改value要么不变撒 反正先保存下来呗
break;
p = e;
}
}
if (e != null) { // existing mapping for key 待插入的元素已经在hashMap 中已存在（之前存在或创建了）
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)//是否需要修改
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)//是否需要扩容？
resize();
afterNodeInsertion(evict);
return null;
}
//检测指定的key对应的value是否为null，如果为null，则用新value代替原来的null。
public V putIfAbsent(K key, V value) {
return putVal(hash(key), key, value, true, true);
}
其中的resize()、putTreeVal()、treeifyBin(tab, hash)等方法中逻辑 以后再做仔细的查看
HashMap 移除
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
/**
*matchValue：只有当值相等时才删除
*movable：不移动其它节点
*/
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
//判断该key的下标位置的头节点不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
//删除的节点在table中
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<K,V>)p).getTreeNode(hash, key);
else {//删除的节点是链表 查找到删除的节点
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)//删除的是树节点 树节点删除后要更新为红黑二叉树
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)//删除的节点在table中 直接将它的下一个赋值给table
tab[index] = node.next;
else//删除的节点在链表中 只需要 把删除的下一个节点赋值给 它上一个的下一个
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
removeTreeNode(this, tab, movable)方法中的逻辑以后在进行观看
//只需要将table赋值为空即可
public void clear() {
Node<K,V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
}
HashMap 修改
public V replace(K key, V value) {
Node<K,V> e;
//查找到相应的节点修改值
if ((e = getNode(hash(key), key)) != null) {
V oldValue = e.value;
e.value = value;
afterNodeAccess(e);
return oldValue;
}
return null;
}
总是感觉要看的东西太多太多，要学的东西也太多太多，大多时候太浮躁，一心想着赶紧做做做，却忽略了质量，其中很多地方都是似懂非懂，又给自己找理由“先把东西熟悉一下，以后回头学习”，不知道自己是怎的了，规定的一个月四篇文章，感觉有时候就像是在为了完成自己的任务而寥寥草事，写的东西前言不搭后语，很多时候自己都不太清楚。那就先这样吧，心太累，总感觉要学的东西太多太多了，慢慢来吧，量变终会产生质变。路漫漫其修远兮，吾将上下而求索。。。
网友评论