HashMap的用法相信我不用解释了，常用于无序键值对的存放，由于其有良好的查找和插入性能，是大量使用的数据结构。HashMap相关的方法有get,put，常见的参数包括loadFactor,Capacity等，在后面都会提到。经常被提到的另两个相似的类是HashTable和java.util.concurrent.ConcurrentHashMap ，这三个类主要区别是多线程时候的性能以及是否线程安全，一言以蔽之：性能HashMap>ConcurrentHashMap>HashTable，但是HashMap是非线程安全的，其余则安全。
最近面试老被问到hashMap的实现，于是花了点时间对其完整的看了一遍。话不多说，进入正题。
基本的原理
java.util.HashMap中有一个Entry[] table ，数据都存放在这个里面。
Entry是HashMap中的一个静态内部类。用于实现一个链表结构，节点表示map中的一个值，从定义可以看出：
首先entry是用于实现链表的一个节点，有key，value用于存储自身节点数据，还有next用于下个节点的引用。
我们看HashMap的默认构造函数：
再看HashMap中的get方法：
我们可以得到这几个结论：
get就是查找对应entry的过程，entry链被放在table数组这n个桶里
1.对nullkey做单独处理，其实就是放在table[0]中。
2.根据key的hash值，决定entry在哪个桶。
3.对桶内的entry链表进行遍历，当查找到时返回value。
4.找不到，返回null
这里要插一个不相关的，要遍历hashmap必须通过hashmap.entrySet().iterator()来遍历，前者本身没有实现iterable一定要注意。entrySet就是保存entry的Set集合类再次重申，hashmap没有实现collection 接口和iterable接口
loadFactor 和 initCapacity
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认加载因子，加载因子是一个比例，当HashMap的数据大小>=容量*加载因子时，HashMap会将容量扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//阈值，当实际数据大小超过threshold时，HashMap会将容量扩容，threshold＝容量*加载因子
int threshold;
//加载因子
final float loadFactor;
可以清楚地看到，默认我们是构造了一个初始容量为16，加载因子为0.75f的一个map。第一次扩容发生在什么时候呢？16*0.75=12
有趣的细节
容量总是2的倍数，为什么呢？为了寻址的快速。
关于扩容
寻址是通过 index & (table.length-1)实现的，其实就是一个取模，如果table.length 是2的倍数的话，table.length-1 总是 111111... 的结构，与运算可以方便的得到mod值。
为什么不用类的hashcode，而是要再做一次hash？避免最坏情况。
int hash = hash(key.hashcode()); ----参见上文的get方法
我们来看hash函数干了什么。
从注释上可以看出：这个函数以位移和异或的方式保证了hashcode不会有最坏情况出现（即大多数kv都分到了同一个桶）。在默认的加载因子下最坏不超过8的冲突。其实就是让分布更加的均化。
引用了StackOverflow上面的老外解释：
关于扩容
之前提到了当容量达到阈值后，HashMap会进行扩容。扩容时干了什么呢？
可以看到，做的事情包括：
1.重新申请空间存放table
2.transfer（把老数据移到新的table中），并将table指向到新的table（之后老table自动垃圾收集掉）
3.调整新的threshold值，以便下一次的resize能够在put方法中被激活
如果研究put方法可以看到：
在put中有这么一个判断
View Code
1 if (size++ >= threshold) 2 resize(2 * table.length);
size的解释是The number of key-value mappings contained in this map. 而threshold已经解释过了。也就是说put时会对元素数量进行检查，并视情况进行扩容。