Java源码分析 – HashMap常用方法和扩容算法

Java源码分析 – HashMap常用方法和扩容算法

前言

本文对HashMap(JDK1.8)的源码进行分析,包括以下几个部分:

  • 常用方法(put(), get(), containsKey(), containsValue(), remove())
  • 内部类(entrySet())
  • 底层基本数据结构以及扩容算法解析

什么是HashMap

HashMap是基于数组扩展实现的通过<K,V> 通过这种键值对映射的方式来存储数据的一种数据结构。因此它具有在O(1)时间查找元素的效率。

HashMap有几个基本概念:

  • Hash函数:也称为散列函数,可以把键映射为数组下标的函数。

  • K: 也就是Key,代表这个元素的键或者关键字。

  • V:也就是Value,代表要存储的数据,可以是基本数据类型,也可以是对象。

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

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

可以看到,HashMap继承自AbstrackMap,并且实现了 Map<K,V>, Cloneable, Serializable 这几个接口。

由于HashMap的源码(JDK 1.8)有2000多行,一次性把它看完有点难,所以我选择先从常用的方法入手,通过分析常用的方法,再扩展到方法里面涉及到的其他部分,这种形式来分析源码。

常见使用方式:

public class HashMapDemo {

    public static void main(String[] args) {
        Map<Integer, String> hashMap =new HashMap<>();

        hashMap.put(1, "BlueLzy1");  // 1
        hashMap.put(2, "Red");
        hashMap.put(3, "Yellow");

        System.out.println(hashMap.get(1));  // 2

        System.out.println(hashMap.containsKey(1));   // 3
        System.out.println(hashMap.containsValue("Red"));   // 4
        hashMap.remove(1);  // 5

        hashMap.forEach((k,v) -> System.out.println("key: " + k + "  value: " + v)); // 6

        hashMap.entrySet().forEach((k) -> System.out.println("key: " + k.getKey() + "  value: " + k.getValue())); // 7

    }
}

运行结果:

BlueLzy1
true
true
key: 2 value: Red
key: 3 value: Yellow
key: 2 value: Red
key: 3 value: Yellow

上面这段代码里面已经写了7个注释,分别代表HashMap里面7个不同的方法,我们一个个进入到源码里面看。

HashMap的构造方法

  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);
    }

    /**
     * 默认大小(16) 装载因子 (0.75).
     */
    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);
    }

HashMap有4个构造方法,我们可以看到这里出现了两个常量:

  • DEFAULT_LOAD_FACTOR : 默认装载因子 - 0.75
  • DEFAULT_INITIAL_CAPACITY: 默认容量 - 16

问题1:什么是装载因子?

问题2:tableSizeFor() 里面做了什么?

这两个问题都涉及到Hash算法以及位运算的知识,我们后面再讲。继续看put()方法。

1.HashMap的put()方法

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

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;   // 2
        if ((tab = table) == null || (n = tab.length) == 0)  // 3
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)  // 4
            tab[i] = newNode(hash, key, value, null);
        else {  // 5
            Node<K,V> e; K k;
            // 6
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 7
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            // 8
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        // 9
                        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 = e;
                }
            }
            // 10
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

1.我们调用的put() 方法,传入key和value,实际上是调用了putVal(),其中第一个参数就是hash值,通过hash(key) 方法计算出key对应的hash值。这个方法我们也是后面再说。

2. Node<K,V>[] tab 通过这个tab定义我们可以知道HashMap的底层数据结构是存储Node的数组,由于是数组,才会存在扩容方法,而Node的数据结构和之前我们分析过的LinkedList差不过,只是多了个hash变量,这里就不再分析了。

3.首先判断table是不是为空或者长度为0,是的话扩容,这个思想也是和ArrayList类似,使用的时候再进行扩容,初始化的时候只是空数组。

4.根据hash计算数组下标,如果这个位置没有值,那么直接插入

5.如果这个位置有值了,那么我们需要进行更进一步的判断

6.用e来保存当前找到的节点

7.判断是不是树节点,是的话放入到树中

8.否则的话就插入到链表中

9.判断是不是达到阈值了,是的话转化为红黑树

10.最后找到刚刚插入的节点,判断value是不是null,或者onlyIfAbsent为false,是的话就更新value

这个过程比较复杂,其中还有一些方法我们并不知道具体做了什么,后续再详细讲。包括:

问题3:红黑树节点的数据结构是怎么样的?

问题4:如何把链表转化为红黑树

问题5:putTreeVal() 方法做了什么?

由于在JDK1.8加入了红黑树这一层,因此整个HashMap的数据结构都变得比之前复杂,面试官也很喜欢问这个问题:HashMap在1.8和之前有什么区别?

如果按照我们上面的分析,我们应该可以说出这样的答案:

  • HashMap的底层数据结构是数组
  • 但是在发生散列冲突的时候会采用链表法,也就是相同hash的节点用链表的形式存储起来。
  • 如果这个链表达到一定的长度,那么则会转化为红黑树
  • 后续再插入的时候如果判断是树节点,那么调用putTreeVal() 方法放入到树中。

