转载

HashMap剖析之put()和get()方法

前言

本文是基于 Java 8HashMap 进行分析,主要是分析 HashMap 中的 put()get() 方法。

下面将会分析这部分的源码,如果觉得源码分析内容太啰嗦,可以跳过源码部分,直接看源码下面的总结。

put()方法源码分析

HashMapput() 方法是我们最常用的方法,但是 put() 方法是怎么工作的呢?

put()方法

/**
     * HashMap的put()方法支持key/value为null
     */
    public V put(K key, V value) {
        //实际上是先调用HashMap的hash()方法获取到key的hash值
        //然后调用HashMap的putVal()方法
        return putVal(hash(key), key, value, false, true);
    }

put() 方法实际上是

  1. 调用 hash() 方法获取到 keyhash
  2. 调用 putVal() 方法存储 key-value

核心方法是 putVal() 方法,下面我会先分析一下 hash() 方法,因为这个方法涉及到 hash 值这个关键属性的计算。

hash()方法

static final int hash(Object key) {
        int h;
        // key为null时,hash值为0
        // key不为null时,调用key对象的hashCode()方法并通过位运算异或和无符号右移将高位分散到低位
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
  1. hash() 方法指定了 nullhash 值为 0 。这样就可以支持 keynull
  2. (h = key.hashCode()) ^ (h >>> 16) 这段代码通过位运算异或和无符号右移将高位分散到低位,这样做可以减少哈希碰撞的概率(这块不是很清楚原理,是从方法注释上了解到的)

putVal()方法

/**
     * Map.put()方法的实际实现
     *
     * @param hash key的hash值
     * @param key 键值对中的key
     * @param value 键值对中的value
     * @param onlyIfAbsent 如果为true,则键值对中的值已经存在则不修改这个值
     * @param evict 如果为false,则是处于创建模式
     * @return 上一次的value,如果上一次的value不存在,则为null
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        //tab用于暂存散列表table。p为散列表中对应索引的链表的头节点的指针。n存储tab的长度。i则为命中的散列表的索引
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //给tab和n赋值
        //当tab为null或者tab的长度n为0时,触发resize()来初始化tab
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //使用(n - 1) & hash(等价于hash%n)计算命中的散列表索引,同时判断散列表对应索引的链表是否存在
        if ((p = tab[i = (n - 1) & hash]) == null)
            //散列表对应索引的链表不存在则创建一个新的链表
            tab[i] = newNode(hash, key, value, null);
        else {//散列表对应索引的链表已存在
            Node<K,V> e; K k;
            // 判断头节点的hash值和key是否与入参的hash值和key一致。需要注意,null的hash值为0
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                // 对应的键值对已经存在,记录下来
                e = p;
            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) {//遍历到尾节点
                        //尾插法添加一个新的节点
                        p.next = newNode(hash, key, value, null);
                        //链表长度大于阈值
                        if (binCount >= TREEIFY_THRESHOLD - 1) // 从-1开始,所以为阈值-1 
                            // 将链表转化为红黑树
                            treeifyBin(tab, hash);
                        // 中断循环
                        break;
                    }
                    // 判断当前遍历的节点的hash值和key是否与入参的hash值和key一致,即key是否已经存在
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        // key已经存在,中断循环
                        break;
                    // 记录当前遍历的节点
                    p = e;
                }
            }
            if (e != null) { // Map中存在重复的key
                V oldValue = e.value;//记录下旧值
                if (!onlyIfAbsent || oldValue == null)//判断值存在是否可以进行修改以及旧值是否为null
                    e.value = value;//修改该节点的值
                afterNodeAccess(e);// 链表节点的回调方法,此处为空方法
                return oldValue;//返回旧值
            }
        }
        // HashMap发生结构变化,变化次数累加
        ++modCount;
        // 键值对个数自增,同时判断是否达到扩容的阈值
        if (++size > threshold)
            resize();
        // 链表节点的回调方法,此处为空方法
        afterNodeInsertion(evict);
        // 此处返回null是因为链表新增了节点,所以上一次的值必然为null
        return null;
    }

putVal() 方法的关键点:

  1. table 没有初始化则调用 reszie() 方法初始化。
  2. 计算命中的散列表索引位置,公式为 (n - 1) & hash (等价于 hash%n )。其中 n 为散列表长度, hash 为插入的键值对的 key 的哈希值。
  3. 判断散列表对应索引中的首节点是否为 null ,若为 null ,则创建链表,否则进入下一步。
  4. 判断该首节点是否与插入的键值对的 keyhash 一致,若一致则替换该节点的值为 value ,否则进入下一步
  5. 判断首节点是否为树节点,若是则调用树节点的 putTreeVal() 方法遍历红黑树,否则遍历链表。
  6. 遍历红黑树时,若存在 keyhash 相同的节点就替换对应节点的值 value ,若不存在则插入新的树节点。
  7. 遍历链表时,若存在 keyhash 相同的节点就替换对应节点的值为 value 。若找不到 keyhash 相同的节点,则链表尾部插入节点,同时进入下一步。
  8. 若当前链表长度大于或等于树化阈值 TREEIFY_THRESHOLD(8) 时,则将链表转化为红黑树。

get()方法源码分析

除了 HashMapput() 方法外, get() 方法也是一个我们常用的方法,下面开始分析其关键的源码。

get()方法

/**
 * 返回key对应的value,如果不存在则返回null
 */
public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

get() 方法实际上是

  1. 调用 hash() 方法获取到 keyhash
  2. 调用 getNode() 方法通过 keyhash 获取对应的 value ,不存在则返回 null

核心方法是 getNode() 方法,下面我会先分析一下 getNode() 方法。

getNode()方法

/**
     * Map.get()方法的实际实现
     * @param hash key的哈希值
     * @param key 查询用的key
     * @return 节点或者是节点不存在是返回null
     */
    final Node<K,V> getNode(int hash, Object key) {
        //tab用于暂存散列表table。first为散列表中对应索引的链表的头节点的指针。n存储tab的长度。i则为命中的散列表的索引
        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) {
            if (first.hash == hash && 
                ((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);
            }
        }
        //不存在对应的key,返回null
        return null;
    }

getNode() 方法的关键点:

  1. 若散列表 table 不为 null长度 大于 0 且其索引为 (n - 1) & hash (等价于 hash%n )的节点不为 null 。其中 n 为散列表长度, hash 为插入的键值对的 key 的哈希值。则进入下一步,否则直接返回 null
  2. 判断首节点的 keyhash 是否与入参一致,若相同则返回首节点,否则进入下一步。
  3. 判断节点个数只有 1 个,若是则返回 null ,否则进入下一步
  4. 判断首节点是否为树节点,若是则遍历红黑树,否则为链表,进入下一步
  5. 遍历链表,检索 keyhash 与入参相同的节点,若找到则返回该节点,否则返回 null

总结

put()get() 方法是 HashMap 的常用方法,通过学习其源码了解到 HashMap 是如何使用 拉链法 解决哈希冲突。而下面将会通过两幅图展示 put()get() 的执行过程:

  1. put() 方法图解
    HashMap剖析之put()和get()方法
  2. get() 方法图解
    HashMap剖析之put()和get()方法
原文  https://segmentfault.com/a/1190000018156976
正文到此结束
Loading...