面试必问的HashMap,你真的了解吗?

栏目: 数据库 · 发布时间: 4年前

内容简介:HashMap是Map中最为常用的一种,面试中也经常会被问到相关的问题。由于HashMap数据结构较为复杂,回答相关问题的时候往往不尽人意,尤其是在JDK1.8之后,又引入了红黑树结构,其数据结构变的更加复杂,本文就JDK1.8源码为例,对HashMap进行分析;构造方法一共重载了四个,主要初始化了三个参数:我们最常使用的是无参构造,在这个构造方法里面仅仅设置了加载因子为默认值,其他两个参数会在resize方法里面进行初始化,在这里知道这个结论就可以了,下面会在源码里面进行分析;另外一个带有两个参数的构造方

前言

HashMap是Map中最为常用的一种,面试中也经常会被问到相关的问题。由于HashMap数据结构较为复杂,回答相关问题的时候往往不尽人意,尤其是在JDK1.8之后,又引入了红黑树结构,其数据结构变的更加复杂,本文就JDK1.8源码为例,对HashMap进行分析;

源码分析

1.1 老规矩,先上构造方法

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;
        this.threshold = tableSizeFor(initialCapacity);
    }

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


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

    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

构造方法一共重载了四个,主要初始化了三个参数:

  • initialCapacity 初始容量(默认16):hashMap底层由数组实现+链表(或红黑树)实现,但是还是从数组开始,所以当储存的数据越来越多的时候,就必须进行扩容操作,如果在知道需要储存数据大小的情况下,指定合适的初始容量,可以避免不必要的扩容操作,提升效率
  • threshold 阈值:hashMap所能容纳的最大价值对数量,如果超过则需要扩容,计算方式:threshold=initialCapacity*loadFactor(构造方法中直接通过tableSizeFor(initialCapacity)方法进行了赋值,主要原因是在构造方法中,数组table并没有初始化,put方法中进行初始化,同时put方法中也会对threshold进行重新赋值,这个会在后面的源码中进行分析)
  • loadFactor 加载因子(默认0.75):当负载因子较大时,去给table数组扩容的可能性就会少,所以相对占用内存较少(空间上较少),但是每条entry链上的元素会相对较多,查询的时间也会增长(时间上较多)。反之就是,负载因子较少的时候,给table数组扩容的可能性就高,那么内存空间占用就多,但是entry链上的元素就会相对较少,查出的时间也会减少。所以才有了负载因子是时间和空间上的一种折中的说法。所以设置负载因子的时候要考虑自己追求的是时间还是空间上的少。(一般情况下不需要设置,系统给的默认值已经比较适合了)

我们最常使用的是无参构造,在这个构造方法里面仅仅设置了加载因子为默认值,其他两个参数会在resize方法里面进行初始化,在这里知道这个结论就可以了,下面会在源码里面进行分析;另外一个带有两个参数的构造方法,里面对初始容量和阈值进行了初始化,对阈值的初始化方法为 tableSizeFor(int cap),看一下源码:

