HashMap 底层实现原理

要了解HashMap的底层实现原理，我们首先要对HashMap的部分底层源码进行分析

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

我们可以看出HashMap继承了AbstractMap，实现了Map，Cloneable，Serializable接口。

 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

HashMap的默认初始容量（必须是2的幂），它的值是1左移4位，也就是16

static final int MAXIMUM_CAPACITY = 1 << 30;

HashMap的最大容量，如果任何一个带参数的构造函数指定了较大的值，就会使用它来比较，而且值必须是2的幂，并且小于1左移30位，2的30次方，也就是

 static final float DEFAULT_LOAD_FACTOR = 0.75f;

HashMap默认的加载因子，因为从上可知，HashMap的默认初始容量是16，当HashMap的实际容量达到16*0.75，就是12，HashMap会自动扩容。

 static final int TREEIFY_THRESHOLD = 8;

HashMap底层链表转换成红黑树的临界值，当链表的长度大于8时，会自动转化成红黑树。

static final int UNTREEIFY_THRESHOLD = 6;

HashMap底层红黑树转化成链表的临界值，当红黑树的长度小于6时，红黑树又会自动转换成链表。

static final int MIN_TREEIFY_CAPACITY = 64;

HashMap转化成树结构的最小容量，因为HashMap底层时数组+链表+红黑树实现的，HashMap的容量大于64时，会自动转换成树结构，也就是数组的长度大于64时，也会转换成红黑树。

以下是HashMap的静态内部类

static class Node<K,V> implements Map.Entry<K,V> { final int hash;//若放入的节点key的hash值(若key所在的类未进行重写hash()方法的重写，则为Object的hash()方法) 定义数组索引的位置 final K key;//放入节点的key V value;//放入节点的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; } 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) return true; if (o instanceof Map.Entry) { // 判断key和value是否都相等 Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) // 如果key和value都相等，就返回true return true; } // 如果key或者value不相等，就返回false return false; } } 

继续往下看

static final int hash(Object key) { // 计算key的hash值 int h; // 1.先拿到key的hashCode值; 2.将hashCode的高16位参与运算 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } 

static Class<?> comparableClassFor(Object x) { // 1.判断x是否实现了Comparable接口 if (x instanceof Comparable) { Class<?> c; Type[] ts, as; Type t; ParameterizedType p; // 2.校验x是否为String类型 if ((c = x.getClass()) == String.class) // bypass checks return c; if ((ts = c.getGenericInterfaces()) != null) { // 3.遍历x实现的所有接口 for (int i = 0; i < ts.length; ++i) { // 4.如果x实现了Comparable接口，则返回x的Class if (((t = ts[i]) instanceof ParameterizedType) && ((p = (ParameterizedType)t).getRawType() == Comparable.class) && (as = p.getActualTypeArguments()) != null && as.length == 1 && as[0] == c) // type arg is c return c; } } } return null; }

 / * HashMap的成员变量数组 */ transient Node<K,V>[] table; / * 存储的是entrySet，其实里面的每个元素就是HashMap的每个节点 */ transient Set<Map.Entry<K,V>> entrySet; / * HashMap中已存元素的个数 size */ transient int size; / * HashMap被修改的次数 put remove 操作的次数 */ transient int modCount; //阈值 capacity*loadFactor 或者是将要初始化扩容的容量值 int threshold; / * 负载因子 */ final float loadFactor; 

简单看一下底层源码，我们可以做出以下总结：

HashMap的初始容量是16，默认加载因子是0.75，扩容按照原始容量的2倍扩容，可以存储null值和null键，因为没有加锁，当多个线程同时操作一个hashmap就可能出现不安全的情况，所以线程也是不安全的，底层是由数组+链表+红黑树实现。

当添加一个元素（key-value）时，就首先计算元素key的hash值，以此确定插入数组中的位置，但是可能存在同一hash值的元素，这时就添加到同一hash值的元素的后面，他们在数组的同一位置，但是形成了链表，同一各链表上的Hash值是相同的，所以说数组存放的是链表。而当链表长度大于8时，链表就转换为红黑树，以及当数组的长度大于64时，也会自动转换成红黑树，这样大大提高了查找的效率。

通过哈希表函数/哈希算法，将hash值转换成数组的下标，下标位置上如果没有任何元素，就把Node(节点)添加到这个位置上。如果说下标对应的位置上有链表。此时，就会拿着key和链表上每个节点的key进行equals。如果所有的equals方法返回都是false，那么这个新的节点将被添加到链表的末尾。如其中有一个equals的结果返回了true，那么这个节点的value将会被覆盖。