HashMap源码解析(一)

常量


    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认初始容量 (必须是2的幂,用左移动)

  
    static final int MAXIMUM_CAPACITY = 1 << 30;//最大容量,如果隐式指定更高的值,则使用该容量(必须是2的幂且小于等于1 << 30)

   
    static final float DEFAULT_LOAD_FACTOR = 0.75f;//加载因子(负载系数)(用来衡量HashMap满的程度)(默认0.75f)

   
    static final int TREEIFY_THRESHOLD = 8;//(链表转树的阈值)

    
    static final int UNTREEIFY_THRESHOLD = 6;//(树转链表的阈值)

 
    static final int MIN_TREEIFY_CAPACITY = 64;//容器可以树化的最小容量。 (否则,如果bin中的节点太多,则会调整表的大小。)应该至少为4 * TREEIFY_THRESHOLD,以避免调整大小和树化阈值之间的冲突。

基本哈希bin节点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);//键值的hash与上存储值的hash,Objects.hashCode()入参为null返回0
        }

        public final V setValue(V newValue) {//设置值并返回旧值
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)//内存地址相同直接返回true
                return true;
            if (o instanceof Map.Entry) {//如果是Entry 的子类
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue()))//调用当前节点key值的equal方法和当前节点value值的equal方法,结果与
                    return true;
            }
            return false;
        }
    }

静态工具类(方法)

hash(Object key)

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//key的hash值和key的hash值的高16位做异或(>>>左边高位补0)(任何数跟0异或都是其本身)(所以结果是:也就是高十六位+高十六位^低十六位)
    }

范例

hash(-10)

-10.hashCode:       1111111111111111_1111111111110110
-10.hashCode>>>16:  0000000000000000_1111111111111111 
return:             1111111111111111_0000000000001001

comparableClassFor 如果它的形式为“class C implements Comparable <C>”,则返回x的Class,否则返回null

static Class<?> comparableClassFor(Object x) {
        if (x instanceof Comparable) {//如果是比较器子类
            Class<?> c; Type[] ts, as; ParameterizedType p;
            if ((c = x.getClass()) == String.class) // bypass checks
                return c;//如果是String返回String类
            if ((ts = c.getGenericInterfaces()) != null) {//如果实现了接口
                for (Type t : ts) {//循环实现的接口
                    if (
                        (t instanceof ParameterizedType) &&
                        ((p = (ParameterizedType) t).getRawType() == Comparable.class) &&
                        (as = p.getActualTypeArguments()) != null &&
                        as.length == 1 && 
                        as[0] == c
                        ) // type arg is c
                        return c;
                }
            }
        }
        return null;//不是比价器子类
    }

compareComparables() 如果x匹配kc(k的筛选可比类),则返回k.compareTo(x),否则返回0。

@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
    static int compareComparables(Class<?> kc, Object k, Object x) {
        return (x == null || x.getClass() != kc ? 0 :
                ((Comparable)k).compareTo(x));
    }

tableSizeFor 返回给定目标容量的两个大小的幂(返回能装下传入参数的大小,且为2的次方)

static final int tableSizeFor(int cap) {
        int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);//Integer.numberOfLeadingZeros返回左边开会连续的0个数
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

Integer.numberOfLeadingZeros()返回左边最高位开始0的个数

计算范例 tableSizeFor(5)

n = -1 >>> Integer.numberOfLeadingZeros(5-1)

-1:              11111111_11111111_11111111_11111111
5-1=4:          00000000_00000000_00000000_00000100
Integer.numberOfLeadingZeros(5-1):29
-1>>>29:         00000000_00000000_00000000_00000111

n=7
n>0
n<MAXIMUM_CAPACITY
return: n+1
return: 7+1
return: 8       

变量



    transient Node<K,V>[] table;//哈希桶数组(该表在首次使用时初始化)

    
    transient Set<Map.Entry<K,V>> entrySet;//保持缓存的entrySet()  AbstractMap字段用于keySet()和values()
    
    
    transient int size;//此映射中包含的键 - 值映射的数量

    transient int modCount;//此HashMap已被结构修改的次数

   
    int threshold;//下一次需要扩容时的大小(capacity * load factor)(初值为0)

   
    final float loadFactor;//哈希表的加载因子

构造方法

HashMap()(默认的负载因子是0.75f)

 public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // 所有其他属性都是默认的(DEFAULT_LOAD_FACTOR = 0.75f)
    }

HashMap(int initialCapacity)(自定义容量)(通过tableSizeFor来计算2的次方的容量大小)

public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);//(DEFAULT_LOAD_FACTOR = 0.75f)
    }

