map 主要有四个实现类：
HashMap、Hashtable、LinkedHashMap、TreeMap
LinkedHashMap：
有序，按照顺序插入数据，根据Iterator遍历时，先插的先得到。
TreeMap：
是SortedMap接口的实现类，默认按照键值的升序保存数据，也可以指定排序的比较器，key必须实现Comparable接口或者构造map时传入自定义的Comparable，否则会抛ClassCastException异常
HashMap：
线程不安全，可用synchronizedMap或者ConcurrentHashMap代替便线程安全了
根据键的HashCode值来存储数据
最多允许一条记录的键为null，允许多个值为null
HashMap 详解：
底层结构：数组 + 链表 + 红黑树
以上是hashmap的结构，每一个黑点表示一个Node，其中的Node是什么呢，来看一下源码：
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;
}
......此处省略部分方法，详细请看jdk1.8源码
}
Node是HashMap 的内部类，实现了Map.Entry接口，
hash用来定位数组索引的位置， next表示链表的下一个Node。 而Node[] table 表示哈系桶数组，初始化长度默认16
HashMap是使用哈希表来存储的，哈希表为了解决哈希冲突，用开放地址法和链地址法，HashMap采用链地址法，即数组和链表结合，每个数组元素上都有个链表结构，当数组被hash后，得到数组下标，然后把数组放在对应下标的链表里。
下面先介绍下HashMap的构造函数，了解一下内部构造：
HashMap有四个构造函数，默认无参构造和参数是Map的构造函数是Java规范推荐实现的，还有两个是HashMap专门提供的。
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
threshold： 所能容纳的key-value对的极限，即HashMap扩容的阈值。等于容量(数组长度)乘以负载因子（length * loadFactor）
loadFactor：负载因子，默认0.75 （用于衡量散列表的空间使用程度）
modCount：字段主要用来记录HashMap内部结构发生变化的次数
size：这个字段其实很好理解，就是HashMap中实际存在的键值对数量
length：数组（table）长度
负载因子默认值0.75是对空间和时间效率的一个平衡选择。
//默认初始容量为16（2的4次方），该数必须为2的幂次
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量 30
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//当put一个元素时，其链表长度达到8时将链表转换为红黑树
static final int TREEIFY_THRESHOLD = 8;
//链表长度小于6时，解散红黑树
static final int UNTREEIFY_THRESHOLD = 6;
//默认的最小的扩容量64，为避免重新扩容冲突，至少为4 * TREEIFY_THRESHOLD=32，即默认初始容量的2倍
static final int MIN_TREEIFY_CAPACITY = 64;
在HashMap中，哈系桶数组table的长度length设置成2的n次方，这是非常规设置（一般设置为素数），这样做主要是为了取模和扩容时的优化，减少冲突。
尽管这样，依然避免不了会出现拉链过长的情况，一旦过长，就会严重影响性能，jdk1.8中 进行了优化，加入了红黑树的结果，当链表长度过长（默认为8）时，链表就转为红黑树结构。
下面讲一下HashMap 的get，put方法的实现原理：
一 如何确定哈希桶数组索引的位置：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Hash算法包括：取key的hashCode值，高位运算，取模运算
二 HashMap的put方法：
下面看一下put方法的源码以及大概的分析：
public V put(K key, V value) {
//对key的hashCode做hash
return putVal(hash(key), key, value, false, true);
}
//这里onlyIfAbsent表示只有在该key对应原来的value为null的时候才插入，也就是说如果value之前存在了，就不会被新put的元素覆盖。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//若tab为空，则创建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//计算index（即根据key计算hash值得到数组的索引），并对null做处理。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//若节点key的hash值相同，则覆盖value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//判断这个链是否为红黑树（TreeNode）
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//链的长度大于8，则转为红黑树处理
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//key 已经存在，直接覆盖value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//超过最大容量，扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
下图为对HashMap的put方法的分析过程图示例：
简单来讲，HashMap的put方法是基于hashing原理，在put方法传递键值对时，先对键调用hashCode方法，其返回的hashCode的值来确定桶的位置，即数组的索引来存储键，来作为Map.Entry
三 HashMap的hash冲突问题：
产生原因： 在put方法在hashCode获取hash值时，当put的元素越来越多时，难免产生不同的key产生相同的hash值问题，此时，便造成了hash冲突问题。
解决方法： 链表结构解决冲突问题
当存储时，若hash值相同，则会找到相同的bucket的位置，此时发生碰撞，但由于是链表结构，每个Map.Entry都有一个next指针，
获取时，调用equals方法。并且java8中的红黑树结构，更加大大减少了查询时的复杂度。
减少碰撞方法：使用final修饰 或 不可变对象作为键（例如：Integer，String），因为这些已经重写了equals方法和hashcode方法
另外：存入相同的key时，获取的是后put的数据。
四 HashMap的扩容机制：
扩容就是当前容量不够存储数据时，进行扩容，resize方法。下面看一下简单的扩容过程示意图：
前半部分讲到，默认的容量为16，且可修改，但必须为2的幂次，扩容就是将原来的容量扩大2倍，jdk1.8做了些优化，
因为是扩大2倍，所以，元素要么在远位置，要么在原位置移动2次幂的位置。
JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置。
而1.8做了些优化，并不会重新计算hash值，当扩容后，n变为2倍，n-1的范围多出了一个bit字节，通过这个bit是0还是1判断，0则是索引没变，1则是索引变化，变为“原索引+oldCap” resize（）这块的源码暂时还未仔细看，有兴趣的可以看看，一起沟通研究下。
五. 线程安全问题：
文章开头说到，HashMap是线程不安全的，在并发环境中，会造成死循环，为什么呢？
以jdk1.7 为例，重新调整map大小会出现竞争问题，在多线程中，map调整大小的过程中，即扩容重哈希时，存储在链表的元素的次序会倒过来，因为移动到新的bucket位置时，HashMap将元素放在头部而不是尾部（避免尾部遍历），这样导致Entry链形成环，若竞争发生，这样会发生死循环。导致线程不安全。多线程建议使用ConcurrentHashMap（采用了分段加锁技术）
后续会持续更新 ConcurrentHashMap 详解