以下讲解基于JDK1.7
HashMap底层是一个数组，哈希值相同的元素放在数组中的相同的位置，多个相同哈希值的元素形成一个链表。也就是说，元素的组织形式是单向链表。
下面从put、get、remove这三个方法分析一下源代码，看看HashMap增删查改是怎么做的。
构造HashMap对象的时候做了初始化，指定默认的初始容量（数组长度）和增长因子
接下来，从put开始分析
从上面三段代码可以看出添加一个元素的基本流程：
（1）HashMap的key值允许为null，而且key为null的元素放在数组中下标为0的位置
（2）根据待插入元素的key值计算出一个哈希值，然后根据这个哈希值和数组的长度计算该元素将要放置的位置（PS：下标）。如果这个位置为空，那么直接插入。否则，遍历该位置上的链表，依次比较他们的key值是否相同，如果相同，则将用新值替换旧值，然后返回就值。
（3）正常插入，将待插入的元素放置在链表的头部，然后将其指向原先的链表头部（即：原先放置在待插入位置的元素）。也就是说，新插入的元素是放在头部的，我觉得这样做的好处可能是根据LRU的原则减少遍历的次数。
(4)有一种特殊情况是，扩容。
扩容就是，将原数组中的每个位置的元素都迁移到新数组中，在迁移到新数组的过程中同样先计算哈希值，然后得出将要放置在新数组中那个位置上。链表的迁移过程相当于将原先的链表倒置，先将头部的元素迁移过去，然后将下一个元素迁移过去，令next元素的next指向新数组位置上的元素，最终呈现出来的效果就是链表倒置。
接下来看get操作
get操作比较简单：
（1）根据key算哈希值，进而得出元素可能的位置，然后遍历该位置上的链表，比较key值是否相同，相同则返回，否则返回null
最后是remove
删除也相对比较简单：
（1）删除元素所在位置，遍历链表，比较key值，找到待删除元素以后，如果当前只有一个元素，直接删除，此位置置位NULL，否则将前面元素的next指向后面元素。
HashMap在并发情况下存在的问题（并发就是没法保证顺序）
（1）插入的元素可能被覆盖
假设有两个线程都执行到这里，线程1它的key=A，value=aaa，线程2它的key=B，value=bbb。
假设i=1，那么线程1执行的时候table[1]=new Entry<>(1234, "A", "aaa", null);
等到线程2执行的时候table[1]=new Entry<>(1234, "B", "bbb", null);
于是乎，线程1插入的数据就丢失了（或者说是被覆盖了）
（2）put的时候，链表可能形成环形数据结构，导致如果查找一个不存在的元素时死循环
那么环状是怎么形成的呢？发生在扩容的时候。请看图
假设有两个元素A和B，它们的关系是A.next=B，B.next=null
大概就是下面这个样子
假设有两个线程，线程-1和线程-2，它们在执行插入的时候都发现需要扩容，于是乎都开始扩容。
当然，扩容是在它们自己的内存中进行的。假设线程-1完成对A元素的迁移后准备对B进行迁移并执行到Entry<K,V> next = e.next;时还没执行时线程被挂起了。执行到线程-2先执行完扩容，于是扩容后的指向关系变成了这个样子：B.next=A，A.next=null
特别注意，看图上画的好像是元素直接放到数组的某个位置，但我们要知道，其它放的是元素的地址，也就是说元素本身的位置不变，修改的只是指针指向。尽管线程-2构造的新数组对线程-1而言是不可见的，但是不可否认，线程-2在扩容过程中已经将A和B的指向关系修改了，也就是说，此时，B是指向A的，这一点对线程-1而言是可见的。
接下来，线程-1醒来，继续执行
while(null != e) {
Entry<,> next = e.;
(rehash) {
e.= == e.? : hash(e.);
}
i = (e., newCapacity);
e.= newTable[i];
newTable[i] = e;
e = next;
}
此时，对照代码应该是这样的
经过这一遍，现在在新数组中的指向关系变成：B-->A-->NULL
紧接着，因为e已经是A了，所以null != e，于是再执行一遍
然后就变成这样了
接下来，麻烦来了。
查找C，经过计算C应该与A、B在数组的同一个位置，于是遍历链表
于是，通过A找到B，通过B又找到A，通过A又找到B，通过B又找到A，如此反复，永远都不为null，死循环
终于讲明白了
最后，再提一点，就是hash方法，字符串和非字符串算哈希值的方法是不一样的
参考：
http://blog.csdn.net/zhuqiuhui/article/details/51849692
https://www.cnblogs.com/binyue/p/3726403.html
本文转自 手不要乱摸 51CTO博客，原文链接:http://blog.51cto.com/5880861/1984059
