HashMap采用了数组和链表的数据结构，能在查询和修改方便继承了数组的线性查找和链表的寻址修改，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的。
解决哈希冲突的三个方法：
a.开放定址法
又被称为再散列法，包括线性探测再散列、二次探测再散列、伪随机探测再散列
b.再哈希法
地址冲突后，对哈希结果再次进行哈希，直到不冲突为止
c.链地址法
冲突后的元素组成一个链指向当前地址（HashMap采用的该方式，只是当链表长度超过8后，就会把链表改为红黑树）
以下是具体的put过程（JDK1.8版）
1、对Key求Hash值，然后再计算下标
2、如果没有碰撞，直接放入数组中（碰撞的意思是计算得到的Hash值相同，需要放到同一个bucket中）
3、如果碰撞了，以链表的方式链接到后面
4、如果链表长度超过阀值( TREEIFY THRESHOLD==8)，就把链表转成红黑树，链表长度低于6，就把红黑树转回链表
5、如果节点已经存在就替换旧值
6、如果数组满了(容量16*加载因子0.75)，就需要 resize（扩容2倍后重排）
选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当长度大于8的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。
下面从初始化一个HashMap及put一个键值对，来看下HashMap的resize()
Map exampleMap = new HashMap();
初始化Map则，可以看到exampleMap中，loadFactor是默认值0.75（loadFactor用于设置阈值，即到什么程度执行resize操作）
exampleMap.put("1",1)
map中放入数据，看下源代码做了什么
1public V put(K key, V value) { 2 return putVal(hash(key), key, value, false, true); 3} 4 5/** 6 * Implements Map.put and related methods 7 * 8 * @param hash hash for key 9 * @param key the key 10 * @param value the value to put 11 * @param onlyIfAbsent if true, don't change existing value 12 * @param evict if false, the table is in creation mode. 13 * @return previous value, or null if none 14 */ 15final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {//hash是1的hash值，key是字符串1，value是1 16 Node<K,V>[] tab; Node<K,V> p; int n, i; 17 if ((tab = table) == null || (n = tab.length) == 0)//tab的length是16，n的值是16 18 n = (tab = resize()).length; 19 if ((p = tab[i = (n - 1) & hash]) == null)//按一定的规则，确定新增的参数放在tab数组的tab[i]位置，如果该位置为空，则直接初始化Node放入该位置； 20 tab[i] = newNode(hash, key, value, null); 21 else {//如果tab[i]不为空进入该分支 22 Node<K,V> e; K k; 23 if (p.hash == hash && 24 ((k = p.key) == key || (key != null && key.equals(k))))//如果hash相同，key相同，则替换tab[i] 25 e = p; 26 else if (p instanceof TreeNode)//判断如果tab[i]是treeNode，则把当前数据放入红黑树中 27 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 28 else {//如果tab[i]是普通Node，则在tab[i]维护的链尾部新增，当链接的Node数量大于8后，要把链改为红黑树结构存储 29 for (int binCount = 0; ; ++binCount) { 30 if ((e = p.next) == null) { 31 p.next = newNode(hash, key, value, null); 32 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 33 treeifyBin(tab, hash); 34 break; 35 } 36 if (e.hash == hash && 37 ((k = e.key) == key || (key != null && key.equals(k)))) 38 break; 39 p = e; 40 } 41 } 42 if (e != null) { // existing mapping for key 43 V oldValue = e.value; 44 if (!onlyIfAbsent || oldValue == null) 45 e.value = value; 46 afterNodeAccess(e); 47 return oldValue; 48 } 49 } 50 ++modCount; 51 if (++size > threshold)//添加Node之后判断当前map中数据量是否大于12（DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR），如果大于需要resize，否则结束当前操作 52 resize(); 53 afterNodeInsertion(evict); 54 return null; 55}