公告:欢迎来到极梦小屋!本站资源全部可以免费下载,积分都是可以免费获取的!

HashMap源码学习(JDK8)

HashMap源码学习

HashMap是我们经常用到的集合之一,并且在面试的时候经常会问到诸如此类的问题:什么是HashMap?HashMap的工作原理是什么?当然,这些答案我们在网上能够轻易的找到,甚至更加深入的问题答案在网上也有很多大佬回答的特别清楚,但是这个并不影响我们进入HashMap类里扒一扒源码,了解一下其常用的方法及实现。

当然第一件事还是看看此类的官方描述:

​
/**
 * Hash table based implementation of the Map interface.  This
 * implementation provides all of the optional map operations, and permits
 * null values and the null key.  (The HashMap
 * class is roughly equivalent to Hashtable, except that it is
 * unsynchronized and permits nulls.)  This class makes no guarantees as to
 * the order of the map; in particular, it does not guarantee that the order
 * will remain constant over time.
 *
 *

This implementation provides constant-time performance for the basic * operations (get and put), assuming the hash function * disperses the elements properly among the buckets. Iteration over * collection views requires time proportional to the “capacity” of the * HashMap instance (the number of buckets) plus its size (the number * of key-value mappings). Thus, it’s very important not to set the initial * capacity too high (or the load factor too low) if iteration performance is * important. ……… (篇幅较长,这里就不一一复制) ​

大致意思就是:基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。(除了非同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)此类不保证映射的顺序,特别是它不保证该顺序恒久不变。 此实现假定哈希函数将元素适当地分布在各桶之间,可为基本操作(get 和 put)提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”(桶的数量)及其大小(键-值映射关系数)成比例。所以,如果迭代性能很重要,则不要将初始容量设置得太高(或将加载因子设置得太低)。HashMap 的实例有两个参数影响其性能:初始容量加载因子容量是哈希表中桶的数量,初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时,通过调用 rehash 方法将容量翻倍。 通常,默认加载因子 (.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销,但同时也增加了查询成本(在大多数 HashMap 类的操作中,包括 get 和 put 操作,都反映了这一点)。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子,以便最大限度地降低 rehash 操作次数。如果初始容量大于最大条目数乘以加载因子,则不会发生 rehash 操作。 如果很多映射关系要存储在 HashMap 实例中,则相对于按需执行自动的 rehash 操作以增大表的容量来说,使用足够大的初始容量创建它将使得映射关系能更有效地存储。注意,此实现不是同步的。如果多个线程同时访问此映射,而其中至少一个线程从结构上修改了该映射,则它必须保持外部同步。(图片来源于网络,侵删)

                        ​

hashmap继承AbstractMap<K,V>类,实现了Map<K,V>, Cloneable, Serializable接口。

​public class HashMap<K,V> extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable {

hashmap提供了四个构造函数,分别是:

1、HashMap():无参构造函数,只定义了负载因子为默认的负载因子(0.75)

     public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

2、HashMap(int initialCapacity):含初始化容量的构造函数,以传入参数作为初始化容量大小。

    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

3、HashMap(int initialCapacity, float loadFactor):含自定义的初始化容量以及自定义的负载因子为参数的构造函数

    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;//传入负载因子赋给当前map的负载因子的值
        this.threshold = tableSizeFor(initialCapacity);//以传入容量大小为参数定义容量大小(如下代码)
    }
    /**
     * Returns a power of two size for the given target capacity.返回大于初始化容量(cap)的最小2次幂的大小容量。
     */
    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;//这一步就是在n的基础上加一,目的就是成为2的次幂
    }
注:n |= n>>>1  其实就是 n = n | n>>>1。

上述位移操作可以查看这篇文章,其实最后经过tableSizeFor()之后,返回的数均是2的次幂。

4、HashMap(Map<? extends K, ? extends V> m):利用已存在的map创建hashmap

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

putMapEntries操作:

    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();//获取到传入map大小
        if (s > 0) {
            if (table == null) { //判断table是否为初始化(是否为null);
                //根据实际大小计算预估容量
                float ft = ((float)s / loadFactor) + 1.0F;
                //是否小于最大容量,是则为计算的预估容量,否则为默认的最大容量
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                (int)ft : MAXIMUM_CAPACITY);
                 //如果容量大于阈值,则返回一个大于预估值的最小二次幂数值(详见上面位移操作)
                if (t > threshold)
                    threshold = tableSizeFor(t);
            }
            else if (s > threshold) //传入map容量大于阈值
                resize(); //扩容(详见下面resize部分代码)
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {//循环遍历map数据
                K key = e.getKey();//拿到key
                V value = e.getValue();//拿到value
                putVal(hash(key), key, value, false, evict);//设值(详见下面putVal部分代码)
            }
        }
    }