我们继续看get() 方法

2.HashMap的get()方法

    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        // 1
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            // 2
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                // 3
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                // 4
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

1.首先判断Node数组是不是为空,如果数组有数据,那么进入下一步

2.判断第一个节点的hash,key, value是不是我们get()方法要的值,是的话返回first

3.判断是不是树节点,是的话通过getTreeNode() 方法返回节点

4.如果不是树节点,那么循环链表直到找到key和value都相等的节点并返回。

问题6: 为什么 (first = tab[(n - 1) & hash]) ? 这样写有什么好处?

3-4.HashMap的containsKey()和containsValue()方法

首先来看containsKey() 方法:

    public boolean containsKey(Object key) {
        return getNode(hash(key), key) != null;
    }

其实就是调用上面说到的getNode() 方法,判断返回值是否为null,就知道HashMap有没有包括这个key了。

然后看看containsValue() 方法:

    public boolean containsValue(Object value) {
        Node<K,V>[] tab; V v;
        if ((tab = table) != null && size > 0) {
            for (int i = 0; i < tab.length; ++i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                    if ((v = e.value) == value ||
                        (value != null && value.equals(v)))
                        return true;
                }
            }
        }
        return false;
    }

通过遍历数组table,看是否存在value等于我们传入参数value的节点,有的话返回true,否则返回false。这个应该也挺好理解的。这里嵌套两个for循环,第一个是数组的遍历,第二个则是相同hash的链表遍历。

5.HashMap的remove()方法

如果上面put()方法大家都能理解的话,那么remove()方法应该也不难理解,因为它其实大部分逻辑是一样的,都是要找到属于这个key的位置,只不过put是要插入,而remove是找到之后移除。

    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 {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            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);
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

定义了一个node变量用来存放找到要删除的节点。

同样先是直接计算hash,判断这个位置是不是我们想要的,然后再判断树和链表上的节点。

找到节点之后就进行移除操作:

  • 如果是树节点,调用removeTreeNode()方法
  • 如果是直接找到的数组下标,那么修改为node.next
  • 如果是链表上的节点,那么调用p.next = node.next 修改指针地址完成移除操作

6.HashMap的entrySet()方法

public Set<Map.Entry<K,V>> entrySet() {
    Set<Map.Entry<K,V>> es;
    return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}

判断entrySet变量是不是null,是的话创建EntrySet() 对象

 final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
        public final int size()                 { return size; }
        public final void clear()               { HashMap.this.clear(); }
        public final Iterator<Map.Entry<K,V>> iterator() {
            return new EntryIterator();
        }
        public final boolean contains(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?,?> e = (Map.Entry<?,?>) o;
            Object key = e.getKey();
            Node<K,V> candidate = getNode(hash(key), key);
            return candidate != null && candidate.equals(e);
        }
        public final boolean remove(Object o) {
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>) o;
                Object key = e.getKey();
                Object value = e.getValue();
                return removeNode(hash(key), key, value, true, true) != null;
            }
            return false;
        }
        public final Spliterator<Map.Entry<K,V>> spliterator() {
            return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
        }
        public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
            Node<K,V>[] tab;
            if (action == null)
                throw new NullPointerException();
            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);
                }
                if (modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }
    }

EntrySet是HashMap的内部类,继承自AbstractSet,而且它的泛型是Map.Entry,也就是说,它持有的对象是key + value,在调用forEach()方法的时候就能看到,通过遍历数组,把Node当成参数传入到action.accept()中,因此我们可以直接使用到Node,也就可以直接拿到这个节点的key和value。

7.HashMap的forEach()方法

    @Override
    public void forEach(BiConsumer<? super K, ? super V> action) {
        Node<K,V>[] tab;
        if (action == null)
            throw new NullPointerException();
        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();
        }
    }

HashMap里面的forEach()方法其实和上面我们说到的EntrySet里面的forEach()方法是一模一样的!!

问题7:为什么需要EntrySet 这样一个内部类?

OK,到这里为止,HashMap常用的方法我们都过了一遍源码,了解了基本的流程,但是里面还有一些细节没用弄懂,主要是hash算法相关的东西,这部分因为内容比较多,我会单独写一篇来总结。

问题解答

问题1:什么是装载因子?

装载因子就是用来表示当然散列表中的空位还有多少。它的公式是:

装载因子 = 元素个数 / 散列表的长度

例如:如果我们用默认的构造函数来创建HashMap,那么此时的装载因子就是0.75,默认容量是16,因此阈值是0.75 *16 = 12,在上面put()方法中,我们在最后也会判断当前散列表的size是否大于阈值,是的话就会进行扩容。

那么这个装载因子有什么作用呢?

在上面分析过,HashMap采用的是链表法来解决散列冲突的,如果现在数组的空闲容量不多了,那么再插入新的元素就很容易发生散列碰撞,当链表越来越长的时候,查找的时间复杂度也会越来越大,慢慢退化成O(n),所以为了解决这个问题,我们才需要对数组进行扩容,而装载因子就是决定什么时候进行扩容的一个变量。

