简述HashMap的基本原理

HashMap是基于哈希表实现的，由数组+链表\红黑树组成。在添加数据时先计算key的哈希值，若key的哈希值和某个值的哈希值相同，则比对key和值的区别，若相同则进行替换，若不同则存入链表或红黑树中。具体在下面的put方法实现中。
在JDK1.7版本中，HashMap仅采用数组加链表的形式进行存储，后来在JDK1.8中引入了红黑树，在链表长度>8且数组长度>64时，链表会自动转换为红黑树进行存储，若红黑树的大小小于6时会退化成链表。

简述HashMap的put过程

Hash在添加数据时首先会进行判断，判断数组是否为空，若为空则初始化一个长度为16的数组并进行添加。若不为空则根据key的哈希值进行索引，若哈希值为空则直接添加，并判断size+1是否大于临界值，若大于临界值则需要进行扩容。若key的哈希值不为空则有两种情况，一种是有两个一模一样的key插入进来，还有一种就是虽然哈希值相同但是key不相同，因为哈希值是有限的。这时候就要判断key是否相同。若相同则直接进行替换，以最后的key为主。若不相同则要把key存入数组下的链表或红黑树中。这时候我们要先进行判断数组下面连着的是不是红黑树。如果是红黑树则要判断红黑树中的key是否相同，若相同则直接替换，若不同则红黑树添加。如果不是红黑树我们则要先遍历链表，检验key是否已经在链表中存在，若存在则进行覆盖，若不存在则在链表的末尾添加该kv。添加后我们还需要对链表的长度进行判断，若链表的长度大于8且数组的长度大于64，则链表需要转换为红黑树。

简述HashMap的扩容过程

首先我们要判断HashMap的旧容量（oldCap）是否大于0.若不大于0则证明此HashMap是刚刚创建的，需要对其进行初始化，我们设置容量为16的数组，设置扩容阈值为16*0.75=12，当容量大于12时会进行自动扩容。若旧容量大于0则证明已经初始化完成。那么我们就新建一个容量为原数组2倍的新数组，并将原数组的数据复制到新数组中。若数组中的next为空，则证明数组下面没有链表或红黑树，可以直接添加到新数组。若不为空我们就要判断下面的数据结构是否为红黑树。若是红黑树我们直接红黑树添加。若不是我们则先要遍历链表，并判断原表的哈希值和新表的哈希值是否相同。若相同则把该数组下面的所有值放置原位，若不相同则把需要移动的数组的所有值安置在原始位置+增加的数组大小的位置上。

ConcurrentHashMap

ConcurrentHashMap是HashMap的线程安全版本，所以在数据结构上和HashMap基本相同。在Java1.7版本中使用的是分段的数组+链表，在1.8版本中则跟HashMap1.8一样使用率数组+链表/红黑树。
1.7版本中ConcurrentHashMap采用了分段锁，底层使用的是ReentrantLock.在put的时候要先计算key的哈希值，定位到segment，如果是空就先初始化segment.若不为空则使用ReetrantLock加锁，如果获取锁失败就自旋获取，如果自旋超过一定次数就阻塞获取，保证能获取到锁。之后的流程和HashMap1.7版本相同。
1.8版本中ConcurrentHashMap采用了CAS+Synchronized来保证线程安全。相对于segment来说锁粒度更细，性能更好。