HashMap源码分析

HashMap的结构图

HashMap原理介绍

数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，当然，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)

线性链表：对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为O(n)

二叉树：对一棵相对平衡的有序二叉树，对其进行插入，查找，删除等操作，平均复杂度均为O(logn)。

哈希表：相比上述几种数据结构，在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)，接下来我们就来看看哈希表是如何实现达到惊艳的常数阶O(1)的，哈希表就是数组和链表组成的。

HashMap 是数组 + 链表 + 红黑树（JDK1.8 中新增的红黑树部分）实现的

HashMap的数据结构

链表

Node是HashMap的一个内部类，实现了Map.Entry接口，本质上是一个映射（键值对）

 static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;//存储hash值，用来定位数组索引位置
        final K key;//存储key值
        V value;//存储key值对应的value值
        Node<K,V> next;//指向下一节点的指针

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }
		//hash值为key的hash值的value的hash值的按位异或
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)//如果o为当前对象
                return true;
            if (o instanceof Map.Entry) {//o为Map.Entry的类型或其子类
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))//判断key和value是否完全相等
                    return true;
            }
            return false;
        }
    }

红黑树

下面只给处红黑树一部分代码。红黑树比链表多了四个变量，parent父节点、left左节点、right右节点、prev上一个同级节点。

//红黑树
static final class TreeNode<k,v> extends LinkedHashMap.Entry<k,v> {
    TreeNode<k,v> parent;  // 父节点
    TreeNode<k,v> left; //左子树
    TreeNode<k,v> right;//右子树
    TreeNode<k,v> prev;    // needed to unlink next upon deletion//删除后需要取消下一步链接
    boolean red;    //颜色属性
    TreeNode(int hash, K key, V val, Node<k,v> next) {
        super(hash, key, val, next);
    }
 
    //返回当前节点的根节点
    final TreeNode<k,v> root() {
        for (TreeNode<k,v> r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }
}

位桶

HashMap类中有一个非常重要的字段，就是 Node[] table，即哈希桶数组，明显它是一个Node的数组

transient Node<k,v>[] table;//存储（位桶）的数组

HashMap的底层实现

 首先有一个每个元素都是链表的数组，当添加一个元素（key-value）时，就首先计算元素key的hash值，以此确定插入数组中的位置，但是可能存在同一hash值的元素已经被放在数组同一位置了，这时就添加到同一hash值的元素的后面，他们在数组的同一位置，但是形成了链表，所以说数组存放的是链表。而当链表长度太长时，链表就转换为红黑树，这样大大提高了查找的效率。

HashMap的静态实用程序

//得到key的hash值
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
//如果x的类的形式为“Class C implements Compariable<C>”，则返回x的类，否则返回null
 static Class<?> comparableClassFor(Object x) {
        if (x instanceof Comparable) {  // 判断是否实现了Comparable接口
            Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
            if ((c = x.getClass()) == String.class) 
                return c;   // 如果是String类型，直接返回String.class
            if ((ts = c.getGenericInterfaces()) != null) {  // 判断是否有直接实现的接口
                for (int i = 0; i < ts.length; ++i) {   // 遍历直接实现的接口
                    if (((t = ts[i]) instanceof ParameterizedType) &&   // 该接口实现了泛型
                        ((p = (ParameterizedType)t).getRawType() == // 获取接口不带参数部分的类型对象
                         Comparable.class) &&   //  该类型是Comparable
                        (as = p.getActualTypeArguments()) != null &&    // 获取泛型参数数组
                        as.length == 1 && as[0] == c)   // 只有一个泛型参数，且该实现类型是该类型本身
                        return c;   // 返回该类型
                }
            }
        }
        return null;
    }

HashMap的参数

	// 序列号
    private static final long serialVersionUID = 362498820763181265L;    
    // 默认的初始容量是16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   
    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30; 
    // 默认的填充因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 当链表中的元素个数超过8，并且Node[] table数组长度没有超过MIN_TREEIFY_CAPACITY的值64时，进行数组扩容，否则链表结构转化成红黑树结构，进行结构优化
    static final int TREEIFY_THRESHOLD = 8; 
    // 当桶(bucket)上的结点数小于这个值时树转链表
    static final int UNTREEIFY_THRESHOLD = 6;
    // 桶中结构转化为红黑树对应的table的最小大小
    static final int MIN_TREEIFY_CAPACITY = 64;
    // 存储元素的数组，总是2的幂次倍
    transient Node<k,v>[] table; 
    // 存放具体元素的集
    transient Set<map.entry<k,v>> entrySet;
    // size 是 HashMap 中实际存在的键值对的数量
    transient int size;
    // 每次扩容和更改map结构的计数器
    transient int modCount;   
    // threshold 是 HashMap 所能容纳的最大的键值对的个数。临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容，扩容为原来两倍
    int threshold;
    // 填充因子
    final float loadFactor;

HashMap的构造函数