【Java容器源码】HashMap（四）获取 value 及迭代器源码分析

古城微笑少年丶 2022-10-31 00:47 182阅读 0赞

> HashMap 系列：
> 
>  *  [【Java容器源码】HashMap（一）底层结构分析][Java_HashMap]
>  *  [【Java容器源码】HashMap（二）添加元素及树化源码分析][Java_HashMap 1]
>  *  [【Java容器源码】HashMap（三）扩容源码分析][Java_HashMap 2]
>  *  [【Java容器源码】HashMap（四）获取 value 及迭代器源码分析][Java_HashMap 2]
>  *  [【Java容器源码】HashMap（五）源码分析&死锁问题（JDK7）][Java_HashMap_JDK7]
>  *  [【Java容器源码】关于HashMap的几个问题][Java_HashMap 3]

## 1.从Hash表中获取元素 ##

### get() ###

计算hash，并调用getNode

public V get(Object key) {
        
                Node<K,V> e;
            	// 如果是null直接返回null
                return (e = getNode(hash(key), key)) == null ? null : e.value;
        }

### getNode() ###

getNode() 大致流程如下：

1.  根据hash值定位数组的索引位置
2.  equals 判断当前节点是否是我们需要寻找的 key
    
     *  是的话直接返回
     *  不是则判断当前节点有无 next 节点，有的话判断是链表类型，还是红黑树类型。
3.  分别走链表和红黑树不同类型的查找方法

// 传入的hash值用于确定哈系桶，key用于确定具体节点
    final Node<K,V> getNode(int hash, Object key) {
        
            Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
            // 数组不为空 && hash算出来的索引下标有值，
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) {
        
                // hash 和 key 的 hash 相等，直接返回
                if (first.hash == hash &&
                    ((k = first.key) == key || (key != null && key.equals(k))))
                    return first;
                // hash不等，看看当前节点的 next 是否有值
                if ((e = first.next) != null) {
        
                    // 使用红黑树的查找
                    if (first instanceof TreeNode)
                        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                    // 采用自旋方式从链表中查找 key，e 为链表的头节点
                    do {
        
                        // 如果当前节点 hash == key 的 hash，并且 equals 相等，当前节点就是我们要找的节点
                        // 先比较hash效率高，因为hash一定是数字，key可能是包装类可能是自定义对象
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            return e;
                        // 否则，把当前节点的下一个节点拿出来继续寻找
                    } while ((e = e.next) != null);
                }
            }
            return null;
        }

### getTreeNode() ###

返回红黑树的根节点

final TreeNode<K,V> getTreeNode(int h, Object k) {
        
    		 // root() 是通过循环寻找树的根节点
             return ((parent != null) ? root() : this).find(h, k, null);
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center]

find() 红黑树寻找指定节点

1.  从根节点递归查找；
2.  根据 hashcode，比较查找节点，左边节点，右边节点之间的大小，根本红黑树左小右大的特性进行判断；
3.  判断查找节点在第 2 步有无定位节点位置，有的话返回，没有的话重复 2，3 两步；
4.  一直自旋到定位到节点位置为止。

final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
        
    			// this 就是根节点
                TreeNode<K,V> p = this;
                do {
        
                    int ph, dir; K pk;
                    TreeNode<K,V> pl = p.left, pr = p.right, q;
                    if ((ph = p.hash) > h)
                        p = pl;
                    else if (ph < h)
                        p = pr;
                    else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                        return p;
                    else if (pl == null)
                        p = pr;
                    else if (pr == null)
                        p = pl;
                    else if ((kc != null ||
                              (kc = comparableClassFor(k)) != null) &&
                             (dir = compareComparables(kc, k, pk)) != 0)
                        p = (dir < 0) ? pl : pr;
                    else if ((q = pr.find(h, k, kc)) != null)
                        return q;
                    else
                        p = pl;
                } while (p != null);
                return null;
            }

## 2.迭代器 ##

