共计 4910 个字符，预计需要花费 13 分钟才能阅读完成。
- HashMap 究竟是什么
基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作（get 和 put）提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键 - 值映射关系数）成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。
-
JDK1.7 与 JDK1.8 中 HashMap 区别
- 最重要的一点是底层结构不一样，1.7 是数组 + 链表，1.8 则是数组 + 链表 + 红黑树结构
- 插入键值对的 put 方法的区别，1.8 中会将节点插入到链表尾部，而 1.7 中是采用头插
- jdk1.7 中当哈希表为空时，会先调用 inflateTable() 初始化一个数组；而 1.8 则是直接调用 resize() 扩容
- jdk1.7 中的 hash 函数对哈希值的计算直接使用 key 的 hashCode 值，而 1.8 中则是采用 key 的 hashCode 异或上 key 的 hashCode 进行无符号右移 16 位的结果，避免了只靠低位数据来计算哈希时导致的冲突，计算结果由高低位结合决定，使元素分布更均匀
- 插入键值对的 put 方法的区别，1.8 中会将节点插入到链表尾部，而 1.7 中是采用头插
- 扩容时 1.8 会保持原链表的顺序，而 1.7 会颠倒链表的顺序
- 1.7 中是只要不小于阈值就直接扩容 2 倍；而 1.8 的扩容策略会更优化，当数组容量未达到 64 时，以 2 倍进行扩容，超过 64 之后若桶中元素个数不小于 7 就将链表转换为红黑树，但如果红黑树中的元素个数小于 6 就会还原为链表，当红黑树中元素不小于 32 的时候才会再次扩容。
-
JDK1.8 实现原理
- 数据结构存储
HashMap 是通过数组存储所有的数据，每个元素所存放数组的下标，是根据该存储元素的 key 的 Hash 值与该数组的长度减去 1 做与运算，如下所示：index = (length_of_array - 1) & hash_of_the_key
数组中存放元素的数据结构使用了 Node 和 TreeNode 两种数据结构，在单个 Hash 值对应的存储元素小于 8 个时，默认值为 Node 的单向链表形式存储，当单个 Hash 值存储的元素大于 8 个时，其会使用 TreeNode 的数据结构存储。
因为在单个 Hash 值对应的元素小于等于 8 个时，其查询时间最差为 O(8)，但是当单个 Hash 值对应的元素大于 8 个时，再通过 Node 的单向链表的方式进行查询，速度上就会变得更慢了；这个时候 HashMap 就会将 Node 的普通节点转为 TreeNode（红黑树）进行存储，这是由于 TreeNode 占用的空间大小约为常规节点的两倍，但是其查询速度可以得到保证，这个是通过空间换时间了。当 TreeNode 中包括的元素变得比较少时，为了存储空间的占用，也会转换为 Node 节点单向链表的方式实现，它们之间可以互相转换的。
-
Node
static class Node<K,V> implements Map.Entry<K,V> { final int hash;// 当前 Node 的 Hash 值 final K key;// 当前 Node 的 key V value;// 当前 Node 的 value Node<K,V> next;// 表示指向下一个 Node 的指针，相同 hash 值的 Node，通过 next 进行遍历查找 Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } ...... } -
TreeNode
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // red-black tree links 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); } ...... }
可以看到 TreeNode 使用的是红黑树（Red Black Tree）的数据结构，红黑树是一种自平衡二叉查找树，在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能，即使在最坏情况运行时间也是非常良好的，并且在实践中是非常高效的，它可以在 O(log n) 时间内做查找、插入和删除等操作，这里的 n 是树中元素的数目。
-
Hash 值的计算方法
// 计算指定 key 的 hash 值，原理是将 key 的 hash code 与 hash code 无符号向右移 16 位的值，执行异或运算。// 在 Java 中整型为 4 个字节 32 位，无符号向右移 16 位，表示将高 16 位移到低 16 位上，然后再执行异或运行，也 // 就是将 hash code 的高 16 位与低 16 位进行异或运行。// 小于等于 65535 的数，其高 16 位全部都为 0，因而将小于等于 65535 的值向右无符号移 16 位，则该数就变成了 // 32 位都是 0，由于任何数与 0 进行异或都等于本身，因而 hash code 小于等于 65535 的 key，其得到的 hash 值 // 就等于其本身的 hash code。static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
-
写入数据 (put)
public V put(K key, V value) { // 首先根据 hash 方法，获取对应 key 的 hash 值，计算方法见后面 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) // 为空则进行初使化，并将初使化后的数组赋值给变量 tab，数组的长值赋值给变量 n n = (tab = resize()).length; // 判断根据 hash 值与数组长度减 1 求与得到的下标，// 从数组中获取元素并将其赋值给变量 p(后续该变量 p 可以继续使用)，并判断该元素是否存在 if ((p = tab[i = (n - 1) & hash]) == null) // 如果不存在则创建一个新的节点，并将其放到数组对应的下标中 tab[i] = newNode(hash, key, value, null); else {// 根据数组的下标取到了元素，并且该元素 p 且不为空，下面要判断 p 元素的类型是 Node 还是 TreeNode Node<K,V> e; K k; // 判断该数组对应下标取到的第一值是不是与正在存入值的 hash 值相同、//key 相等（可能是对象，也可能是字符串），如果相等，则将取第一个值赋值给变量 e if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 判断取的对象是不是 TreeNode，如果是则执行 TreeNode 的 put 方法 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else {// 是普通的 Node 节点，// 根据 next 属性对元素 p 执行单向链表的遍历 for (int binCount = 0; ; ++binCount) { // 如果被遍历的元素最后的 next 为空，表示后面没有节点了，则将新节点与当前节点的 next 属性建立关系 if ((e = p.next) == null) { // 做为当前节点的后面的一个节点 p.next = newNode(hash, key, value, null); // 判断当前节点的单向链接的数量（8 个）是不是已经达到了需要将其转换为 TreeNode 了 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st // 如果是则将当前数组下标对应的元素转换为 TreeNode treeifyBin(tab, hash); break; } // 判断待插入的元素的 hash 值与 key 是否与单向链表中的某个元素的 hash 值与 key 是相同的，如果是则退出 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 判断是否找到了与待插入元素的 hash 值与 key 值都相同的元素 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; } -
读取数据 (get)
public V get(Object key) { Node<K,V> e; // 根据 Key 获取元素 if ((e = getNode(hash(key), key)) == null) return null; if (accessOrder) afterNodeAccess(e); return 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 语句的第一个判断条件 if ((tab = table) != null // 将数组赋值给变量 tab，将判断是否为 null && (n = tab.length) > 0 // 将数组的长值赋值给变量 n && (first = tab[(n - 1) & hash]) != null) {// 判断根据 hash 和数组长度减 1 的与运算，计算出来的的数组下标的第一个元素是不是为空 // 判断第一个元素是否要找的元素，大部份情况下只要 hash 值太集中，或者元素不是很多，第一个元素往往都是需要的最终元素 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) // 第一个元素就是要找的元素，因为 hash 值和 key 都相等，直接返回 return first; if ((e = first.next) != null) {// 如果第一元素不是要找到的元，则判断其 next 指向是否还有元素 // 有元素，判断其是否是 TreeNode if (first instanceof TreeNode) // 是 TreeNode 则根据 TreeNode 的方式获取数据 return ((TreeNode<K,V>)first).getTreeNode(hash, key); do {// 是 Node 单向链表，则通过 next 循环匹配，找到就退出，否则直到匹配完最后一个元素才退出 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } // 没有找到则返回 null return null; }
正文完
