基础知识(一) HashMap 源码详解

旧城等待， 2022-09-29 14:00 155阅读 0赞

因为最近想面试，所以复习下。分析学习基于JDK1.8

HashMap 继承于 AbstrackHashMap 实现于 Map<K,V>, Cloneable, Serializable，内部使用散列链表 红黑树实现。注意此Map不是线程安全的，如果需要同步使用请使用ConcurrentHashMap 或者 Collections.synchronizedMap

**常量参数**

1、下面的都是直接static final 的值，也就是在JVM准备的时候就已经初始化了

DEFAULT\_INITIAL\_CAPACITY =16 默认容量为

MAXIMUM\_CAPACITY =1 << 30 最大容量为

DEFAULT\_LOAD\_FACTOR = 0.75f 默认负载因子

TREEIFY\_THRESHOLD=8 链表转换红黑树的阀值

UNTREEIFY\_THRESHOLD=6 红黑树转换链表的阀值

MIN\_TREEIFY\_CAPACITY=64 桶中bin最小hash容量，如果大于这个值会进行resize扩容操作，此值至少是TREEIFY\_THRESHOLD的4倍

2、下面说下成员变量 都是 transient，也就是说不会被序列化的字段

Node<K,V>\[\] table  HashMap内部类实现了Map的内部类Entry,用于存储K,V，第一次使用的时候被创建，根据需要可以进行resize。分配长度为2的冥次方

Set<Map.Entry<K,V>> entrySet   当被调用entrySet时被赋值。通过keySet()方法可以得到map key的集合，通过values方法可以得到map value的集合

int size 存放在map中K,V的总数

int modCount  HashMap被结构性修改的次数。（结构性修改是指改变了KV映射数量的操作或者修改了HashMap的内部结构（如 rehash）。这个用于fail-fast

int threshold  进行resize的阀值，当Map中K,V数量（size） 超过了这个值，那将进行resize操作。

threshold  =DEFAULT\_INITIAL\_CAPACITY\*DEFAULT\_LOAD\_FACTOR

final float loadFactor 负载因子

**构造方法**

目前有4个构造方法

1、public HashMap(int initialCapacity, float loadFactor)

参数为初始容量，负载因子

步骤：

1、如果容量参数小于0就抛出异常

2、如果容量参数大于最大值MAXIMUM\_CAPACITY 就初始化为MAXIMUM\_CAPACITY

3、如果负载因子小于等于0或者是一个非数字就抛出异常

4、赋值负载因子

5、使用tableSizeFor 计算初始容量

**方法源码解析**

先看put方法，使用的是

