HashMap的put和get数据流程揭秘

╰半橙微兮° 2022-01-12 06:37 204阅读 0赞

本文是针对JDK1.8中的HashMap，之前以为已经懂的不错了，结果发现很多关键点没明白

**1. 先说HashMap的数据结构**

核心数据结构就三个：**数组，链表，Tree**

*  数组Node<K,V> table  
    数据就是个简单的Node数组，存放的是当前索引应第一个Node<K,V>对节点，或者是空（说明没有存放数据）
 *  链表  
    如果挂在同一个索引下的数据Node个数小于变Tree阈值（默认是8个），那么将以数组中的元素为头节点，依次挂成一个链表
 *  Tree  
    如果这个个数超过了变Tree阈值，将把key的hash()结果变成value，建立红黑树

**2. 关键点**

*  K V对进来时怎么找到放到table中的位置？  
    K V对进来时，放到数组中的位置是根据K的hashcode和当前数组的容量计算出来的一个索引值，这种计算方式是HashMap放置数据的核心。

计算在数组中的位置主要方式是：  
首先，计算出K的hashcode，如果是String的话，那就是直接拿的Object的Native方法；  
然后，取这个hashcode的高16位和低16位做作疑惑，得到一个hash值，为啥要这么做呢？源码中解释是有助于减少冲突；

就是这样计算的hash值：
    	static final int hash(Object key) {
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }

最后，**把hash与容量建议相与，即 index = (n - 1) & hash**

这个index 就是新进来的K V对应该放的位置。

插播：
    对象的hash算法和equal是存在一定关系的，不是随便写个hash算法和equal方法就可以了
    对于同一个对象：
    1. 相同对象，多次hashcode得到的int型数字应该是一样的；
    2. 如果两个对象equal，那这两个对象的hashcode必须一样；
    3. 两个对象不equal，不一定hashcode不一样

**所以HashMap中如果Key是自定义对象的话，一定要重新hashcode方法和equal方法，不然本来相同的会拿到不同的hashcode，用equal时也会判断不相等。**

**3. get取数据**

核心的核心是根据Key值找到数组中对应的index，当时找index的方法就是**2**中所说的

了解到数据结构和运行原理后，相信基本能猜到HashMap里面是怎么个逻辑了

1.  找到数组中的index，其实就是如果这个key有数据，那它会在数组中哪个开头的链表或者树上。
2.  如果这个index上的头为空，那就是没有；如果只有一个头，但和它和key不相等，那也没有；如果不止一个头，说明是链表或者树，根据first instanceof TreeNode来判断是不是树；
3.  剩下的就是如果是链表就链表找，如果是树就树找，判断找到的条件是，地址一样或者equal

源码中关键方法是:

get(Object key);
    get(int hash, Object key);
    
        // 这个方法就是个入口，顶多是计算了从哪找
        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) {
                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;
        }

**4. put数据**

put数据就比get要复杂些，但也没什么太神奇的，相信如果自己去实现，逻辑也是基本类似的。

首先，肯定是找Key放的位置，就是计算index，及数组中第一个元素；  
然后，如果这个位置为空，那new 一个就可以了；如果这个位置的头结点是TreeNode呢，那它肯定已经变树了，那按树的方式放数据；如果不是呢，那就按链表的方式，放到链表最后面，为啥不放到头节点后面呢？因为放完之后还要看要不要把链表变树，肯定要遍历一遍，所以应该这样就直接放到尾节点了。如果达到了变树的阈值，肯定就要变树了。  
最后，上面其实做的是放位置，放完位置还有检查下是不是该扩容了，如果要扩容就麻烦点了，需要resize。

扩容的几个关键点在于：

1.  数组table扩成两倍大小；
2.  扩容之后node的位置，要么是在原有的index上，要么在原有数组大小+index的位置，就这两种可能。
3.  扩容的过程中首先造一个两倍的数组，然后遍历老的数组，对于每一个头节点的要么是单个数据，要是是链表，要么是树。单个数据的简单，链表和树的就会把原有的数据拆分两部分，一部分放到index位置，一部分放到数组大小+index位置

// 这个是常看到的，对我的，在这里计算了hash
         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)      // index上啥也没有，直接加
                    tab[i] = newNode(hash, key, value, null);
                else {
                    Node<K,V> e; K k;
                    if (p.hash == hash &&
                        ((k = p.key) == key || (key != null && key.equals(k))))
                        e = p;
                    else if (p instanceof 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;
                            }
                            if (e.hash == hash &&
                                ((k = e.key) == key || (key != null && key.equals(k))))
                                break;
                            p = e;
                        }
                    }
                    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;
            }

resize自己看罗

**关键还要看源码，要思考这玩意就应该我自己来写，怎么实现**