例如默认的容量是16,那么当容量达到12的时候,HashMap就会进行扩容。

问题2:tableSizeFor() 里面做了什么?

问题1提到了扩容,那么我们看看具体是怎么进行扩容的。

    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;
    }

第一次看到这段代码的时候我的一脸懵逼的,后面才慢慢理解了。我们用一个实际的例子来说明:

例如 cap = 20     二进制:0001 0100
n = cap - 1 = 19

n |= n >>> 1     二进制: 0001 0011 
                     或  0000 1010
                     =   0001 1011  (27)

n |= n >>> 2      二进制: 0001 1110
                      或  0000 0110
                      =   0001 1110 (30)

n |= n >>> 4      二进制: 0001 1110
                      或  0000 0001 
                      =   0001 1111  (31)

n |= n >>> 8      二进制: 0001 1111
                      或  0000 0000 
                      =   0001 1111  (31)

n |= n >>> 16      二进制: 0001 1111
                       或  0000 0000 
                       =   0001 1111  (31)

n = n + 1 = 32

我们输入20,扩容后会变成32,为什么要做这样的处理?

首先说一下为什么要在一开始的时候减一:

我们在上面分析源码的时候说过,初始化的容量必须是2的幂。如果现在已经是2的幂,例如16,我们再来执行一次这个过程,而且不减一:

例如 cap = 16     二进制:0001 0000
n = cap  // 这里不减一

n |= n >>> 1     二进制: 0001 0000 
                     或  0000 1000
                     =   0001 1000  (24)

n |= n >>> 2     二进制: 0001 1000 
                     或  0000 0110
                     =   0001 1110  (30)

n |= n >>> 4      二进制: 0001 1110 
                     或  0000 0001
                     =   0001 1111  (31)

n >>> 8 和 n >>> 16 省略

此时 n = n + 1 = 32

我们发现,如果本来就是2的幂,也就是传入16的时候,如果没有减一,返回的值是32!这很明显就不对了,因此一开始的减一就是为了保证这种情况下不会出现错误。

其次,由于int型在Java里面占用4个字节大小,也就是32位,最大值是32个1,如果移动32位那么就变成了0,这样是没有意义的。因此只要移动到16位就足够了。

通过这样一个算法,最终我们就能找到给定值的最小2次幂的值。真的是太巧妙了!

问题7:为什么需要有EntrySet这个内部类

我们发现在HashMap里面有很多种遍历的方式:

// 直接forEach
hashMap.forEach((k,v) -> System.out.println("key: " + k + "  value: " + v));

// 通过values()
hashMap.values().forEach((t) -> System.out.println(t));

// 通过KeySet
hashMap.keySet().forEach((t)-> System.out.println(t));

// 通过EntrySet
hashMap.entrySet().forEach((k) -> System.out.println("key: " + k.getKey() + "  value: " + k.getValue())); 

但是我们在上面也讲过,hashMap.forEach()其实内部也是调用了entrySet()getKey()getValue() 方法。

EntrySet最大的好处就是他的泛型类型是Map<Key, Value>,也就是说,通过EntrySet进行迭代的时候返回的对象是Map,我们能直接获取每个Map的Key和Value,而不是像其他方法一样,要么只能获取values,那么是keySet只有key。

注意,如果我们通过entrySet的迭代器来修改添加或者删除的元素,那么Map也会受到影响

 public static void main(String[] args) {
        Map<Integer, String> hashMap =new HashMap<>();

        hashMap.put(1, "BlueLzy1");  // 1
        hashMap.put(2, "Red");
        hashMap.put(3, "Yellow");
        hashMap.put(1, "test"); 
        while (hashMap.entrySet().iterator().hasNext()) {
            Map.Entry<Integer, String> ite =          hashMap.entrySet().iterator().next();
            hashMap.remove(ite.getKey());
            System.out.println("remove: " + ite.getKey());
        }

        hashMap.forEach((k,v) -> System.out.println("key: " + k + "  value: " + v)); 

}

输出结果:

remove: 1
remove: 2
remove: 3

说明迭代器移除了元素之后,Map也同样remove掉了。

问题4-问题6

关于hash算法以及红黑树的部分我会在另外一篇文章里单独写,因为这部分内容也挺多的,要讲清楚需要较长的篇幅。

  • hash算法底层是怎么实现的?
  • 如果发生了哈希碰撞要怎么解决?
  • 有没有降低碰撞几率,提高散列表效率的方法?
  • 红黑树是什么样的数据结构?它有什么特点?
  • 为什么链表过长会选择转化为红黑树?

 
 
 

本文以创作共用版权协议发布,转载本文要求遵循“署名-非商业性使用-相同方式共享3.0”的创作共用协议,并以链接形式指明本文地址。

本文链接地址:https://www.bluelzy.top/java-foundation-linkedlist/

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注