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可能已经不同了。