Java教程

HashMap(1.8)源码学习

本文主要是介绍HashMap(1.8)源码学习,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

一.HashMap介绍

1.哈希表(hash table)

  • 在哈希表中进行添加,删除,查找等操作,时间复杂度为O(1)

  • 存储位置 = f(关键字)

    其中,这个函数f一般称为哈希函数,这个函数的设计好坏会直接影响到哈希表的优劣

    将key通过哈希算法计算出哈希值,把哈希值作为数组下标

    通过该方法建立的数组就叫做哈希表

  • 哈希冲突

    当我们对某个元素进行哈希运算,得到一个存储地址,然后要进行插入的时候,发现已经被其他元素占用了,其实这就是所谓的哈希冲突,也叫哈希碰撞。

    • 解决方案:

      • 开放定址法

        开放地执法有一个公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1)
        其中,m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,…m-1,称线性探测再散列。

      • 再散列函数法

        当发生冲突时,使用第二个、第三个、哈希函数计算地址,直到无冲突时。缺点:计算时间增加。

      • 链地址法(拉链法)

        将所有关键字为同义词的记录存储在同一线性链表中

2.HashMap实现原理

2.1 Map

  • HashMap是Map的主要实现类,线程不安全的,效率高;可以存储null的key和value
  • Map就是用于存储键值对(<key,value>)的集合类,也可以说是一组键值对的映射(数学概念),在java中map是一个接口,是和collection接口同一等级的集合根接口。
  • Map特点:
    • key键值不可以重复
    • 每个key只能对应一个value,多个key可以对应一个value
    • key,value 都可以是任何引用类型(包括 null)的数据(只能是引用类型)

2.2 HashMap

  • HashMap是用数组 + 单链表 + 红黑树实现的map类。

  • HashMap 的实现不是同步的,这意味着它不是线程安全的。

  • 扩容机制和哈希函数越合理,空间成本越小,哈希函数计算结果越分散均匀。越分散发生哈希冲突的几率就越小

3.红黑树

、、、、、、、、

二.源码部分

1.基本属性

AbstractMap<K, V> :AbstractMap 提供了 Map 的基本实现,使得我们以后要实现一个 Map 不用从头开始,只需要继承 AbstractMap, 然后按需求实现/重写对应方法即可。

Map是Java集合框架的根接口,另一个是Collection接口

Cloneable接口是一个标记接口,也就是没有任何内容

Serializable 接口之所以定义为空,是因为它只起到了一个标识的作用,告诉程序实现了它的对象是可以被序列化的,但真正序列化和反序列化的操作并不需要它来完成。

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    private static final long serialVersionUID = 362498820763181265L;
/**
 * The default initial capacity - MUST be a power of two.
 * 默认的初始容量--必须是2的幂
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * The maximum capacity, used if a higher value is implicitly specified
 * by either of the constructors with arguments.
 * MUST be a power of two <= 1<<30.
 * 哈希表的最大容量为2^30
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * The load factor used when none specified in constructor.
 * 在构造函数中未指定时使用的负载系数,负载因子默认为0.75f
 * 当元素的总个数>当前数组的长度 * 负载因子。数组会进行扩容,扩容为原来的两倍
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * The bin count threshold for using a tree rather than list for a
 * bin.  Bins are converted to trees when adding an element to a
 * bin with at least this many nodes. The value must be greater
 * than 2 and should be at least 8 to mesh with assumptions in
 * tree removal about conversion back to plain bins upon
 * shrinkage.
 * 当链表结点到达8时转换为红黑树
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * The bin count threshold for untreeifying a (split) bin during a
 * resize operation. Should be less than TREEIFY_THRESHOLD, and at
 * most 6 to mesh with shrinkage detection under removal.
 * 当红黑树结点小于6时重新转化为链表
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * The smallest table capacity for which bins may be treeified.
 * 可以树形化容器的最小表容量。
 * (Otherwise the table is resized if too many nodes in a bin.)
 * 否则,如果容器中的节点太多,则会调整表的大小
 * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
 * between resizing and treeification thresholds.
 * 当Table所有元素超过该值,才会进行树化(为了防止前期阶段频繁扩容和树化过程冲突)
 */
