HashMap

HashMap是基于数组加链表的数据结构实现的，java 8上的话是数组加链表或者数组加红黑树。

HashMap是线程不安全的。

HashMap允许空键值对，及key与value都可以为null。

一、流程图

基于Java 8

HashMap的存放是Key， value的形式。Key可以是Object，而每个Object都有一个HashCode。

Put操作的时候会先对key的hashCode进行位运算得到hash值。

然后进行位运算：hash & (table.length – 1)等同于 hash%(table.length – 1)。

范围是0 —table.length – 1。

这样就得到其在数组中table中的位置。

1、为何是数组加链表。

Hash碰撞：通过这种方法hash & (table.length – 1)算出的index有可能相同。相同index的就在同一条链表中。Hash表长度越小，Hash碰撞概率越大。

Put里面有两个两个耗时的地方：

1、put的时候需要去遍历该链表看是否已经有了。

2、数组长度如果超出了阈值，那么需要扩容，重新计算hashCode然后计算下标。

里面有个扩容因子，根据扩容因子算出数组长度到达多少才需要扩容，扩容后全部元素都得重新算。

Get里面的耗时在于遍历链表查询。

二、Java 8上得优化：

put操作得时候判断链表的长度是否大于8，如果是的话将链表转换为红黑树，因为红黑树的查询更加快速。

查找的事件复杂度由O(n)->O(logn)

三、数据结构

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

四、key为何可以为null

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

五、HashMap与ConcurrentHashmap与Hashtable的设计对比

ConcurrentHashmap、 HashMap和Hashtable都是key-value存储结构，但他们有一个不同点是 ConcurrentHashmap、Hashtable不支持key或者value为null，而HashMap是支持的。为什么会有这个区别？在设计上的目的是什么？

ConcurrentHashmap和Hashtable都是支持并发的，这样会有一个问题，当你通过get(k)获取对应的value时，如果获取到的是null时，你无法判断，它是put（k,v）的时候value为null，还是这个key从来没有做过映射。HashMap是非并发的，可以通过contains(key)来做这个判断。而支持并发的Map在调用m.contains（key）和m.get(key),m可能已经不同了。