Hash（哈希），又称“散列”。散列（hash）英文原意是“混杂”、“拼凑”、“重新表述”的意思。 在某种程度上，散列是与排序相反的一种操作，排序是将集合中的元素按照某种方式比如字典顺序排列在一起，而散列通过计算哈希值，打破元素之间原有的关系，使集合中的元素按照散列函数的分类进行排列。 在介绍一些集合时，我们总强调需要重写某个类的 equlas() 方法和 hashCode() 方法，确保唯一性。这里的 hashCode() 表示的是对当前对象的唯一标示。计算 hashCode 的过程就称作 哈希。 我们通常使用数组或者链表来存储元素，一旦存储的内容数量特别多，需要占用很大的空间，而且在查找某个元素是否存在的过程中，数组和链表都需要挨个循环比较，而通过 哈希 计算，可以大大减少比较次数。 举个栗子：现在有 4 个数 {2,5,9,13}，需要查找 13 是否存在。 然后把它们存储到对应的位置。当要查找 13 时，只要先使用哈希函数计算它的位置，然后去那个位置查看是否存在就好了，本例中只需查找一次(暂不考虑hash函数冲突)，时间复杂度为 O(1)。 因此可以发现，哈希其实是随机存储的一种优化，先进行分类，然后查找时按照这个对象的分类去找。哈希通过一次计算大幅度缩小查找范围，自然比从全部数据里查找速度要快。 哈希函数（算法）不是指某种特定的函数（算法），而是一类函数，它有各种各样的实现。例如 MD4、MD5、SHA。哈希函数（散列函数）能够将任意长度的输入值转变成固定长度的值输出，该值称为散列值，输出值通常为字母与数字组合。好的哈希算法发生碰撞的几率非常小，碰撞主要取决于： 我们先大概瞥一眼 JDK 1.7 之前的 HashMap 结构： 简而言之，HashMap 是由数组组成的一定数量的桶（bucket）。在进行存储时，使用 key 的 hashcode() 通过 hash 函数计算得到 hash 值，然后通过 为了高效的定位元素在数组中的位置，以及使放入的元素尽可能均匀的分布在数组中。 如果 hash 函数足够完美，将能实现数据的均匀分配，此时时间复杂度为 O(1)。但是开发者通常会编写较差的哈希函数，这将导致分布不均。 Hash碰撞表示对于同一个hash函数，对不同的key进行hash计算得出对结果相同。此时数组将会有很大一部分被浪费。 为了解决这个问题，一方面，我们可以增大哈希值的取值空间来减少冲突的可能性，比如使 hash 表(数组，桶bucket)大于所需的总数据量。期望只要有哈希表的 70 % 被占用就足够。存储元素的个数和哈希表桶的数量的比值就叫做负载因子（Load factor）。
负载因子的值通常是可配置的，并在时间和空间成本之间进行权衡，下图是负载因子值调低调高时的影响。 Java 中 HashMap 的默认负载因子是 0.75，也就是说只要哈希表的 75 % 被占用就足够了。Java HashMap 的默认初始容量为 16，即存储区数组在首次插入时被延迟初始化。当插入的元素到达一定的阈值，HashMap 将会扩容来重新计算哈希，该阈值的计算公式为：
以 HashMap 的默认值计算，则为：, 也就是说当插入第 13 个元素后会进行扩容为之前的两倍 oldThreshold << 1，此时将发生重新哈希（Rehashing），由于重新哈希处理增加了存储桶的数量，因此降低了负载因子。 为什么 HashMap 加载因子默认是 0.75？ 计算结果如上述的列表所示，当一个桶中的链表长度达到 8 个元素的时候，概率为 0.00000006，几乎是一个不可能事件。选择0.75作为默认的加载因子，完全是时间和空间成本上寻求的一种折衷选择。 为了给冲突元素一个合适的位置存储，我们将解决方案从寻址方向上分为两个大类： JDK 1.8后，Java HashMap 是结合闭合式寻址中第一种和第三种的实现。 在代码中，桶数组用如下变量表示： 这里需要注意几点： 每个桶内部由链表组成，在代码中为类 Node<K, V> 的实例，此类是 HashMap 类的静态内部类，并且实现 Map.Entry<K, V> 接口，此节点的表示形式为： 之前我们提到计算索引是使用哈希函数计算的 hash 值和桶数组长度求余，但是求余的效率并没有直接按位运算的高。同样我们需要借助一些位运算的技巧，这里 n 为桶数组的长度： 注意，为什么这里 hash 函数需要将高位数据移位到低位进行异或运算呢？这是因为有些数据计算出的哈希值差异主要在高位，而 HashMap 里的哈希寻址是忽略容量以上的高位的，那么这种处理就可以有效避免类似情况下的哈希碰撞。 计算桶索引并不只是发生在 put 方法时，在调用 get、contains、remove 时都会调用 hash 方法重新计算 hash 值并在计算桶索引。 HashMap 内部使用单向链表来维护哈希冲突的元素，但为什么不用数组或双向链表，这其实是一个平衡后的考虑： 使用单向链表的好处在于，其既可以使空间相对较少，也能保证删除和插入的时间复杂度为 O(1)。但是如果链表过长，最坏的可能是所有元素都放入一个桶里，此时时间复杂度将变为 O(n)。为了优化这一点，JDK 1.8 使用了红黑树来优化链表过长的情况。 当桶数组的长度超过 MIN_TREEIFY_CAPACITY 且桶中的元素超过 TREEIFY_THRESHOLD 值时，链表转为红黑树。 当桶中元素减少至 UNTREEIFY_THRESHOLD 时，红黑树退回到链表。 因为当大量哈希冲突的时候会导致节点链表越来越长从而降低 HashMap 性能。而红黑树为自平衡二叉搜索树，重新平衡并不完美，但保证在 O(logN) 时间内搜索，其中 n 是树的节点数。插入和删除操作，以及树的重排和重新着色，也在 O(logN) 时间内执行。 因此在数据量大的且桶中冲突较大的散列表中红黑树比单向链表更有优势。 本质上这是个安全问题 因为在元素放置过程中，如果一个对象哈希冲突，都被放置到同一个桶里，则会形成一个很长的链表，我们知道链表查询是线性的，会严重影响存取的性能。而在现实世界，构造哈希冲突的数据并不是非常复杂的事情，恶意代码就可以利用这些数据大量与服务器端交互，导致服务器端 CPU 大量占用，这就构成了哈希碰撞拒绝服务攻击，国内一线互联网公司就发生过类似攻击事件。 为什么选择红黑树而不是二叉树或绝对平衡二叉树呢 而红黑树它是一棵自平衡树但不是绝对平衡树，优点有以下： 我们知道 HashMap 使用 hash 函数定位桶，桶内部使用单向链表存储冲突元素，不能保证插入的顺序。LinkedHashMap 继承了 HashMap，在原有的数据结构基础上，将所有桶内元素通过双向链表链接起来，该链表定义了迭代的顺序，默认是数据插入的顺序，也可以配置为访问顺序。转换为红黑树时也维护链表。 如果将键重新插入映射中，则插入顺序不会受到影响。 该实现提供了顺序保证，但是并没有增加时间复杂度，和 HashMap 一样还是 O(1)。TreeMap 由于使用了红黑树来提供顺序保证，所以时间复杂度为 O(logN)。 以下是 TreeMap、HashMap 和 LinkedHashMap 之间的重要区别。 注：本章的代码均基于JDK 1.7.0_67 Java 7中的ConcurrentHashMap的底层数据结构仍然是数组和链表。与HashMap不同的是，ConcurrentHashMap最外层不是一个大的数组，而是一个Segment的数组。每个Segment包含一个与HashMap数据结构差不多的链表数组。整体数据结构如下图所示。 ConcurrentHashMap与HashMap相比，有以下不同点 HashTable（jdk 1.2 时期的，后续没没太多优化，不建议使用，尽做向后兼容）容器在竞争激烈的并发环境下表现出效率低下的原因是所有访问HashTable的线程都必须竞争同一把锁，那假如容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效的提高并发访问效率，这就是ConcurrentHashMap所使用的锁分段技术，首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。 注：本章的代码均基于JDK 1.8.0_111 Java 7为实现并行访问，引入了Segment这一结构，实现了分段锁，理论上最大并发度与Segment个数相等。Java 8为进一步提高并发性，摒弃了分段锁的方案，而是直接使用一个大的数组。同时为了提高哈希碰撞下的寻址性能，Java 8在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为O(N)）转换为红黑树（寻址时间复杂度为O(long(N))）。 即JDK1.8中，ConcurrentHashMap的数据结构与1.8中的HashMap结构类似，都是：数组+单向链表/红黑树。 其数据结构如下图所示： Java 8的ConcurrentHashMap同样是通过Key的哈希值与数组长度取模确定该Key在数组中的索引。同样为了避免不太好的Key的hashCode设计，它通过如下方法计算得到Key的最终哈希值 不同的是，Java 8的ConcurrentHashMap作者认为引入红黑树后，即使哈希冲突比较严重，寻址效率也足够高，所以作者并未在哈希值的计算上做过多设计，只是将Key的hashCode值与其高16位作异或并保证最高位为0（从而保证最终结果为正整数）。相比HashMap，多了一步与运算：保证最高位为0，从而保证最终结果为正整数。 要想对链表或红黑树进行put操作，必须拿到表头或根节点，所以，锁住了表头或根节点，就相当于锁住了整个链表或者整棵树。这个设计与分段锁的思想一致，只是其他读取操作需要用cas来保证。 相比JDK1.7的ConcurrentHashMap，JDK1.8中的改进之处主要体现在： https://www.cnblogs.com/goloving/p/15242372.html什么是 hash
为什么要有 Hash
H[key] = key % 3;
// 四个数 {2,5,9,13} 对应的哈希值为：
H[2] = 2 % 3 = 2;
H[5] = 5 % 3 = 2;
H[9] = 9 % 3 = 0;
H[13] = 13 % 3 = 1;
哈希函数(算法)
JDK 1.7 之前的 HashMap
(hash值 % 数组长度)来确定将 Entry(key + value) 放入数组的哪个桶里。
正确实现 hashcode() 方法返回的 hash 值可以达到散列分布的目的，同样的键也会返回相同的 hash 值，因此我们使用 hash 信息来确定元素在数组中的下标信息以达到快速访问。Hash碰撞及解决（Collision）
负载因子与容量
这个跟一个统计学里很重要的原理——泊松分布有关。泊松分布是统计学和概率学常见的离散概率分布，适用于描述单位时间内随机事件发生的次数的概率分布。
等号的左边，P 表示概率，N 表示某种函数关系，t 表示时间，n 表示数量。等号的右边，λ 表示事件的频率。在理想情况下，使用随机哈希码，在扩容阈值（加载因子）为 0.75 的情况下，节点出现在频率在 Hash 桶（表）中遵循参数平均为 0.5 的泊松分布。忽略方差，即 X = λt，P(λt = k)，其中 λt = 0.5的情况。所以我们可以知道，其实常数 0.5 是作为参数代入泊松分布来计算的，而加载因子 0.75 是作为一个条件，当 HashMap 长度为length/size ≥ 0.75 时就扩容，在这个条件下，冲突后的拉链(链表)长度和概率结果为：0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
冲突元素寻址
开放式寻址（Open Addressing）
闭合式寻址（Closed Addressing）
通过在哈希表数组本身中搜索另一个空存储桶来处理冲突。
键始终存储在散列到的桶中。在每个桶的基础上使用单独的数据结构来处理冲突。
每个桶中最多存放一个键。
每个桶存储任意键数。
理论最大负载系数为1。
没有理论上的最大负载系数。
哈希表数组的大小必须始终至少与哈希表中键的数量一样大。
性能随着负载系数的增长而降低。
开放式寻址相关技术
闭合式寻址相关技术
HashMap 详解
先总体了解下 HashMap 作为集合类的特性：
final HashMap<String, String> hashMap = new HashMap<>(20, 0.75f);
final Iterator<Map.Entry<String, String>> iterator = hashMap.entrySet().iterator();
while (iterator.hasNext()) {
if (iterator.next().getKey().equals("test")) {
iterator.remove(); // ok!
}
}
// java 8 removeIf
hashMap.entrySet().removeIf(stringStringEntry -> stringStringEntry.getKey().equals("test"));
数组桶(bucket)
transient Node<K,V>[] table;
单链表
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // 使用 hash 定位桶
final K key; // 节点存放的 key
V value; // 节点存放的 值
Node<K,V> next; // 指向链表的下一个节点
}
HashMap 如何计算桶索引
index = hash(key) & (n-1) // 相当于求 hash(key) % n，当 n 为 2 的次幂且不为 0 时成立
// hash 函数求 hash 值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
为什么桶内不使用 ArrayList 或 LinkedList
为什么桶内元素过长时用红黑树
- 树属于折半查找，于较长的链表相比查询效率要高
- 自平衡树解决了二叉树的计算情况问题（二叉树退化成链表）
- 非绝对平衡树比绝对平衡树在增删节点时要高效一些
因此红黑树是综合性能较强的树型数据结构。LinkedHashMap
TreeMap 比较
No.
关键点
TreeMap
HashMap
LinkedHashMap
1
元素的顺序
插入到 TreeMap 中的元素根据其键的自然顺序进行排序，或者通过在 Map 创建时提供的 Comparator 进行排序，具体取决于使用的构造函数。
HashMap 不保证 Map 的顺序，也不保证顺序随时间保持不变。
LinkedHashMap 默认遵循元素的插入顺序，并维护插入元素的顺序。
2
内部实现
TreeMap 的内部实现不允许存储 null 键，但允许 null 值。
HashMap 允许存储一个 null 键以及多个 null 值。
LinkedHashmap 的内部实现与 HashMap 相似，因此允许存储一个 null 键和多个 null 值。
3
时间复杂度
TreeMap 的 get、put 和 remove 操作的时间复杂度都是 O(logN)，比 HashMap 大。
HashMap 在 get、put 和 remove 操作的情况下具有 O(1) 的复杂性。
LinkedHashMap 具有与 HashMap 相同的复杂度，即 O(1)。
4
继承
TreeMap 实现了 Collection 框架的 SortedMap 接口，它是 Map 的子代。TreeMap 内部实现了红黑树（一种自平衡二叉搜索树）。
HashMap 实现了简单的 Map 接口，并在内部使用散列来存储和检索其元素。
LinkedHashMap 扩展了 HashMap 并在内部像 HashMap 一样使用散列。
5
索引性能
与 HashMap 和 LinkedHashMap 相比，TreeMap 维护其元素的顺序，因此性能指标较低，并且需要更多内存。
HashMap 不维护其元素的任何插入顺序，因此与 TreeMap 相比更快，也不根据其值对其元素进行排序，因此也比 LinkedHashMap 更快。
LinkedHashMap 比 TreeMap 快，但比 HashMap 慢。
6
比较
TreeMap 中的元素通过使用 compareTo() 方法进行比较，其中也可以提供自定义实现。
HashMap 使用 Object 类的 compare() 方法进行元素比较。
LinkedHashMap 也使用 Object 类的 compare() 方法进行元素比较。
Java 7基于分段锁的ConcurrentHashMap
Java 8基于CAS的ConcurrentHashMap
//计算key的哈希值
h = key.hashCode();
//ConcurrentHashMap中的hash算法，其中HASH_BITS为0x7fffffff，即Integer.MAX_VALUE的值
h = (h ^ (h >>> 16)) & HASH_BITS
//HashMap中的hash算法
h = h ^ (h >>> 16)
//计算table数组位置
(n - 1) & h
put 大体思路
参考
https://www.zeral.cn/data-structure/java-hashmap-%E5%AE%9E%E7%8E%B0/
http://www.jasongj.com/java/concurrenthashmap/