static final int MIN_TREEIFY_CAPACITY = 64;
/* ---------------- Fields -------------- */

/**
 * The table, initialized on first use, and resized as
 * necessary. When allocated, length is always a power of two.
 * (We also tolerate length zero in some operations to allow
 * bootstrapping mechanics that are currently not needed.)
 * node数组
 */
transient Node<K,V>[] table;

/**
 * Holds cached entrySet(). Note that AbstractMap fields are used
 * for keySet() and values().
 * 存放键值对的集合
 */
transient Set<Map.Entry<K,V>> entrySet;

/**
 * The number of key-value mappings contained in this map.
 *键-值映射的数量
 */
transient int size;

/**
 * The number of times this HashMap has been structurally modified
 * 这个HashMap被结构修改的次数
 * Structural modifications are those that change the number of mappings in
 * the HashMap or otherwise modify its internal structure
 * 结构修改是HashMap中那些改变映射数量的修改或修改其内部结构
 * (e.g.,
 * rehash).  This field is used to make iterators on Collection-views of
 * the HashMap fail-fast.  (See ConcurrentModificationException).
 */
transient int modCount;

/**
 * The next size value at which to resize (capacity * load factor).
 *要调整大小的下一个大小值,边界值
 * @serial
 */
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;

/**
 * The load factor for the hash table.
 *哈希表的加载因子
 * @serial
 */
final float loadFactor;

2.结构

  • 如2.2中的图,顶层为动态数组,每个元素为一个node
    而每个node又是一个链表的头节点
    node的next指向下个hash值相同的结点
    /**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     * node内部类,node
     */
    static class Node<K,V> implements Map.Entry<K,V> {
        //当前的hash值
        final int hash;
        //键值
        final K key;
        //数据值
        V value;
        //指向node
        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;
        }
        //返回node键值的get方法
        public final K getKey()        { return key; }
        //返回node数据的get方法
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }
        //value的set方法
        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;
        }
    }
static final class TreeNode<K,V> extends LinkedHashMap.Entry<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);
    }

3.构造函数

/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and load factor.
 *构造一个手动设置初始容量和负载因子的空hashmap
 * @param  initialCapacity the initial capacity
 * @param  loadFactor      the load factor
 * @throws IllegalArgumentException if the initial capacity is negative
 *         or the load factor is nonpositive
 */
public HashMap(int initialCapacity, float loadFactor) {
    //如果设置的初始容量小于0,抛出异常
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    //如果手动设置的初始容量大于最大容量,则设置为最大容量,即2^30 = 1,073,741,824
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    //如若设置的负载因子<=0 或者
    //NaN全称是Not a Number,意思是“不是一个数字”,代表一种不合法,即float值和double值不合法。
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    //将负载因子赋值
    this.loadFactor = loadFactor;
    //将初始容量的2次幂值赋给边界值
    this.threshold = tableSizeFor(initialCapacity);
}
/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and the default load factor (0.75).
 *使用指定的初始容量构造一个空的HashMap
 * 负载因子为默认的0.75
 * @param  initialCapacity the initial capacity.
 * @throws IllegalArgumentException if the initial capacity is negative.
 */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**
 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 * (16) and the default load factor (0.75).
 * 无参构造
 * 初始容量为默认值 16
 * 默认负载因子也为0.75
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
 * Constructs a new <tt>HashMap</tt> with the same mappings as the
 * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
 * default load factor (0.75) and an initial capacity sufficient to
 * hold the mappings in the specified <tt>Map</tt>.
 *根据传入的map,使用相同的映射构造一个新的HashMap
 * 负载因子为0.75
 * @param   m the map whose mappings are to be placed in this map
 * @throws  NullPointerException if the specified map is null
 */
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}
/**
 * Returns a power of two size for the given target capacity.
 * 返回给定目标容量的2次幂大小
 * 由于HashMap的capacity都是2的幂,因此这个方法用于找到大于等于initialCapacity的最小的2的幂(initialCapacity如果就是2的幂,则返回的还是这个数)。
 */