resize()操作:

    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;//将table赋值给oldTab;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;//获取到oldCap 容量(初始化的值则为0)
        int oldThr = threshold;//阈值赋给oldThr 
        int newCap, newThr = 0;//初始化newCap,newThr 为0;
        if (oldCap > 0) {//判断原容量是否大于0
            if (oldCap >= MAXIMUM_CAPACITY) {//原容量大于默认最大容量
                threshold = Integer.MAX_VALUE;//int的最大值设为阈值(即最大值)
                return oldTab;//返回原集合值
            }
            //返回原容量两倍的值
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)//扩容后值大于初始化容量且小于默认最大容量
                newThr = oldThr << 1;   //新容量为原始值两倍
        }
        else if (oldThr > 0) // 判断原阈值是否大于0(第一次初始化时可能出现这种情况)
            newCap = oldThr;//新初始化容量为oldThr(原阈值)= threshold
        else { 
            //新初始化容量为默认容量,阈值为默认赋值因子乘以默认容量         
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) { //新初始化阈值为0
            float ft = (float)newCap * loadFactor; //预估阈值为初始化容量乘以负载因子
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?//判断预估阈值大小
            (int)ft : Integer.MAX_VALUE);//新初始化阈值为预估阈值 | int最大值
        }
        threshold = newThr; //新初始化阈值赋值给threshold (原阈值)
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//以新容量初始化一个节点
        table = newTab; //将新集合赋值给table(原集合)
        if (oldTab != null) {
            //循环将旧table的值放到新的新table中
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)//链表为单节点,则直接赋值到新的bucket中
                        newTab[e.hash & (newCap - 1)] = e;//e.hash & (newCap - 1)计算元素在新table中的位置
                    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;
                            //(e.hash & oldCap)用来判断元素在数组中的位置是否需要移动
                            例如:e.hash = 14 ,oldCap = 16;
                                  e.hash = 0000 1110  
                                  oldCap = 0001 0000
                                  e.hash & oldCap = 0(元素位置不变)

                                  e.hash = 17 ,oldCap = 16;
                                  e.hash = 0001 0001  
                                  oldCap = 0001 0000
                                  e.hash & oldCap = 1(元素位置改变)
                            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;//将链表节点最后一位置为null
                            newTab[j] = loHead;(位置不变的元素:原位置)
                        }
                        if (hiTail != null) {
                            hiTail.next = null;//将链表节点最后一位置为null
                            newTab[j + oldCap] = hiHead;(位置改变的元素:原位置+原集合长度)
                        }
                    }
                }
            }
        }
        return newTab;//返回扩容后新链表
    }

putval(…)操作:(增)

    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)//判断table的长度是否为0,
            n = (tab = resize()).length;//为0则resize一个初始化tab(详见尚reize操作)
        if ((p = tab[i = (n - 1) & hash]) == null)//如果要插入的键值对应的存放的位置刚好为空
            tab[i] = newNode(hash, key, value, null);//使用键值封装一个Node并插入该位置
        else {//说明该位置有元素
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))//插入元素已存在
                e = p;//p赋值给e(替换)
            else if (p instanceof TreeNode)//当前节点是红黑树,调用putTreeVal方法
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {//当前节点是链表
                for (int binCount = 0; ; ++binCount) {//遍历链表数据
                    if ((e = p.next) == null) {
                        //将插入的键值封装成node并插入链表最后
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1)//当前链表长度大于8,转换为红黑树
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))//放入的元素在node构成的链表中已存在,结束循环
                        break;
                    p = e;
                }
            }
            if (e != null) { //已存在key对应的映射(key键已存在)
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;//替换key对应的旧值(或Null值)
                afterNodeAccess(e);//空实现的函数,用作LinkedHashMap重写使用。
                return oldValue;//结束操作,modCount不增加,返回被替换的旧值
            }
        }
        ++modCount;//modCount加一
        if (++size > threshold)//插入操作后size大于阈值
            resize();//扩容
        afterNodeInsertion(evict);//空实现的函数,用作LinkedHashMap重写使用。
        return null;//插入操作结束,返回null
    }

在上述构造方法分析时,顺带把resize()以及putVal()方法说过了,接下来我们继续学习其他常用方法:

