HashMap源码解析（体系化总结）持续更新

Java集合继承关系

典型集合源码阅读

HashTable

继承Dictionary类，实现Map类
使用Syncronize实现线程安全，读写都做
数组+单向链表存储
key的寻址算法：(hash & 0x7FFFFFFF) % tab.length; 32位
containsValue：两层遍历，外层遍历数组，内层单向遍历链表，equals比对值
containsKey：先用key.hashcode计算所在数组位置，然后遍历链表，比对entry.hash值以及key.equals
最大存储量：MAX_ARRAY_SIZE（Integer.MAX_VALUE - 8）+1
rehash：当前容量>=threshhold时，对hashtable扩容，然后就需要对之前的元素重新hash存入新table，

扩容容量int newCapacity = (oldCapacity << 1) + 1;
remove：链表移除指定节点，1、首节点；2、中间节点
- 扩展到算法场景：去除链表的指定节点
keySet（），entrySet（），使用Collections.synchronizedSet
values（）：Collections.synchronizedCollection

HashMap

实现Map接口，继承AbstractMap
最大容量2^29次方
getNode方法（元素查找）

/**
  * Implements Map.get and related methods
  * 接口方法Map.get的具体实现
  * @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) {
    // https://blog.****.net/weixin_42340670/article/details/80779699
    // 声明节点数组对象（就是该HashMap），首节点，遍历的当前节点，数组长度，节点的键对象
    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) {
        // 首先比对首节点，如果首节点的hash值和key的hash值相同 并且 首节点的键对象和key相同（地址相同或equals相等），则返回该节点
        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);
        }
    }
    // 如果没有遍历到指定节点，就返回null
    return null;
}

resize是HashMap的扩容函数，当容量利用在容量*负载因子（默认16*0.75）进行扩容，之前的两倍。
HashMap是采用桶+链表，1.8开始，使用桶+链表+红黑树的形式。
当链表的长度大于8时，就会将之前的链表转成红黑树存储，查找的时间复杂度由O(N)变换成O(logN)
链表插入采用头插法，高效插入。这也是相同key，后插入的会覆盖前插入的原因。
查找分两步：查找需要分成两步进行：
- 计算键值对所在的桶；
- 在链表上顺序查找，时间复杂度显然和链表的长度成正比

HashMap源码解析（体系化总结）持续更新

Java集合继承关系

典型集合源码阅读

HashTable

HashMap

相关推荐