static final int tableSizeFor(int cap) {
    //cap-1是当进入的数本身为二次幂数而进行转换
    //让最高位的1后面的位全变为1,最后加1,就得到了2次幂大小
    //当32为都为1的时候,容量为MAXIMUM_CAPACITY
    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;
}

img

4.hashcode

  • Java中的hashCode方法就是根据一定的规则将与对象相关的信息(比如对象的存储地址,对象的字段等)映射成一个数值,这个数值称作为散列值。

  • 由于和(length-1)运算,length 绝大多数情况小于2的16次方。所以始终是hashcode 的低16位(甚至更低)参与运算。要是高16位也参与运算,会让得到的下标更加散列。

  •   static final int hash(Object key) {
          int h;
          //h >>> 16是用来取出h的高16,(>>>是无符号右移)
          return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
      }
    

5.get方法

public V get(Object key) {
    Node<K,V> e;
    //找不到键映射的值,返回null,否则返回value
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
 * Implements Map.get and related methods
 *get操作是通过调用getNode方法
 * @param hash hash for key
 * @param key the key
 * @return the node, or null if none
 */
final Node<K,V> getNode(int hash, Object key) {
    //
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //在table不为空的情况下
    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;
        //以下为first node不是目标结点的情况
        if ((e = first.next) != null) {
            //判断是否为红黑树对象
            //instanceof是Java中的二元运算符,左边是对象,右边是类;当对象是右边类或子类所创建对象时,返回true;否则,返回false。
            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);
        }
    }
    //没找到,返回null
    return null;
}

instanceof是Java中的二元运算符,左边是对象,右边是类;当对象是右边类或子类所创建对象时,返回true;否则,返回false。

6.put方法

/**
 * Associates the specified value with the specified key in this map.
 * If the map previously contained a mapping for the key, the old
 * value is replaced.
 * 将键/值对添加到 hashMap 中
 * 如果先前的映射包含一个键的映射,则旧的value被替换。
 * @param key key with which the specified value is to be associated
 * @param value value to be associated with the specified key
 * @return the previous value associated with <tt>key</tt>, or
 *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 *         (A <tt>null</tt> return can also indicate that the map
 *         previously associated <tt>null</tt> with <tt>key</tt>.)
 */
public V put(K key, V value) {
    //false: onlyIfAbsent,表示改变现有值
    //true: 不处于创建模式
    return putVal(hash(key), key, value, false, true);
}
/**
 * Implements Map.put and related methods
 *实现了地图Map.put及相关方法
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 *        如果为true,则不更改现有值
 * @param evict if false, the table is in creation mode.
 *        如果为false,则表示表处于创建模式
 * @return previous value, or null if none
 */
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为空,则进行扩容操作
    if ((tab = table) == null || (n = tab.length) == 0)
        //n 为扩容后的长度
        n = (tab = resize()).length;
    //如果 tab[i]为空,则新建结点
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        //n = (tab = resize()).length
        //p目前指向tab[i = (n - 1) & hash],也就是数组的最后一个元素
        //如果p的hash有相同的,且key != null,说明键值已经存在了
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            //把p存储在e中
            e = p;
        //如果p结点为红黑树结点
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            //遍历链表
            for (int binCount = 0; ; ++binCount) {
                //如果p结点没有后继结点,则新建链表节点
                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 = p.next;
                p = e;
            }
        }
        //如果e不为空说明hashmap本来就存储了键值
        if (e != null) { // existing mapping for key
            //把原来的vlue保存起来
            V oldValue = e.value;
            //当相同可以修改的时候,进行重新赋值操作
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            //继承HashMap的LinkedHashMap类服务的
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //在进行一次扩容判断
    if (++size > threshold)
        resize();
    //继承HashMap的LinkedHashMap类服务的
    afterNodeInsertion(evict);
    return null;
}

