HashMap_get方法实现解析

「爱情、让人受尽委屈。」 2023-03-14 10:57 15阅读 0赞

### 1 get() ###

/** * Returns the value to which the specified key is mapped, * or {@code null} if this map contains no mapping for the key. * * <p>More formally, if this map contains a mapping from a key * {@code k} to a value {@code v} such that {@code (key==null ? k==null : * key.equals(k))}, then this method returns {@code v}; otherwise * it returns {@code null}. (There can be at most one such mapping.) * * <p>A return value of {@code null} does not <i>necessarily</i> * indicate that the map contains no mapping for the key; it's also * possible that the map explicitly maps the key to {@code null}. * The {@link #containsKey containsKey} operation may be used to * distinguish these two cases. * * @see #put(Object, Object) */
        public V get(Object key) { 
            Node<K,V> e;
    		
    		// hash(key) 获取key的hash
    		// e = getNode(hash(key), key) 通过筒的hash和key获取节点
    		// 返回节点的值
            return (e = getNode(hash(key), key)) == null ? null : e.value;
        }
    
        /** * Implements Map.get and related methods. * * @param hash hash for key * @param key the key * @return the node, or null if none */
        final Node<K,V> getNode(int hash, Object key) { 
    
    		// tab 数组加链表
    		// first 链表（第一个节点）
    		// e 链表
    		// n 数组总长度
    		// k 节点的键
            Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    
    		// tab = table 获取数组加链表
    		// n = tab.length 获取数组的长度（筒的数量）
    		// (n - 1) & hash 当前筒的定位下标
    		// first = tab[(n - 1) & hash] 获取链表（第一个节点）
    		// 如果数组加链表不为空并且当前筒不为空
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) { 
    
    			// k = first.key 获取节点的key
    			// 若如果筒存在，并且，节点存在
                if (first.hash == hash && // always check first node
                    ((k = first.key) == key || (key != null && key.equals(k))))
                    // 返回
                    return first;
    
    			// e = first.next 获取下一个节点
    			// 如果下一个节点不为空
                if ((e = first.next) != null) { 
    
    				// 如果当前节点类型是或黑树节点
                    if (first instanceof TreeNode)
                    	// (TreeNode<K,V>)first 转化当前链表为红黑树
                    	// 在树中获取指定节点，并且，返回
                        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
    
    				// 如果下一个节点类型不是红黑树节点（链表节点）
                    do { 
    
    					// k = e.key 获取下一个节点的key
    					// 如果当前节点筒一致，并且key一致
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            // 返回节点
                            return e;
    
    				// e = e.next 获取当前节点的下一个节点
    				// 如果下一个节点不为空，执行do
                    } while ((e = e.next) != null);
                }
            }
            // 返回空
            return null;
        }

### 2 getTreeNode() ###

/** * Calls find for root node. */
            final TreeNode<K,V> getTreeNode(int h, Object k) { 
    
    			// root() 获取根节点
    			// find() 从红黑树中获取指定hash和key的树节点
    			// 从根节点或当前红黑树，获取指定节点，并返回
                return ((parent != null) ? root() : this).find(h, k, null);
            }
            
            /** * Returns root of tree containing this node. */
            final TreeNode<K,V> root() { 
    
    			// 获取当前节点
                for (TreeNode<K,V> r = this, p;;) { 
    
    				// p = r.parent 获取当前节点的父节点
    				// 如果父节点不存在
                    if ((p = r.parent) == null)
                    	// 返回当前节点
                        return r;
    
    				// 如果父节点存在，赋值父节点为当前节点
                    r = p;
                }
            }
            
            /** * Finds the node starting at root p with the given hash and key. * The kc argument caches comparableClassFor(key) upon first use * comparing keys. */
            final TreeNode<K,V> find(int h, Object k, Class<?> kc) { 
    
    			// 获取树（当前节点）
                TreeNode<K,V> p = this;
                do { 
    
    				// ph 当前节点的hash
    				// dir 树的所有层级？当前节点的层级位置？
    				// pk 当前节点的键
    				// pl 当前节点的（左子树）左节点
    				// pr 当前节点的（右子树）右节点
    				// q 临时节点
                    int ph, dir; K pk;
                    TreeNode<K,V> pl = p.left, pr = p.right, q;
                    
    				// ph = p.hash 获取当前节点的hash
    				// 如果当前节点的hash大于查找节点的hash值
    				if ((ph = p.hash) > h)
    					// 将左节点设置为当前节点，即，小的方向查找
                        p = pl;
    
    				// 如果当前节点的hash小于查找节点的hash值
                    else if (ph < h)
                    	// 将右节点设置为当前节点，即，大的方向查找
                        p = pr;
    
    				// pk = p.key 获取节点的key
    				// 如果节点的key匹配
                    else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                    	// 返回该节点
                        return p;
                    
                    // 如果hash相等，key不匹配，左节点为空
                    else if (pl == null)
                    	// 获取右节点
                        p = pr;
    
    				// 如果hash相等，key不匹配，右节点为空
                    else if (pr == null)
                    	// 获取左节点
                        p = pl;
    
    				// kc = comparableClassFor(k) 获取键的类型
    				// dir = compareComparables(kc, k, pk) 校验键的类型，返回校验结果，
    				// 如果键的类型存在，并且，匹配当前节点
                    else if ((kc != null ||
                              (kc = comparableClassFor(k)) != null) &&
                             (dir = compareComparables(kc, k, pk)) != 0)
                        // 如果键的类型xxx,获取左节点，获取右节点；
                        p = (dir < 0) ? pl : pr;
                    
                    // q = pr.find(h, k, kc) 获节点
                    // 如果节点不为空
                    else if ((q = pr.find(h, k, kc)) != null)
                    	// 返回节点
                        return q;
    
    				// 赋值左子节点为当前节点
                    else
                        p = pl;
    
    			// 继续遍历下一个节点
                } while (p != null);
    
    			// 没有获取到节点返回null
                return null;
            }