HashMap实现原理分析 概述
HashMap是Java集合框架（Java Collection Framework， JCF）中一个基础类，它在1998年12月，加入到Java 2版本中。在此之后，Map接口本身除了在Java 5中引入了泛型以外，再没有发生过明显变化。然而HashMap的实现，则为了提升性能，不断地在改变。
1.hash表的复习在正式学习HashMap源码之前，先复习一下hash表的实现。
1.1 什么是哈希表哈希表（Hash table，也叫散列表），是根据关键字值（key,value）直接进行访问的数据结构。也就是说，它通过把关键字映射到表中一个位置来访问的纪录，以加快查找的速度。这个映射函数叫做散列函数，存放纪录的数组叫散列表。
1.2 哈希函数 1.2.1 直接定址法取关键字或关键字的某个线性函数值为哈希地址。
H(key) = key 或 H(key) = a*key+b 1.2.2 除法散列法取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词.
H(key) = key % p （p<=m） 1.2.3 平方散列法当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。
H(key) = ((key * Key) >> X) << Y 1.2.4 fibonacci散列法和平方散列法类似，此种方法使用斐波那契数列的值作为乘数而不是自己。
对于16位整数而言，这个乘数是40503。
对于32位整数而言，这个乘数是2654435769。
对于64位整数而言，这个乘数是11400714819323198485。
开放寻址法把所有的元素都存放在散列表中，也就是每个表项包含动态集合的一个元素（元素可以为NULL）。
1.在开放寻址法中，当要插入一个元素时，可以连续地检查散列表的个各项（连续检查是可以通过不同的算法获得偏移位），直到找到一个空槽来放置这个元素为止。
2.当查找一个元素时，要检查所有的表项，直到找到所需的元素，或者最终发现元素不在表中。
3.在开放寻址法中，对散列表元素的删除操作执行起来比较困难。当我们从槽i中删除关键字时，不能仅将此位置元素置空。因为这样做的话，会导致在无法判断此位置是否有元素。应该用个特殊的值表示该元素已经删除。
其中H(key）为散列函数，m为散列表长，di为增量序列，可有下列三种取法:
di=1,2,3，…，m-1，称线性探测再散列。
di=1^2,-1^2,2^2,-2^2，⑶^2，…，±（k)^2,(k<=m/2）称二次探测再散列。
di=伪随机数序列，称伪随机探测再散列。
产生碰撞时，再使用另一个散列函数计算地址，直到碰撞不再发生，这种方法不易产生“聚集”，但增加了计算时间（一个地址的产生可能会经过多个散列函数的计算）
Hi=Hn(key), [n=1,2 ...,]有一个包含一组哈希函数 H1…Hn 的集合。当需要从哈希表中添加或获取元素时，首先使用哈希函数 H1。如果导致碰撞，则尝试使用 H2，以此类推，直到 Hn。所有的哈希函数都与 H1 十分相似，不同的是它们选用的乘法因子。
1.3.3 拉链法产生碰撞时，把哈希到同一个槽中的所有元素都放到一个链表中。拉链法采用额外的数据结构来处理碰撞，其将哈希表中每个位置（slot）都映射到了一个链表。
1.3.4 公共溢出区建立一个公共溢出区，当发生碰撞时，把碰撞元素放到缓冲区。
1.4 负载因子负载因子(load factor)，它用来衡量哈希表的 空/满 程度，一定程度上也可以体现查询的效率，
计算公式为:
负载因子越大，意味着哈希表越满，越容易导致冲突，性能也就越低。因此，一般来说，当负载因子大于某个常数(可能是 1，或者 0.75 等)时，哈希表将自动扩容。
2红黑树的复习 2.HashMap 2.1 HashMap的定义 public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>,Cloneable, Serializable { /** 默认的哈希表的负载因子 */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** hashMap的最大容量 */ static final int MAXIMUM_CAPACITY = 1 << 30; /** hashMap的默认容量 */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** HashMap要调整的下一个容量大小 */ int threshold; /** hashMap容量的变量 */ int threshold; /** 哈希表负载因子的变量 */ final float loadFactor; /** 构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的 HashMap */ public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } /** 构造一个带指定初始容量和默认加载因子 (0.75) 的 HashMap。 */ public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } /** 构造一个带指定初始容量和加载因子的 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(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); } /** 返回给定容量大小的下一个容量。 */ 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; } /** 构造map的结构或者将map的内容全部赋值 evict 初始化hashMap时是false，其余的情况为true。 */ final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { int s = m.size(); if (s > 0) { if (table == null) { // pre-size 初始化空间 float ft = ((float)s / loadFactor) + 1.0F; int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); if (t > threshold) threshold = tableSizeFor(t); } else if (s > threshold) //重新调整空间 resize(); for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); putVal(hash(key), key, value, false, evict); } } } }