7.resize()方法

/**
 * Initializes or doubles table size.  If null, allocates in
 * accord with initial capacity target held in field threshold.
 * Otherwise, because we are using power-of-two expansion, the
 * elements from each bin must either stay at same index, or move
 * with a power of two offset in the new table.
 * 初始化或加倍表大小
 * @return the table
 */
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    //旧容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //旧阈值
    int oldThr = threshold;
    int newCap, newThr = 0;
    //如果旧的容量大于0,则以2的幂次加倍table的容量
    if (oldCap > 0) {
        //如果容量已经为最大值时,将边界值也赋值成最大值,返回原来的table
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //newCap * 2 小于最大容量,且oldCap大于等于默认容量(已经初始化过的table),阈值 * 2
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    //oldCap <= 0,但是oldThr > 0,说明构造hashtable对象时,手动设置了容量
    else if (oldThr > 0) // initial capacity was placed in threshold 初始容量设置为threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults 零初始阈值表示使用默认值,16
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //??
    if (newThr == 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;
            //如果 j 结点不为空,则将其先保存在e中,并将原结点设置为null
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                //如果该结点没有后继结点(树,链表),直接把这个结点放在新的数组中
                //根据当前节点的hash值与新数组容量减1做&运算,得到新数组的插入位置
                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;
                        //新的位置在原位置
                        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) {
                        //再将最后的结点赋值为null
                        loTail.next = null;
                        //再将数组头节点赋给数组
                        newTab[j] = loHead;
                    }
                    //高位同样操作
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    //返回新的数组
    return newTab;
}