HashMap(int initialCapacity, float loadFactor)

 public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)//容量小于0,抛出异常
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)//容量大于最大容量1 << 30
            initialCapacity = MAXIMUM_CAPACITY;//则使用最大容量
        if (loadFactor <= 0 || Float.isNaN(loadFactor))//如果负载因子小于0或者不是数字,抛出异常
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;//赋值负载因子
        this.threshold = tableSizeFor(initialCapacity);//计算容量,为2的幂
    }

HashMap(Map<? extends K, ? extends V> m)根据一个map构造一个map

 public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;//默认的负载因子
        putMapEntries(m, false);
    }

 putMapEntries(Map<? extends K, ? extends V> m, boolean evict)实现Map.putAll和Map构造函数

 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();//获取m映射数量
        if (s > 0) {//长度大于0
        
            if (table == null) { //表是空的(没有数据)
                float ft = ((float)s / loadFactor) + 1.0F;//按照默认负载因子比例计算出的大小+1
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);//小于最大容量就使用ft计算,大于最大容量使用最大容量计算
                if (t > threshold)//如果超过扩容阈值,那么就重新计算扩容阈值
                    threshold = tableSizeFor(t);//重新计算扩容阈值(2的幂)
            }
            else if (s > threshold)//如果表不是空的,且大小大于扩容阈值
                resize();//进行扩容
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {//循环插入
                K key = e.getKey();//获取key
                V value = e.getValue();//获取value
                putVal(hash(key), key, value, false, evict);
            }
        }
    }

resize()扩容

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;//旧的表
        int oldCap = (oldTab == null) ? 0 : oldTab.length;//不为空的话赋值为旧表数据量
        int oldThr = threshold;//获取扩容的阈值
        int newCap, newThr = 0;
        
        
        if (oldCap > 0) {//如果旧表不为空
        
        
            if (oldCap >= MAXIMUM_CAPACITY) {//如果旧表数据量大于最大容量
                threshold = Integer.MAX_VALUE;//扩容阈值设置成0x7fffffff(1111111111111111111111111111111)
                return oldTab;//返回旧的数据表
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY&&oldCap >= DEFAULT_INITIAL_CAPACITY)//否则,两倍大小小于最大容量,且旧的空间大于初始化空间
                newThr = oldThr << 1; // 新的阈值为旧的阈值两倍
        }
        
        
        else if (oldThr > 0) //旧表为空,且旧表阈值>0 
            newCap = oldThr;//初始容量被置于阈值
        else {   //旧表为空,且旧表阈值<0           
            newCap = DEFAULT_INITIAL_CAPACITY;//默认的空间
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//默认的阈值
        }//if (oldCap > 0)结束
        
        
        if (newThr == 0) {//如果新的阈值等于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<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {//有旧的数据
        
            for (int j = 0; j < oldCap; ++j) {// 把每个哈希桶里的值都移动到新的哈希桶中
            
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {//哈希桶位不为空
                
                    oldTab[j] = null;//原位置空
                    if (e.next == null)//如果这个桶位只有这一个元素(没有next)
                        newTab[e.hash & (newCap - 1)] = e;//用新的长度取模,数据放置位置
                    else if (e instanceof TreeNode)//如果是红黑树
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { //如果是链表
                    
                        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;
                        }
                        
                    }//(e.next == null)的else结尾
                    
                }//if ((e = oldTab[j]) != null)结尾
                
            }// for (int j = 0; j < oldCap; ++j)结尾
            
            
        }//if (oldTab != null)结尾
        
        return newTab;
    }

putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) 放置值

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)//如果桶是空的,或者桶的长度是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;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))//和链表的第一个值同值,进行覆盖
                e = p;
            else if (p instanceof TreeNode)//红黑树
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {//binCount为下标指针循环链表
                    if ((e = p.next) == null) {//循环到链表的末尾(next为空)
                        p.next = newNode(hash, key, value, null);//把插入的节点作为链表的末尾的下一个节点
                        if (binCount >= TREEIFY_THRESHOLD - 1) //如果达到树化的阈值,那么转化为树
                            treeifyBin(tab, hash);
                        break;//结束循环
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))//插入的节点和链表某一个节点相同,直接跳出
                        break;
                    p = e;//循环指针p移到下一位
                }
            }
            if (e != null) { //已存在映射,覆盖
                V oldValue = e.value;//获取旧值
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;//赋值
                afterNodeAccess(e);//后期回调操作
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)//是否达到扩容阈值
            resize();
        afterNodeInsertion(evict);//后期回调操作
        return null;
    }

评论

暂无评论