public HashMap(int initialCapacity, float loadFactor) {
    /**
     * 找到大于或等于 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;
    }

第一次看到这个方法的时候,我当时的心情是:

面试必问的HashMap,你真的了解吗?

接下来分析一下这个方法,对于无符号右移运算符不了解的,可以看一下这篇文章了解一下( https://www.jianshu.com/p/927... ),下面偷一张图(真的是借别人的图,google搜索的,不知道是谁的,如果大佬觉得太可耻,私信我我删了他)以10为例进行分析:

面试必问的HashMap,你真的了解吗?

另外,需要注意一下的是,第一步  int n = cap - 1; 这个操作,执行这个操作的主要原因是为了防止在cap已经是2的n次幂的情况下,经过运算后得到的结果是cap的二倍的结果,例如如果n为l6,经过一系列运算之后,得到的结果是0001 1111,此时最后一步n+1 执行之后,就会返回32,有兴趣的可以自己进行尝试;

1.2 put方法

在hashMap源码中,put方法逻辑是最为复杂的,接下来先看一下源码:

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    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尚未初始化,则此处进行初始化数组,并赋值初始容量,重新计算阈值
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            //通过hash找到下标,如果hash值指定的位置数据为空,则直接将数据存放进去
            tab[i] = newNode(hash, key, value, null);
        else {
            //如果通过hash找到的位置有数据,发生碰撞
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                //如果需要插入的key和当前hash值指定下标的key一样,先将e数组中已有的数据
                e = p;
            else if (p instanceof TreeNode)
                //如果此时桶中数据类型为 treeNode,使用红黑树进行插入
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                //此时桶中数据类型为链表
                // 进行循环
                for (int binCount = 0; ; ++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;
                    }
                    //如果链表中有新插入的节点位置数据不为空,则此时e 赋值为节点的值,跳出循环
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }

            //经过上面的循环后,如果e不为空,则说明上面插入的值已经存在于当前的hashMap中,那么更新指定位置的键值对
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        //如果此时hashMap size大于阈值,则进行扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

从代码看,put方法分为三种情况:

  • table尚未初始化,对数据进行初始化
  • table已经初始化,且通过hash算法找到下标所在的位置数据为空,直接将数据存放到指定位置
  • table已经初始化,且通过hash算法找到下标所在的位置数据不为空,发生hash冲突(碰撞),发生碰撞后,会执行以下操作:
  • 判断插入的key如果等于当前位置的key的话,将 e 指向该键值对
  • 如果此时桶中数据类型为 treeNode,使用红黑树进行插入
  • 如果是链表,则进行循环判断, 如果链表中包含该节点,跳出循环,如果链表中不包含该节点,则把该节点插入到链表末尾,同时,如果链表长度超过树化阈值(TREEIFY_THRESHOLD)且table容量超过最小树化容量(MIN_TREEIFY_CAPACITY),则进行链表转红黑树(由于table容量越小,越容易发生hash冲突,因此在table容量<MIN_TREEIFY_CAPACITY 的时候,如果链表长度>TREEIFY_THRESHOLD,会优先选择扩容,否则会进行链表转红黑树操作)

首先分析table尚未初始化的情况:

如果还想了解更多关于Hashmap有关的知识,这里有准备了一期专门讲解Hashmap源码的视频: https://pan.baidu.com/s/1DZxu... 提取码: br53

1.2.1 table尚未初始化

n = (tab = resize()).length;

从代码可以看出,table尚未初始化的时候,会调用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;

        //1、table已经初始化,且容量 > 0
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                //如果旧的容量已近达到最大值,则不再扩容,阈值直接设置为最大值
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                //如果旧的容量不小于默认的初始容量,则进行扩容,容量扩张为原来的二倍
                newThr = oldThr << 1; // double threshold
        }
        //2、阈值大于0 threshold 使用 threshold 变量暂时保存 initialCapacity 参数的值
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        //3 threshold 和 table 皆未初始化情况,此处即为首次进行初始化
        //也就在此处解释了构造方法中没有对threshold 和 初始容量进行赋值的问题
        else {               // zero initial threshold signifies using defaults
            //如果阈值为零,表示使用默认的初始化值
            //这种情况在调用无参构造的时候会出现,此时使用默认的容量和阈值
            newCap = DEFAULT_INITIAL_CAPACITY;
            //此处阈值即为 threshold=initialCapacity*loadFactor
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        // newThr 为 0 时,按阈值计算公式进行计算,容量*负载因子
        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;

        //如果之前的数组桶里面已经存在数据,由于table容量发生变化,hash值也会发生变化,需要重新计算下标
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                //如果指定下标下有数据
                if ((e = oldTab[j]) != null) {
                    //1、将指定下标数据置空
                    oldTab[j] = null;
                    //2、指定下标只有一个数据
                    if (e.next == null)
                        //直接将数据存放到新计算的hash值下标下
                        newTab[e.hash & (newCap - 1)] = e;
                    //3、如果是TreeNode数据结构
                    else if (e instanceof TreeNode)

                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    //4、对于链表,数据结构
                    else { // preserve order
                        //如果是链表,重新计算hash值,根据新的下标重新分组
                        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;
                        }
                    }
                }
            }
        }
        return newTab;
    }

resize方法逻辑比较复杂,需要静下心来一步步的分析,但是总的下来,分为以下几步:

  • 首先先判断当前table是否进行过初始化,如果没有进行过初始化,此处就解决了调用无参构造方法时候,threshold和initialCapacity 未初始化的问题,如果已经初始化过了,则进行扩容,容量为原来的二倍
  • 扩容后创建新的table,并对所有的数据进行遍历
  • 如果新计算的位置数据为空,则直接插入
  • 如果新计算的位置为链表,则通过hash算法重新计算下标,对链表进行分组
  • 如果是红黑树,则需要进行拆分操作

1.3 get方法,查找

put方法分析完成之后,剩下的就很简单了,先看一下源码:

   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 &&
            (first = tab[(n - 1) & hash]) != null) {

            //1、根据hash算法找到对应位置的第一个数据,如果是指定的key,则直接返回
            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 {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

get方法相对于put来说,逻辑实在是简单太多了

  1. 根据hash值查找到指定位置的数据
  2. 校验指定位置第一个节点的数据是key是否为传入的key,如果是直接返回第一个节点,否则继续查找第二个节点
  3. 如果数据是TreeNode(红黑树结构),直接通过红黑树查找节点数据并返回
  4. 如果是链表结构,循环查找所有节点,返回数据
  5. 如果没有找到符合要求的节点,返回null

在这个方法里面,需要注意的有两个地方:hash(key)和hash的取模运算 (n - 1) & hash

1.3.1 hash(key)的源码

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }

这段代码叫做扰动函数,也是hashMap中的hash运算,主要分为下面几步:

  • key.hashCode(),获取key的hashCode值,如果不进行重写的话返回的是根据内存地址得到的一个int值
  • key.hashCode() 获取到的hashcode无符号右移16位并和元hashCode进行^ ,这样做的目的是为了让高位与低进行混合,让两者都参与运算,以便让hash值分布更加均匀

1.3.2 取模运算 (n - 1) & hash

在hashMap的代码中,在很多地方都会看到类似的代码:

first = tab[(n - 1) & hash])

hash算法中,为了使元素分布的更加均匀,很多都会使用取模运算,在hashMap中并没有使用(n)%hash这样进行取模运算,而是使用(n - 1) & hash进行代替,原因是在计算机中,&的效率要远高于%;需要注意的是,只有容量为2的n次幂的时候,(n - 1) & hash 才能等效(n)%hash,这也是hashMap 初始化初始容量时,无论传入任何值,都会通过tableSizeFor(int cap) 方法转化成2的n次幂的原因,这种巧妙的设计真的很令人惊叹;至于为什么只有2的n次幂才能这样进行取模运算,这里就不再详细叙述了,有兴趣的可以看一下一位大佬写的文章:

由HashMap哈希算法引出的求余%和与运算&转换问题

https://www.cnblogs.com/ysoce...

1.4 remove方法,删除

了解完get方法之后,我们再最后了解一下remove方法:

public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }

    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;

        //根据key和key的hash值,查找到对应的元素
        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 {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }

            //如果查找的了元素node,移除即可
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                //如果是TreeNode,通过树进行移除
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                //如果是第一个节点,移除第一个节点,将index下标的位置指向第二个节点
                else if (node == p)
                    tab[index] = node.next;
                else
                    //如果不是链表的第一个节点,则移除该节点
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

从源码可以看出来,通过key找到需要移除的元素操作过程和get方法几乎一致,最后在查找到key对应的节点之后,根据节点的位置和类型,进行相应的移除操作就完成了,过程非常简单

1.4.0 其他源码

到这里,hashMap的源码基本就解析完成了,其余的方法和源码逻辑相对非常简单,大部分还是使用上述代码来实现的,例如containsKey(jey),就是使用get方法中的getNode()来判断的,由于篇幅原因就不一一介绍。

另外,中间有很部分不影响逻辑理解的代码被一笔带过,比如 红黑树的转化,查找,删除等操作,有兴趣的可以自己进行学习,不过还有一些其他的特性需要提醒一下

最后总结一下:

  • HashMap 底层数据结构在JDK1.7之前是由数组+链表组成的,1.8之后又加入了红黑树;链表长度小于8的时候,发生Hash冲突后会增加链表的长度,当链表长度大于8的时候,会先判读数组的容量,如果容量小于64会先扩容(原因是数组容量越小,越容易发生碰撞,因此当容量过小的时候,首先要考虑的是扩容),如果容量大于64,则会将链表转化成红黑树以提升效率
  • hashMap 的容量是2的n次幂,无论在初始化的时候传入的初始容量是多少,最终都会转化成2的n次幂,这样做的原因是为了在取模运算的时候可以使用&运算符,而不是%取余,可以极大的提上效率,同时也降低hash冲突
  • HashMap是非线程安全的,在多线程的操作下会存在异常情况(如形成闭环(1.7),1.8已修复闭环问题,但仍不安全),可以使用HashTable或者ConcurrentHashMap进行代替

看完文章如果还想了解更多关于Hashmap有关的知识,这里有准备了一期专门讲解Hashmap源码的视频: https://pan.baidu.com/s/1DZxu... 提取码: br53

免费获取更多安卓开发架构的资料(包括Fultter、高级UI、性能优化、架构师课程、 NDK、Kotlin、混合式开发(ReactNative+Weex)和一线互联网公司关于android面试的题目汇总可以加入 【安卓开发架构】


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

数据结构及应用算法教程

数据结构及应用算法教程

2011-5 / 45.00元

《数据结构及应用算法教程(修订版)》从数据类型的角度,分别讨论了四大类型的数据结构的逻辑特性、存储表示及其应用。此外,还专辟一章,以若干实例阐述以抽象数据类型为中心的程序设计方法。书中每一章后都配有适量的习题,以供读者复习提高之用。第1~9章还专门设有“解题指导与示例”一节内容,不仅给出答案,对大部分题目提供了详尽的解答注释;其中的一些算法题还给出了多种解法。书中主要算法和最后一章的实例中的全部程......一起来看看 《数据结构及应用算法教程》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

MD5 加密
MD5 加密

MD5 加密工具

html转js在线工具
html转js在线工具

html转js在线工具