Map 对 key、value 和 entity（节点） 都提供了迭代器。这些迭代器都是通过map.~Set().iterator()进行调用

*  迭代key：HashMap\#keySet()–> KeySet\#iterator()–> KeyIterator
 *  迭代value：HashMap\#values()–> Values\#iterator()–> ValueIterator
 *  迭代key：HashMap\#entrySet()–> EntrySet\#iterator()–> EntryIterator

虽然是不同的迭代器，但是它们本质上却没有区别：

1.  都继承了HashIterator
2.  都只有一个方法：next()，而且里面调用的都是 HashIterator.nextNode()，只不过最后在node中取值不同

final class KeyIterator extends HashIterator
        implements Iterator<K> {
        
        public final K next() {
         return nextNode().key; } // 调用父类的nextNode方法，返回node的key
    }
    
    final class ValueIterator extends HashIterator
        implements Iterator<V> {
        
        public final V next() {
         return nextNode().value; } // 调用父类的nextNode方法，返回node的value
    }
    
    final class EntryIterator extends HashIterator
        implements Iterator<Map.Entry<K,V>> {
        
        public final Map.Entry<K,V> next() {
         return nextNode(); }  // 调用父类的nextNode方法，返回node
    }

### HashIterator ###

abstract class HashIterator {
        
                Node<K,V> next;        // next entry to return
                Node<K,V> current;     // current entry
                int expectedModCount;  // for fast-fail
                int index;             // current slot
        
                HashIterator() {
        
                    expectedModCount = modCount;
                    Node<K,V>[] t = table;
                    current = next = null;
                    index = 0;
                    if (t != null && size > 0) {
         // advance to first entry
                        do {
        } while (index < t.length && (next = t[index++]) == null);
                    }
                }
        	//......
            }

### hasNext() ###

判断当前node在桶中是否有下一个node

public final boolean hasNext() {
        
            return next != null;
        }

### nextNode() ###

获取当前节点的下一个node。

*  整体的迭代策略是逐个桶遍历，可理解成外层是遍历数组，内层是遍历链表（红黑树）
 *  该方法屏蔽了node处于不同桶所带来的差异，就好像所有元素在一个桶中。

final Node<K,V> nextNode() {
        
        Node<K,V>[] t;
        // 记录next结点
        Node<K,V> e = next; 
        // 若在遍历时对HashMap进行结构性的修改则会抛出异常
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        // 下一个结点为空，抛出异常
        if (e == null)
            throw new NoSuchElementException();
            
        // 如果下一个结点为空 && table不为空，表示当前桶中所有结点已经遍历完
        // 注：核心！！！实现了跨桶遍历
        if ((next = (current = e).next) == null && (t = table) != null) {
        
            // 寻找下一个不为空的桶：未到最后一个槽点 && 下一个槽点不为空
            do {
        } while (index < t.length && (next = t[index++]) == null);
        }
        return e;
    }

### remove() ###

删除刚遍历过的 node

public final void remove() {
        
            Node<K,V> p = current;
            // 当前结点为空，抛出异常
            if (p == null)
                throw new IllegalStateException();
            // 若在遍历时对HashMap进行结构性的修改则会抛出异常
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            // 若在遍历时对HashMap进行结构性的修改则会抛出异常
            current = null;
            K key = p.key;
            // 移除结点
            removeNode(hash(key), key, null, false, false);
            // 赋最新值
            expectedModCount = modCount;
        }

[Java_HashMap]: https://blog.csdn.net/weixin_43935927/article/details/108501752
[Java_HashMap 1]: https://blog.csdn.net/weixin_43935927/article/details/113884949
[Java_HashMap 2]: https://blog.csdn.net/weixin_43935927/article/details/113886585
[Java_HashMap_JDK7]: https://blog.csdn.net/weixin_43935927/article/details/108502329
[Java_HashMap 3]: https://blog.csdn.net/weixin_43935927/article/details/108733304
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/c4d760e822734530945b9ad658e44801.png