1,前述
很早之前就想写博客，一直想找个平台，github的自定义博客不赖，有些难度自己也没时间来研究，既然简书很好那就从简书开始吧
还有一直想研究个东西，jdk源码，虽然是java出身，对前景一直有迷惑，不知道该干嘛，想想数据结构和算法是重要的，并发又是很重要的一块，那就从研究ConcurrentHashMap开始吧
public void main(){
System.out.print("hello word !");
}
2,map接口
public interface Map<K,V> {
int size();
boolean isEmpty();
boolean containsKey(Object key);
boolean containsValue(Object value);
V get(Object key);
V put(K key, V value);
V remove(Object key);
void putAll(Map<? extends K, ? extends V> m);
void clear();
Set<K> keySet();
Collection<V> values();
Set<Map.Entry<K, V>> entrySet();
interface Entry<K,V> {
K getKey();
V getValue();
V setValue(V value);
boolean equals(Object o);
int hashCode();
}
boolean equals(Object o);
int hashCode();
}
上面列出的是jdk6中的interface内容，jdk8新增了一些方法，jdk8开始加入了default修饰符，可以在interface中写入具体的实现方法，在实现类中可以选择性决定方法的实现，本文还是以jdk8 中的内容来讲解，重点方法put () resize()，其他方法都是围绕此来展开
3,hashmap
3-1,属性
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
{
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认初始化大小16
static final int MAXIMUM_CAPACITY = 1 << 30; //默认最大容量
static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认扩容因子
transient Entry[] table;//真正的存储结构
transient int size;//当前已经存储元素的个数
int threshold; //判断size是否需要扩容的阈值。也是当前的容量，可以在后面的resize方法分析出来
final float loadFactor; //扩容因子，扩容后的容量为 loadFactor * threshold
transient volatile int modCount; //map 修改的次数，包括put 和 delete
}
transient 修饰符表示序列化时不序列化此部分， HashMap 中的存储数据的是数组，其中没有被使用到的空间被序列化没有意义。所以需要手动使用 writeObject() 方法，只序列化实际存储元素的数组
默认的参数表示如果用户不在构造器中设置则以默认为准
3-2构造
public HashMap(int initialCapacity, float loadFactor) {}
public HashMap(int initialCapacity){}
public HashMap(){}
public HashMap(Map<? extends K, ? extends V> m){}
/*
列举两个范例
*/
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);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
所有的构造器都只是对属性进行了赋值，但构造器并没有初始化 table ，这一操作在resize 方法中
loadFactor 扩容比例，如果用户不指定则以默认为准
threshold 是扩容的阀值，有时候和当前数组的容量一样，具体细节会在resize方法中分析出来，现在只是简单介绍下，分为几个情况：
如果构造中输入了initialCapacity参数，会在构造中通过tableSizeFor()计算得出，在resize方法执行时，这个值就是数组的容量，所以要保证2的次幂特性；
如果构造器中没有输入initialCapacity参数，会在resize第一次执行扩容时容量初始化为16，threshold 初始化为 12，
其中构造中的计算方法如下
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;
}
tableSizeFor方法是保证函数返回值是大于等于参数 initialCapacity 最小的2的幂次方的数值，比如initialCapacity是20，返回值32(2的5次幂)
/*
| 或运算
|= 等价于 n = n | a
>>> 无符号位的左移
int n = cap - 1;
当前cap本身就是2的次幂时，如果不减一，最终结果会变成 cap * 2，不符合我们预期
n |= n >>> 1;
右移一位，即n的二进制最高位右移1位，再与n本身或操作，最终n的高1-2位都为1
n |= n >>> 2;
右移2位，即n的二进制最高1-2位右移2位，与n本身或操作，最终n的高1-4位都是1
n |= n >>> 4;
。。。最终n的高位1-8都是1
n |= n >>> 8;
。。。最终n的高位1-16都是1
n |= n >>> 16;
。。。最终n的高位1-32都是1
这里可以举个栗子，假设给定的cap的值为20
二进制表示：0001 0011，最终执行完的结果为 0001 1111，再加1 为 0010 0000 = 32
*/
为什么cap要保持为2的幂次方？
存储数据的数组table的下标是由key的Hash值决定的。在HashMap存储数据的时候，我们期望数据能够均匀分布，以避免哈希冲突。自然而然我们就会想到去用%取余的操作来实现我们这一构想。
这里要了解到一个知识：取余(%)操作中如果除数是2的幂次方则等同于与其除数减一的与(&)操作。(这样做比直接取余操作效率要好)
如果newCap是2的次幂时，下面成立：
index = e.hash & (newCap - 1)
等同于：
index = e.hash % newCap
3-3 node
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) {
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中的静态内部类，实现Map.Entry<K,V>接口。 是map中value值的载体，除了key键、value值之外，还有next节点，元素之间可以构成单向链表。
/*
table 是map的数组，是所有数据的载体，如果key 的hash值有冲突时，就以链表存在，node提供了这种支持
*/
transient Entry[] table;
HashMap存储的数据结构：维护了一个数组，每个数组又维护了一个单向链表。之所以这么设计，考虑到遇到哈希冲突的时候，同index的value值就用单向链表来维护。
3-4 hash方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/*
index = e.hash & (newCap - 1)
^ 异或操作，一样则为0
*/
因为hash 的值最终要和 newCap-1 的值进行与操作，而 newCap 是2的次幂，减一后高位全为0，与操作时 hash 的高位就没有参与进来，index 冲突的几率会上升，h >>> 16 是将高位也参与到hash 中来能够降低 index 冲突的几率。（这是参考其他人的说法，个人不知道为何会降低）
3-5 put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
// tab 为空,调用resize()初始化tab。
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
// 通过hash和key确定要存储在table中的下标，如果没有被占用,将value封装为Node存储
tab[i] = newNode(hash, key, value, null);
else {
//当前key获取的下标位置已经被占用，可能需要用链表形式存储
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// p为数组的第一个元素，如果key相同，value值应该直接被覆盖，此时e = p为了在后面的方法中对e进行操作
e = p;
else if (p instanceof TreeNode)
// 如果p是红黑树类型，调用putTreeVal方式赋值
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// index 相同的情况下，但key不同，可能继续以链表形式存放或者转为红黑树存放
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// 如果p的next为空，将新的value值添加至链表后面
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 如果链表长度大于8，链表转化为红黑树，执行插入
treeifyBin(tab, hash);
break;
}
// key相同则跳出循环，key相同时，会继续判断是否将老的值进行替换
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
//根据规则选择是否覆盖value
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); //看源码注释好像是为LinkedHashMap准备的
return oldValue;
}
}
++modCount; //map被修改的次数
if (++size > threshold)
// size大于加载因子,扩容
resize();
afterNodeInsertion(evict); //看源码注释好像是为LinkedHashMap准备的
return null;
}
注释写的已经很好了，不需要再解释
3-6 resize方法
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;//旧table 大小
int oldThr = threshold;
int newCap, newThr = 0;
//分为2种情况，1是table已经存在，2是table 不存在需要初始化
//初始化分为两种：1threshold > 0 即初始化为自定义的长度，2反之则初始化为默认大小 （这里和构造中有关）
if (oldCap > 0) {
// table已存在
if (oldCap >= MAXIMUM_CAPACITY) {
// oldCap大于MAXIMUM_CAPACITY,threshold设置为int的最大值，并且不再继续扩容，新的元素放到链表或树
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//newCap设置为oldCap的2倍并小于MAXIMUM_CAPACITY，且大于默认值, 新的threshold增加为原来的2倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
// threshold>0, 将threshold设置为newCap,所以要用tableSizeFor方法保证threshold是2的幂次方
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 默认初始化，cap为16，threshold为12。除此之外 threshold 等于 数组的容量
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
// newThr为0，newThr = newCap * 0.75
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//当扩容后，则在现在将容器容量重新赋值给扩容阀值
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 新生成一个table数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// oldTab 复制到 newTab
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
// 链表只有一个节点，直接赋值
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// e为红黑树的情况
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
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;
}
扩容阀值和数组容量的关系
扩容分为两种情况：1是数组还不存在时需要对数组进行初始化，2是数组已经存在进行初始化
数组不存在时：
1，threshold>0, 将threshold设置为newCap也就是数组的大小,所以要用tableSizeFor方法保证threshold是2的幂次方
2，threshold = 0，将执行默认初始化数组长度为16，扩容阀值为12
数组已经存在时：
1，长度已经超过最大值，不再进行扩容，扩容阀值设置为integer的最大值，新增的元素只能以链表或tree的方式存放
2，长度没有超过最大值，则将长度设置为原有的2倍，如果扩大2倍后还没有超过数组最大值，则扩容阀值也扩大2倍
这里有个细节：如果构造器中对threshold进行了赋值，那么数组的容量和阀值一样，如果没有赋值，阀值默认为12之后扩容时阀值也会变为之前的2倍，但和数组容量并不一致
3-7remove(key) 方法 & remove(key, value) 方法
default boolean remove(Object key, Object value) {
Object curValue = get(key);
if (!Objects.equals(curValue, value) ||
(curValue == null && !containsKey(key))) {
return false;
}
remove(key);
return true;
}
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
这两个方法最终都调用了removeNode方法
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;
//判断tab不为null，长度大于0，hash 对应的数组元素 也不为null 才可以进行删除
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;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// index 元素只有一个元素，node 是需要删除的节点，先找到再后面进行删除
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
// index处是一个红黑树，则在红黑树中找到需要删除的node
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
// index处是一个链表，遍历链表寻找 node
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
//此处p的值已经不是链表的第一个元素，是需要删除node 的上一个元素
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)
//如果是第一个元素直接用next替换掉第一个
tab[index] = node.next;
else
//如果不是第一个，则把上一个的next 直接指向下一个元素，p的元素在执行到这一行时，已经不是第一个元素
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
注释写的很清楚，不需要再进行解释，这里红黑树的加入增加了处理的难度，但在目前的分析中有关treenode的部分，都有特定的方法，可以暂时不用分析也能看懂大概的逻辑，有关treenode部分，再下一节中介绍
网友评论