8.遍历方法

  • 先遍历key,再取出value

    /**
     * Returns a {@link Set} view of the keys contained in this map.
     * The set is backed by the map, so changes to the map are
     * reflected in the set, and vice-versa.  If the map is modified
     * while an iteration over the set is in progress (except through
     * the iterator's own <tt>remove</tt> operation), the results of
     * the iteration are undefined.  The set supports element removal,
     * which removes the corresponding mapping from the map, via the
     * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
     * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
     * operations.  It does not support the <tt>add</tt> or <tt>addAll</tt>
     * operations.
     *     返回 hashMap 中所有 key 组成的集合视图
     * @return a set view of the keys contained in this map
     */
    public Set<K> keySet() {
        Set<K> ks = keySet;
        if (ks == null) {
            ks = new KeySet();
            keySet = ks;
        }
        return ks;
    }
    

    然后通过get方法都得到value

  • 直接遍历value

    /**
     * Returns a {@link Collection} view of the values contained in this map.
     * The collection is backed by the map, so changes to the map are
     * reflected in the collection, and vice-versa.  If the map is
     * modified while an iteration over the collection is in progress
     * (except through the iterator's own <tt>remove</tt> operation),
     * the results of the iteration are undefined.  The collection
     * supports element removal, which removes the corresponding
     * mapping from the map, via the <tt>Iterator.remove</tt>,
     * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
     * <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
     * support the <tt>add</tt> or <tt>addAll</tt> operations.
     * 返回 hashMap 中存在的所有 value 值。
     * @return a view of the values contained in this map
     */
    public Collection<V> values() {
        Collection<V> vs = values;
        if (vs == null) {
            vs = new Values();
            values = vs;
        }
        return vs;
    }
    
  • 通过遍历entry来取key和value

    /**
     * Returns a {@link Set} view of the mappings contained in this map.
     * The set is backed by the map, so changes to the map are
     * reflected in the set, and vice-versa.  If the map is modified
     * while an iteration over the set is in progress (except through
     * the iterator's own <tt>remove</tt> operation, or through the
     * <tt>setValue</tt> operation on a map entry returned by the
     * iterator) the results of the iteration are undefined.  The set
     * supports element removal, which removes the corresponding
     * mapping from the map, via the <tt>Iterator.remove</tt>,
     * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
     * <tt>clear</tt> operations.  It does not support the
     * <tt>add</tt> or <tt>addAll</tt> operations.
     * 返回键值对
     * @return a set view of the mappings contained in this map
     */
    public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
    }
    
  • 通过foreach方法直接遍历key和value

    //对 hashMap 中的每个映射执行指定的操作。
        @Override
        // BiConsumer是一个功能接口。 它接受两个参数,但不返回任何内容
        public void forEach(BiConsumer<? super K, ? super V> action) {
            Node<K,V>[] tab;
            //如果action为0,则抛出异常
            if (action == null)
                throw new NullPointerException();
            //如果size大于0, 并且将table 赋给tab
            if (size > 0 && (tab = table) != null) {
                int mc = modCount;
                //遍历哈希表
                for (int i = 0; i < tab.length; ++i) {
                    //遍历表上的链表节点或者树节点
                    for (Node<K,V> e = tab[i]; e != null; e = e.next)
                        action.accept(e.key, e.value);
                }
                if (modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }
    

9.remove方法

/**
 * Removes the mapping for the specified key from this map if present.
 * 删除 hashMap 中指定键 key 的映射关系
 * @param  key key whose mapping is to be removed from the map
 * @return the previous value associated with <tt>key</tt>, or
 *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 *         (A <tt>null</tt> return can also indicate that the map
 *         previously associated <tt>null</tt> with <tt>key</tt>.)
 */
public V remove(Object key) {
    Node<K,V> e;
    //调用removeNode方法,若无则返回null,否则返回value
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}
/**
 * Implements Map.remove and related methods
 * 实现了MAP移除及相关方法
 * @param hash hash for key
 * @param key the key
 * @param value the value to match if matchValue, else ignored
 * @param matchValue if true only remove if value is equal
 *                   如果为true,只在value相等时移除
 * @param movable if false do not move other nodes while removing
 *                如果为false,则在移除时不要移动其他节点
 * @return the node, or null if none
 */
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;
    //同样的在复制的同时,做一个合法性检查
    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))))
            node = p;
        //如果不是,就遍历链表或者红黑树
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    //判断key值相等,则为目标节点
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                    //直到结点遍历完
                } while ((e = e.next) != null);
            }
        }
        //在结点找到,且matchValue为false 或者 两个value相等的时候,则删除结点
        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);
            //如果node为头节点,则将其next变成头节点
            else if (node == p)
                tab[index] = node.next;
            else
                //这时p为e的前驱结点,就将node删除
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            //返回结点
            return node;
        }
    }
    return null;
}

三.总结

  1. HashMap的初始长度为什么是16?每次自动扩展或是手动初始化时,长度为什么是2的幂?

    • HashMap的默认长度为16,15的二进制为1111,做与运算的时候,降低了hash碰撞的几率
    • 容量为2的整数幂是为了让(2^n)-1的二进制是全1 的,符合hash均匀分布的原则
  2. 为什么要引入红黑树?

    为了提高查询效率,故在JDK1.8中引入了改进方法红黑树。此数据结构的平均查询效率为O(log n) 。

  3. 什么是加载因子、负载因子、边界值?

    • 加载因子:用于表示哈希表中元素填满的程度。

      • 加载因子越大,填满的元素越多,好处是,空间利用率高了,但,冲突的机会加大了.反之,亦同。

      • 冲突的机会越大,则查找的成本越高.反之,查找的成本越小.因而,查找时间就越小.

      • 默认的加载因子: static final float DEFAULT_LOAD_FACTOR = 0.75f;

    • 负载因子:等同于加载因子,也叫扩容因子

    • 边界值: threshold

      • threshold = capacity * loadFactory
  4. 怎么计算key值的存储位置?

    hash & (cap - 1)

    扩容时:e.hash & oldCap

这篇关于HashMap(1.8)源码学习的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!