JDK1.7版本中的HashMap

以下讲解基于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;
}

此时，对照代码应该是这样的