按照哈希值进行分配数据，每个哈希值对应一个哈希桶。
当哈希值对应的哈希桶中存在多个元素时，称为哈希碰撞。
该数据结构称之为哈希表，哈希表="数组+链表。
哈希表中的哈希值中的每个值在内存地址都有单独的一个地址，与数据容量无关，复杂度是O1.
哈希桶是链表，所以复杂度是On。
? ?
HashMap是将哈希表作用于所有类型元素的实现。
HashMap中哈希桶的实现是基于hashCode的,每个hashCode对应多个对象（hashCode对应桶中的所有对象）。
hashCode是int类型，有42亿中可能性，可能发生哈希碰撞。
容量每次扩容是2的n次幂，与内存地址左移有关。左移一位为*2。
创造HashMap是空间并没有开辟处理，只有添加数据时才会开辟地址空间。
默认是int为4字节，2的4次方=16。默认HashMap的哈希桶为16个，每次左移一位，就是每次*2.
哈希值分配到16个桶中，哈希值&n-1，高位0低位1，0&任何数都为0，1&任何数都为1。
resize效率很低，可以适当的用空间换时间。
? ?
Java7中HashMap的实现。（实际就是把哈希表的数据结构实现了一遍，没有优化哈希碰撞）
当哈希值等于容量*负载因子的值时，HashMap会自动扩容。
自动扩容时，所有已存在对象的hashCode都会重新进行分配（实际没必要）并添加到新的空间中去。
扩容的新的容量是旧的容量的2倍。该操作为resize操作中包含rehash操作。
复制到新的大空间中，该操作为transfer操作。（操作太复杂）
问题：
容易碰到死锁（HashMap不是线程安全的）
在resize操作中会改变原有哈希表中元素的排列顺序
JAVA HASHMAP的死循环： https://coolshell.cn/articles/9606.html
无锁HASHMAP的原理与实现： https://coolshell.cn/articles/9703.html>
潜在的安全隐患
CVE-2011-4858
Tomca邮件组的讨论
Tomcat中使用一个哈希表来存储http的request值，会使得将request的值
全部串起来放到一个哈希桶中，会使哈希表退化成一个链表。
复杂度将会从O1退化成On，对n个元素进行查找可能会变成On方。
? ?
Java8对HashMap的改进
Java8中的扩容过程：解决链表顺序不变
将扩容后变化的链表拆分成多个链表，将高位的链表不变，
新的元素放在低位的链表中，避免元素顺序改变
再将高位的链表和低位的链表分别复制给新的哈希桶中去。
原文：https://www.cnblogs.com/ChengR/p/13047591.html