HashMap

https://github.com/leavesC/JavaKotlinAndroidGuide/blob/master/java_collections/Java集合框架源码解析之HashMap.md

https://juejin.im/post/5cdaa5e1f265da038932b5de

定义

HashMap 是用于映射(键值对)处理的数据类型，基于哈希表的 Map 接口的非同步实现，允许插入最多一条key为null的键值对，允许插入多条value为null的键值对。此外，HashMap 不保证元素顺序，根据需要该容器可能会对元素重新哈希，元素的顺序也会被重新打散，因此在不同时间段迭代同一个 HashMap 的顺序可能会不同。HashMap 非线程安全，即同一时刻有多个线程同时写 HashMap 的话可能会导致数据的不一致

HashMap 实际上是数组+链表+红黑树的结合体，其底层包含一个数组，数组中的每一项元素的可能值有四种：null、单独一个结点、链表、红黑树（JDK1.8 开始 HashMap 通过使用红黑树来提高元素查找效率）。当往 HashMap 中 put 元素的时候，需要先根据 key 的哈希值得到该元素在数组中的位置（即下标），如果该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表或者红黑树的形式来存放，如果该位置上没有元素，就直接向该位置存放元素

HashMap 要求映射中的 key 是不可变对象，即要求该对象在创建后它的哈希值不会被改变，否则 Map 对象很可能就定位不到映射的位置了

性能

HashMap 中声明的常量有以下几个，其中需要特别关注的是装载因子 DEFAULT_LOAD_FACTOR 和 TREEIFY_THRESHOLD

装载因子用于规定数组在自动扩容之前数据占有其容量的最高比例，即当数据量占有数组的容量达到这个比例后，数组将自动扩容。装载因子衡量的是一个散列表的空间的使用程度，装载因子越大表示散列表的装填程度越高，反之愈小。因此如果装载因子越大，则对空间的利用程度更高，相对应的是查找效率的降低。如果装载因子太小，那么数组的数据将过于稀疏，对空间的利用率低，官方默认的装载因子为0.75，是平衡空间利用率和运行效率两者之后的结果。如果在实际情况中，内存空间较多而对时间效率要求很高，可以选择降低装载因子的值；如果内存空间紧张而对时间效率要求不高，则可以选择提高装载因子的值

此外，即使装载因子和哈希算法设计得再合理，也不免会出现由于哈希冲突导致链表长度过长的情况，这将严重影响 HashMap 的性能。为了优化性能，从 JDK1.8 开始引入了红黑树，当链表长度超出 TREEIFY_THRESHOLD 规定的值时，链表就会被转换为红黑树，利用红黑树快速增删改查的特点以提高 HashMap 的性能

哈希算法

以下是 HashMap 中计算 key 值的哈希值以及根据哈希值获取其在哈希桶数组中位置的算法

/** * Computes key.hashCode() and spreads (XORs) higher bits of hash * to lower. Because the table uses power-of-two masking, sets of * hashes that vary only in bits above the current mask will * always collide. (Among known examples are sets of Float keys * holding consecutive whole numbers in small tables.) So we * apply a transform that spreads the impact of higher bits * downward. There is a tradeoff between speed, utility, and * quality of bit-spreading. Because many common sets of hashes * are already reasonably distributed (so don't benefit from * spreading), and because we use trees to handle large sets of * collisions in bins, we just XOR some shifted bits in the * cheapest possible way to reduce systematic lossage, as well as * to incorporate impact of the highest bits that would otherwise * never be used in index calculations because of table bounds. */

static final int hash(Object key){ int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

确定键值对在哈希桶数组的位置的步骤分为三步：计算 key 的 hashCode（h = key.hashCode()）、高位运算（h >>> 16）、取模运算（(n - 1) & hash）