HashMap

通过 一行代码一行代码嚼烂之超详细注解手写HashMap 这篇博客我们详细地了解了HashMap的底层实现原理并且手动实现了一个HashMap。

在JDK1.7中，HashMap单纯使用数组+链表的形式存储数据，通过容量和负载因子的限制在容量达到初始值的0.75倍时，执行扩容。通过计算hash值决定新进来的元素在HashMap中的数组中的哪一条链表上。当hash碰撞频繁，将导致一条链表足够的长，查找时间复杂度为O(n)。

在JDK1.8中，对HashMap进行了优化，当hash碰撞严重时，写入链表的长度超过了阈值(默认为8)并且 table 的长度不小于64(否则扩容一次)，此时链表将转换为红黑树，而红黑树的时间复杂度为O(logn)，提高了查找的效率。

那么HashMap在并发场景中有什么问题呢？

一、JDK1.7的HashMap在并发场景中使用HashMap容易出现死循环。

在并发场景中的HashMap在进行扩容时，调用 resize() 方法里的 rehash() 时，容易出现环形链表（感兴趣的同学可以去了解一下多线程操作下环形链表的形成）。当环形链表形成，若此时的计算出的index正好对应着HashMap中数组的环形链表位的时候，而要寻找的value值又不存在于这条环形链表中，此时出现死循环，一直寻找无果。
导致这一原因的出现正是JDK1.7的头插法，这也是为什么在JDK1.8的时候，将HashMap优化成了尾插法，并且为了提高查找效率，将时间复杂度为O(n)的链表优化成时间复杂度为O(logn)的红黑树。

二、线程安全问题

线程安全问题是由于多个线程在对HashMap进行put操作时，第一个线程的put操作对第二个线程的put操作的不可见性从而导致了value值被覆盖丢失，进而导致HashMap的理想插入结果与实际插入结果不一致的问题。

HashTable

我们都知道，数组查询很快，而链表增删很快，那么将两者的优点合二为一，就有了HashTable。

那么为什么说HashTable是线程安全的？我们先来看一下HashTable的如下方法：

Hashtable<String,String> table = new Hashtable<>();
        table.put("name","中国");
        table.get("name");

点进HashTable的put和get方法，查看各自的源代码，如下：

public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }

        addEntry(hash, key, value, index);
        return null;
    }

public synchronized V get(Object key) {
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return (V)e.value;
            }
        }
        return null;
    }

可以看到HashTable的put以及get方法都加上了synchronized关键字，所以在多线程的操作下，HashTable能够保证并发线程安全。但是正是由于这样，在高并发情况下的取值或者存储是非常耗时的。