源码阅读实录
📑

源码阅读实录

Created
May 18, 2021 08:28 AM
status
being serialized

HashMap

属性

容器的源码阅读当然要从HashMap开始了,不但在开发中常用,在面试中也是高频考点。
notion image
可以从这张图得出如下结论:
  • 初始容量:16
  • 最大容量:2的30次方
  • 默认装载因子:0.75
  • 链表转化为红黑树的阈值:8
  • 红黑树退化为链表的阈值:6
  • 桶转化为树形结构的最小容量:64
先看hashMap里的一个内部类Node: 不难看出Node是一个链表节点,而Node还存有hashkeyvalue,这就是hashMap中存储数据的最小单位(根据网上查的资料JDK1.8中的Node类与之前的Entry类没有本质区别,可以看做换了个名字)。
notion image

构造方法

notion image
可以看出构造方法就是初始化了hashMap的初始大小和负载因子,如果传入的初始大小超过了最大的大小(2的30次方),那么就会赋予最大值

put 方法

put方法可以说是hashMap的核心。
notion image
put方法调用了putVal方法,传入了以key计算出的hash值,key、value,还有两个为false的参数。接下来看看putVal方法。
notion image
本人较笨,所以决定一步步分析。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)    //如果hashMap里的Node数组为空或者数组长度为0
        n = (tab = resize()).length;                       //进行扩容
    if ((p = tab[i = (n - 1) & hash]) == null)             //(n-1)&hash得到的结果就是数组下标,如果下标对应的桶里没有元素
        tab[i] = newNode(hash, key, value, null);          //就将新的Node放入,数据是传入的数据
    else {                                                 //不然,指桶里已经有元素了,如果没有碰撞,直接覆盖;如果碰撞了,拉链法解决
        HashMap.Node<K,V> e; K k;
        if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))         //如果桶中第一个元素的hash值与传入的hash值相等并且(key==p.key)||key.equals(p.key),
                                                                                //意思就是第一个元素就是我们想要添加的元素,这时put要做的事情应该是覆盖
            e = p;                                                              //就将第一个元素赋予e,用e来记录
        else if (p instanceof HashMap.TreeNode)                                 //如果不满足上述条件,意思就是这第一个元素不是我们想put的元素,即产生了碰撞,接下来应该用拉链法解决
                                                                                //如果这第一个元素是树的节点,意思是现在已经是红黑树状态
            e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);   //放入树中
        else {                                                                  //如果不是树的节点,现在是链表状态
            for (int binCount = 0; ; ++binCount) {                              //循环到链表末尾,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)))) //找到了想要插入的位置
                    break;
                p = e;                                                          //用于循环遍历
            }
        }
        if (e != null) { // existing mapping for key                            //综上所述,e所代表的的就是我们想要插入的位置里的节点
            V oldValue = e.value;                                               //接下来就是新值替换旧值,并返回旧值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;                             //直接插入数组的时候才会执行这些代码,其实就是判断是否扩容修改结构
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
notion image
还有一点细节,put在调用putVal的时候传入的是hash(key),可以看源码得知
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}//通过key的hashcode与高16位做异或运算
这么做的原因是为了增加随机性,减少碰撞的可能

get方法

get方法比较简单,直接看源码吧。
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&	//如果数组不为空且长度大于0
        													//且第一个元素不为空
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // 总是检查第一个元素
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;									//一样就返回
        if ((e = first.next) != null) {						//如果不一样,且next不为空
            if (first instanceof TreeNode)					//分情况取出
                return ((TreeNode<K,V>)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;
}

ConcurrentHashMap

ConcurrentHashMap1.8

先写1.8的吧

存储结构

ConcurrentHashMap在Java8的时候是由Node数组+链表/红黑树组成的。这个听起来十分熟悉。 HashMap也是由Node数组+链表/红黑树组成的。所以粗略一看二者的组成是相同的。

ThreadLocal

(在写另一片博客的时候临时插入)

set方法

public void set(T value) {
    Thread t = Thread.currentThread();	//获取当前线程
    ThreadLocalMap map = getMap(t);		//获取当前线程的threadLocals
    if (map != null)					//如果threadLocals为空
        map.set(this, value);			//存入value,key是this(就是ThreadLocal)
    else
        createMap(t, value);			//如果不为空,就创建新的(也存入了数据)
}

ThreadLocalMap getMap(Thread t) {
    return t.threadLocals;
}

void createMap(Thread t, T firstValue) {
    t.threadLocals = new ThreadLocalMap(this, firstValue);
}

get方法

public T get() {
    Thread t = Thread.currentThread();			//获取当前线程
    ThreadLocalMap map = getMap(t);				//获取当前线程的threadLocals
    if (map != null) {							//如果不为空
        ThreadLocalMap.Entry e = map.getEntry(this);	//得到以this为key的entry
        if (e != null) {						//如果这个entry不为空
            @SuppressWarnings("unchecked")
            T result = (T)e.value;				//返回这个entry的value
            return result;
        }
    }									//如果threadLocals或者entry为空
    return setInitialValue();			//就返回setInitialValue()
}

private T setInitialValue() {
    T value = initialValue();			//initialValue()返回的是null
    Thread t = Thread.currentThread();  //获取当前线程
    ThreadLocalMap map = getMap(t);		//获取当前线程的threadLocals
    if (map != null)					//如果threadLocals不为空,结合上部分看
        								//就是指entry为空
        map.set(this, value);			//set进一个空值
    else
        createMap(t, value);			//如果threadLocals为空,就创建
    return value;						//return的都是null
}

remove方法

public void remove() {
    ThreadLocalMap m = getMap(Thread.currentThread());
    if (m != null)
        m.remove(this);
}
//一看就懂!

InheritableThreadLocal源码实现

public class InheritableThreadLocal<T> extends ThreadLocal<T> {
    protected T childValue(T parentValue) {
        return parentValue;
    }

    ThreadLocalMap getMap(Thread t) {
        return t.inheritableThreadLocals;
    }

    void createMap(Thread t, T firstValue) {
        t.inheritableThreadLocals = new ThreadLocalMap(this, firstValue);
    }
}
InheritableThreadLocal继承自ThreadLocal,并重写了三个代码。而InheritableThreadLocal里变量**inheritableThreadLocals完全代替了threadLocals**。 InheritableThreadLocal是怎么工作的呢?我们需要去看Thread的源码。

Thread的构造函数

public Thread(Runnable target) {
    init(null, target, "Thread-" + nextThreadNum(), 0);
}

private void init(ThreadGroup g, Runnable target, String name,
                  long stackSize, AccessControlContext acc,
                  boolean inheritThreadLocals) {
    	...
        Thread parent = currentThread();		//获取当前的线程(父线程)
   		...
        if (inheritThreadLocals && parent.inheritableThreadLocals != null)
            this.inheritableThreadLocals =
            ThreadLocal.createInheritedMap(parent.inheritableThreadLocals);
    	...
}

static ThreadLocalMap createInheritedMap(ThreadLocalMap parentMap) {
    return new ThreadLocalMap(parentMap);
}
综上所述,在Thread创建的时候,子线程就会复制得到父线程的inheritableThreadLocals。 而InheritableThreadLocal的原理就是在ThreadLocal的基础上重写了三个方法,把操作的对象从threadLocals变量转换成为inheritableThreadLocals对象。
 

Loading Comments...