JDK1.8源码分析之HashMap
HashMap的数据结构（1.8）
前言
今天来说说HashMap，之前的List，主要是ArrayList、LinkedList，这两者反应了两种思想：
* ArrayList以数组形式实现，顺序插入、查找快，插入、删除较慢
* LinkedList以链表的形式实现，顺序插入、查找较慢，插入、删除方便
然而HashMap是拥有结合上面两种数据结构的优点，它是基于哈希表的Map接口的实现，以key-value的形式存在。
构造图如下：
蓝色线条：继承
绿色线条：接口实现、
正文
要理解HashMap，就必须了解其底层实现，而底层实现最终要的就是其数据结构了。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。
要分析理解HashMap源码之前必须对hashcode进行说明。
源于HashCode的官方文档定义：
hashcode方法返回该对象的哈希码值。支持该方法是为哈希表提供一些优点，如 java.util.Hashtable提供的哈希表。
hashCode的常规协定：
在 Java 应用程序执行期间，在同一对象上多次调用 hashCode 方法时，必须一致地返回相同的整数，前提是对象上 equals 比较中所用的信息没有被修改。从某一应用程序的一次执行到同一应用程序的另一次执行，该整数无需保持一致。
如果根据 equals(Object) 方法，两个对象是相等的，那么在两个对象中的每个对象上调用 hashCode 方法都必须生成相同的整数结果。
以下情况不 是必需的：如果根据 equals(java.lang.Object) 方法，两个对象不相等，那么在两个对象中的任一对象上调用 hashCode 方法必定会生成不同的整数结果。但是，程序员应该知道，为不相等的对象生成不同整数结果可以提高哈希表的性能。
实际上，由 Object 类定义的 hashCode 方法确实会针对不同的对象返回不同的整数。（这一般是通过将该对象的内部地址转换成一个整数来实现的，但是 JavaTM 编程语言不需要这种实现技巧。）
当equals方法被重写时，通常有必要重写 hashCode 方法，以维护 hashCode 方法的常规协定，该协定声明相等对象必须具有相等的哈希码。从上可得到：
1、hashCode的存在主要用于查找的快捷性，如Hashtable、HashMap等，hashCode是用来在散列存储结构中确定对象的存储地址的；
2、如果两个对象相同，就适用于equals（Object）方法，那么这两个对象的hashCode一定要相同；
3、如果两个对象的equals方法被重写，那么对象的hashCode尽量重写，并产生hashCode的使用对象，一定要和equals方法中使用的一致；
4、两个对象的hashCode相同，并不一定表示两个对象相同，也就是不一定适用equals（Object）方法，只能说明这两个对象在散列存储结构中，如Hashtable，放在“同一个篮子里”。
HashMap定义
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
HashMap是一个散列表，它的存储的内容就是键值对（key-value）映射。
HashMap继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口
HashMap的实现不是同步的，意味着它不是线程安全的。他的key和value都可以为null。此外HashMap的映射不是有序的。
HashMap的属性
/** * 初始容量为16，容量必须是2的n次幂 */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** * 最大容量为2的30次方 */ static final int MAXIMUM_CAPACITY = 1 << 30; /** * 默认加载因子为0.75f */ static final float DEFAULT_LOAD_FACTOR = 0.75f;
/** * 数组，长度必须为2的n次幂 */ transient Node<K,V>[] table; /** * Holds cached entrySet(). Note that AbstractMap fields are used * for keySet() and values(). */ transient Set<Map.Entry<K,V>> entrySet; /** * 存储的元素数量 */ transient int size; /** * 用来实现fast-fail机制的 */ transient int modCount; /** * 下次扩容的临界值，size>=threshold就会扩容，threshold等于capacity*load factor (capacity * load factor). * * @serial */ int threshold; /** * 加载因子 * * @serial */ final float loadFactor;
HashMap是通过“拉法链”实现hash表的，它包括几个重要的成员变量：table, size, threshold, loadFactor, modCount。
其中table数组的实现：
static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V 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) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }
Node是HashMap的内部类，继承了Map的Entry接口，定义了键key、值value和下一个节点的引用next，以及hash值。
很明确的可以看出Entry的结构，他是一个单线链表的一个节点。也就是说HashMap的底层结构是一个数组，而数组的元素是一个单向链表。
之前介绍的List中，查询的时候需要遍历所有的数组，为了解决这个问题HashMap采用hash算法将key散列为一个int值，这个int值对应到数组的下标，再做查询的时候，拿到key散列值，根据数组下标就能直接找到存储在数组的元素。但是由于hash可能出现相同的散列值，为了解决冲突，HashMap采用将相同的散列值存储到一个链表中，也就是说在一个链表中的元素他们的散列值绝对是相同的。找到数组下标取出链表，再遍历链表是不是比遍历整个数组效率高！！
HashMap构造函数
/** * 构造一个指定初始容量和加载因子的构造函数 */ public HashMap(int initialCapacity, float loadFactor) { //初始容量和加载因子合法性校验 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); } /** * 构造一个指定初始容量的构造函数 */ public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } /** * 构造一个默认容量为16，默认加载因子为0.75的HashMap */ public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } /** * 构造一个指定map的HashMap */ public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }
/** * 返回一个大于输入参数且最近的2的整数次幂的数 */ static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }
在这里提到了两个参数：初始容量，加载因子。这两个参数是影响HashMap性能的重要参数，其中容量表示哈希表中桶的数量，初始容量是创建哈希表时的容量，加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。系统默认负载因子为0.75，一般情况下我们是无需修改的。
API方法
put方法
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } /** * Implements Map.put and related methods * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don't change existing value * @param evict if false, the table is in creation mode. * @return previous value, or null if none */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; //table未初始化或者长度为0，进行扩容 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //(n - 1) & hash 确定元素存放在那个桶中，桶为空， // 新生成节点放入，此时这个节点放在数组中 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else {//桶中的元素已经存在 Node<K,V> e; K k; //比较桶中的第一个元素（数组中的节点）的hash值相等，key相等 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) //将第一个元素赋值给e，用e来记录 e = p; //hash值不相等，即key不相等，为红黑树节点 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;//跳出循环 } //判断链表中的节点的key和插入的元素的key是否相等 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break;//相等跳出循环 //用于遍历桶中的链表，与前面的e=p.next结合，可以遍历链表 p = e; } } //在桶中找到key值、hash值与插入元素相等的节点 if (e != null) { // existing mapping for key //记录e的value V oldValue = e.value; //onlyIfAbsent为false或者oldValue为null if (!onlyIfAbsent || oldValue == null) //用新值替换旧值 e.value = value; afterNodeAccess(e);//访问回调 return oldValue;//返回旧值 } } ++modCount;//fast-fail更改 //实际大小大于阈值则扩容 if (++size > threshold) resize(); //插入后回调 afterNodeInsertion(evict); return null; }
扩容
/** * 扩容函数 * * @return the table */ final Node<K,V>[] resize() { //当前table保存 Node<K,V>[] oldTab = table; //保存table大小 int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold;//保存当前阈值 int newCap, newThr = 0; //之前的table大小大于0 if (oldCap > 0) { //之前table大于最大容量 if (oldCap >= MAXIMUM_CAPACITY) { //阈值为最大整形 threshold = Integer.MAX_VALUE; return oldTab; } //容量翻倍，使用左移，效率高 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) //阈值翻倍 newThr = oldThr << 1; // double threshold } //之前阈值大于0 else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; // oldCap = 0并且oldThr = 0，使用缺省值（如使用HashMap()构造函数，之后再插入一个元素会调用resize函数，会进入这一步） else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //新阈值为0 if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) //初始化table Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; //之前的table已经初始化过了 if (oldTab != null) { //赋值元素重新进行hash for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; // 将同一桶中的元素根据(e.hash & oldCap)是否为0进行分割，分成两个不同的链表，完成rehash do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
扩容会伴随一次重新hash分配，并且会遍历hash表中的所有元素，是非常耗时的，所以应进来避免resize（）。
查找方法
/** * 查询方法 */ public V get(Object key) { Node<K,V> e; 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) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //table已经初始化，长度大于0，根据hash寻找table中的项也不为空 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; }
remove方法
与put方法类似
/** * 删除 */ public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } /** * Implements Map.remove and related methods * * @param hash hash for key * @param key the key * @param value the value to match if matchValue, else ignored * @param matchValue if true only remove if value is equal * @param movable if false do not move other nodes while removing * @return the node, or null if none */ final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { Node<K,V>[] tab; Node<K,V> p; int n, index; if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { Node<K,V> node = null, e; K k; V v; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) node = p; else if ((e = p.next) != null) { if (p instanceof TreeNode) node = ((TreeNode<K,V>)p).getTreeNode(hash, key); else { do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { node = e; break; } p = e; } while ((e = e.next) != null); } } if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { if (node instanceof TreeNode) ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); else if (node == p) tab[index] = node.next; else p.next = node.next; ++modCount; --size; afterNodeRemoval(node); return node; } } return null; }
clear方法
/** * 清除所有元素，并把每个位置置为null */ public void clear() { Node<K,V>[] tab; modCount++; if ((tab = table) != null && size > 0) { size = 0; for (int i = 0; i < tab.length; ++i) tab[i] = null; } }
总结
1、两者最主要的区别在于HashTable是线程安全的，HashMap是非线程安全的。HashTable的实现方法里面添加了synchronized关键字来确保线程同步，因此相对而言HashMap性能可能会高些，若无特殊需求建议使用HashMap，在多线程的环境下使用HashMap则可以使用Collections.synchronizedMap( )方法来获取一个线程安全的集合（Collections.synchronizedMap（）实现原理是Collections定义了一个SynchronizedMap的内部类，这个类实现了Map接口，在调用方法时，使用synchronized来保证线程同步，当然了实际上操作的还是我们传入的HashMap实例，简单说就是Collections.synchronizedMap（）方法帮我们在操作HashMap的时候自动添加了synchronized来实现线程同步，其他类似的Collections.synchronizedxxx（）也是一样的道理）
2、HashMap允许key为null值，而HashTable则不允许。HashMap以null作为key值则总是存储在数组的第一个节点上。
3、HashMap是实现了Map接口，HashTable是实现了Map接口和Dictionary抽象类
4、HashMap的初始容量为16，HashTable为11，两者的加载因子都是0.75。扩容的时候，HashMap是为原来的两倍，HashTable是两倍还要+1.
5、两者的底层实现都是数组+链表+红黑树。
6、两者计算hash值的方法不同：
HashTable是直接用key的hashCode对table的长度进行取模。
int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length;HashMap是key的hashCode与hashCode的高16位做异或运算。
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
https://www.cnblogs.com/leesf456/p/5242233.html
原文: http://tengj.top/2016/04/15/javajh3hashmap/ 作者: 嘟嘟MD