get(Object key):(根据传入的键)

    public V get(Object key) {
        Node<K,V> e;
    //调用getNode()方法获取对应节点并返回对应的value。
        return (e = getNode(hash(key), key)) == null ? null : e.value;//先将key的hashCode进行hash操作获取hash值再调用getNode()。
    }
    
    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 &&
            (first = tab[(n - 1) & hash]) != null) {//table不为空,且根据hash值计算的index下有节点
            if (first.hash == hash && // always check first node  总是检查头节点
                ((k = first.key) == key || (key != null && key.equals(k))))//链表头为要删除的节点
                return first;返回该节点
            if ((e = first.next) != null) {//index位置为链表
                if (first instanceof TreeNode)//如果链表为红黑树,则调用getTreeNode的方法并返回对应节点
                    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;//不存在对应节点则返回null
    }

remove(Object key):(根据传入键删除)

    public V remove(Object key) {
        Node<K,V> e;
        //调用removeNode()删除节点并返回删除的value
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;//先将key的hashCode进行hash操作获取hash值再调用removeNode(),并返回删除节点key对呀的value。
    }

    final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        //如果参数matchValue是true,则必须key 、value都相等才删除。 
        //如果movable参数是false,在删除节点时,不移动其他节点
        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) {//table不为空且根据hash计算的index位置有节点
            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;//将该节点赋值给node
            else if ((e = p.next) != null) {//待删除index位置的节点是链表
                if (p instanceof TreeNode)//链表是红黑树,调用getTreeNode()方法返回待删除节点并赋值给node
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {//普通链表
                    do {循环该链表找到对应节点并赋值给node
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            ////如果有待删除节点node,且 matchValue为false,或值相等
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                if (node instanceof TreeNode)//红黑树则调用removeTreeNode()方法
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)//待删除节点为链表头
                    tab[index] = node.next;//将待删除节点的下节点赋值给tab[index](头节点)
                else//待删除节点在链表中间
                    p.next = node.next;//将p(待删节点的前置节点)的后置节点指向删除节点的后置节点(其实就是将原来指向删除节点的指针指向了删除后的那个节点)
                ++modCount;//modCoun加一
                --size;//size减一
                afterNodeRemoval(node);//空实现的函数,用作LinkedHashMap重写使用。
                return node;//返回待删节点
            }
        }
        return null;//没有找到待删节点则返回null
    }

remove(Object key, Object value):(根据传入键和值删除)

    public boolean remove(Object key, Object value) {
        //此方法同时传入键和值,此时matchValue为true,即键和值都必须相等才执行删除
        return removeNode(hash(key), key, value, true, true) != null;//具体细节参看上述根据键删除方法
    }

replace() :(修改)

    public boolean replace(K key, V oldValue, V newValue) {
        Node<K,V> e; V v;
        //根据传入的键、原值、新值进行修改
        //调用getNode()方法找到对应节点并判断节点对应值是否与传入的原值相等,相等则用新值替换
        //getNode()方法参看上述的get()操作
        if ((e = getNode(hash(key), key)) != null &&
            ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
            e.value = newValue;
            afterNodeAccess(e);//空实现的函数,用作LinkedHashMap重写使用
            return true;//成功返回true
        }
        return false;//失败返回false
    }

    public V replace(K key, V value) {
        Node<K,V> e;
        //根据传入的键、新值进行修改
        //调用getNode()方法找到对应节点并用新值替换原值
        if ((e = getNode(hash(key), key)) != null) {
            V oldValue = e.value;
            e.value = value;
            afterNodeAccess(e);//空实现的函数,用作LinkedHashMap重写使用
            return oldValue;//成功返回true
        }
        return null;//失败返回false
    }

containsKey(Object key):(判断是否包含该key)

    public boolean containsKey(Object key) {
        return getNode(hash(key), key) != null;//实际调用getNode()方法
    }

containsValue(Object value):(判断是否包含该value)

    public boolean containsValue(Object value) {
        Node<K,V>[] tab; V v;
        if ((tab = table) != null && size > 0) {//哈希桶不为空
            //循环遍历hash桶上的每一个链表
            for (int i = 0; i < tab.length; ++i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                    //找到对应value就返回true
                    if ((v = e.value) == value ||
                        (value != null && value.equals(v)))
                        return true;
                }
            }
        }
        return false;//否则返回false
    }

以上是HashMap源码的简单分析,如果喜欢本文,请为我点赞,您的支持是我继续下去的动力,您也可以在评论区与我探讨或指正错误,最后别忘了关注一下我哦,谢谢。

人已赞赏
经验杂谈

EFCore初始配置

2020-11-15 18:36:41

苹果应用

Ortho - 实时透视修正相机:¥18→0【iOS限免App精选】

2020-5-9 16:09:37

6 条回复 A文章作者 M管理员
  1. 谢谢分享

  2. 谢谢

  3. 感谢分享

  4. 👍

  5. 666

  6. 😁

个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索