**public** V put(K key , V value ) \{

**return** putVal(*hash*( key ), key , value , **false** , **true** );

内置final方法，不可被子类重写，在编译期已经静态绑定

**final** VputVal( **int** hash , K key , V value , **boolean** onlyIfAbsent , **boolean** evict )

参数：

hash 计算出的hash值

key  传入键

value 传入值

onlyIfAbsent 默认false，为true的时候不覆盖已存在的值

evict 默认true

transient Node<K,V>[] table;
    static final int TREEIFY_THRESHOLD = 8;
    transient int modCount;
    transient int size;
    int threshold;
    //新手看到这么多变量肯定晕了，记住一点，这是引用传递
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            //首先定义局部变量
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            //将目前存储table 赋值给局部变量tab 并判断其是否为空或size为0，如果为空则进行table初始化，并将初始化的size赋值给n(初始化其实就是给threshold计算出一个阀值，并new了一个node给table)
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
            //根据hash值计算出tab数组的位置并判断其是否为空，如果为空就直接把值存入一个新的Node中
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            //如果计算出的p 索引有元素存在
            else {
                Node<K,V> e; K k;
                //根据hash key判断是不是相同的元素，如果是相同的元素就把p（老元素） 赋值给新的成员变量e
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                //如果不是相同的key,只是index一样，判断元素是不是红黑树，是就将他放入树中
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                //不是一样的key hash 并且不是红黑树
                else {
                     //无限循环
                    for (int binCount = 0; ; ++binCount) {
                        //判断是否有下一个元素
                        if ((e = p.next) == null) {
                            //没有下一个元素，就将当前元素存入为下一个元素
                            p.next = newNode(hash, key, value, null);
                            //判断当前链表长度是否超过了7，则将链表元素转换为红黑树，跳出循环
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                treeifyBin(tab, hash);
                            break;
                        }
                        //判断当前index的元素是否一样，一样就赋值替换，跳出
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
                //
                if (e != null) { // existing mapping for key
                    //将老元素的value提取出
                    V oldValue = e.value;
                    //判断是否覆盖老元素的值
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    //这个方法是给LinkedHashMap留得，因为他用的也是这个put方法
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            //更新结构更改次数
            ++modCount;
            //判断+1后的size是否大于阀值默认计算出的是12)
            if (++size > threshold)
                resize();
            //这个方法是给LinkedHashMap留得，因为他用的也是这个put方法
            afterNodeInsertion(evict);
            return null;
        }

下面说下resize

int threshold;
    static final int MAXIMUM_CAPACITY = 1 << 30;
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    final float loadFactor;
        
    // 扩容方法，不能被重写
         final Node<K, V>[] resize() {
               Node<K, V>[] oldTab = table;
               // 获取当前容量
               int oldCap = (oldTab == null) ? 0 : oldTab.length;
               // 获取扩容阀值，默认0
               int oldThr = threshold;
               // newCap 新容量 newThr 新阀值
               int newCap, newThr = 0;
    
               if (oldCap > 0) {
                    // 判断其容量如果大于最大值就将扩容阀值设置为Integer最大值
                    if (oldCap >= MAXIMUM_CAPACITY) {
                          threshold = Integer.MAX_VALUE;
                          return oldTab;
                          // 判断当前容量的两倍是否小于最大容量限定，并且当前容量是否大于等于默认的16 ，满足条件就将当前容量扩大一倍
                    } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
                          newThr = oldThr << 1; // double threshold
               } else if (oldThr > 0) // initial capacity was placed in threshold
                    newCap = oldThr;
               // 走到这代表是个新map首次创建
               else { // zero initial threshold signifies using defaults
                          // 初始化容量16
                    newCap = DEFAULT_INITIAL_CAPACITY;
                    // 初始化计算扩容阀值12
                    newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
               }
               if (newThr == 0) {
                    float ft = newCap * loadFactor;
                    newThr = (newCap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE);
               }
               threshold = newThr;
               @SuppressWarnings({ "rawtypes", "unchecked" })
               Node<K, V>[] newTab = new Node[newCap];
               // 赋值扩容完的node[]给teble
               table = newTab;
               // 判断当前table是否为空，如果为null说明是新建，否则为扩容
               if (oldTab != null) {
                    // 根据当前容量循环Node
                    for (int j = 0; j < oldCap; ++j) {
                          Node<K, V> e;
                          // 先将老对象赋值给成员变量，然后判断其是否为null
                          if ((e = oldTab[j]) != null) {
                               // 将老对象设置为null，方便垃圾回收
                               oldTab[j] = null;
                               // 如果当前元素没有下一个元素，计算出其index并赋值给新node[]
                               if (e.next == null)
                                     newTab[e.hash & (newCap - 1)] = e;
                               // 判断其是否为红黑树
                               else if (e instanceof TreeNode)
                                     ((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;
                                          // 根据hash oldCap计算出结果，将符合结果的元素组建成为新的链表lo
                                          if ((e.hash & oldCap) == 0) {
                                                if (loTail == null)
                                                     loHead = e;
                                                else
                                                     loTail.next = e;
                                                loTail = e;
                                          } else {
                                                // 将不为0的元素组建成为链表hi
                                                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

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;
               //判断当前table是否为空，并根据lenght hash算出index位置
               if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
                    //直接在第一个桶中查找看是否命中
                    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<K, V>) first).getTreeNode(hash, key);
                          do {
                               //这就是链表了，直接next循环查找
                               if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                                     return e;
                          } while ((e = e.next) != null);
                    }
               }
               return null;
         }

下一篇来说下linkedHashMap