HashMap详解

HashMap基于哈希表的 Map 接口的实现，键值是HashMap类型的，必须为Object，所以其键值不能使用基本数据类型，保存进去的基本数据类型会做装箱操作。

HashMap根据键的HashCode存储数据，所以可以快速的定位到其值，但无法确定遍历的顺序。允许使用 null 值和 null 键（只能有一个为null的键，值可有多个null）。HashMap是非线程安全的，可以使用synchronizedMap是其线程安全。

其底层jdk1.8之前是数组+链表，jdk1.8版本后HashMap的数据结构改为为 ：数组 + 链表+红黑树；（因为链表的特性，当链表过长时性能会有影响，所以经过大量的测试，选择了数组 + 链表+红黑树结合的方式）（使用链表的查找性能是 O(n)，而使用红黑树是 O(logn)）。

HashMap是用链表+红黑树的形式来解决hash冲突的，就是把同一hash值但不相等的数据，归到一个集合内成为哈希桶，内部的元素由链表形式组织起来，hash表中存放链表的头，当链表元素数量达到设置值后就将链表转换成红黑树形式。在插入时，链表节点超过8个、且数组大小超过64个则将链表转换成红黑树，否则不转换。其中数组小于64时会进行扩容不会转化为红黑树。在移除数据时，当红黑树的节点移除到剩6个时，将红黑树转换成链表。（选择6个而不是8个，是为了避免频繁进行红黑树和链表的转换，造成性能的损耗。）

• 数组+链表

• 数组+链表+红黑树
  

我们先看一下HashMap中设置的几个重要属性：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;  //认初始容量 - 必须是 2 的幂，默认16
static final int MAXIMUM_CAPACITY = 1 << 30;	//最大容量
static final float DEFAULT_LOAD_FACTOR = 0.75f;	 //构造函数中未指定负载因子时，默认使用的负载因子。
static final int TREEIFY_THRESHOLD = 8; 	//链表元素超过8个，才使用红黑树结构
static final int MIN_TREEIFY_CAPACITY = 64;	//数组大于64个，才使用红黑树结构
static final int UNTREEIFY_THRESHOLD = 6;	//红黑树元素小于6个，就转化为链表

默认的数组大小 initialCapacity 16，加载因子loadFactor 为0.75，扩容的阈值=默认初始大小 * 加载因子 ，默认情况下阈值为 16 * 0.75 = 12;
​ 数组的容量为2ⁿ，在达到扩容阈值后，扩容后大小为当前的2倍

HashMap中的构造函数，可以通过一下几种方式区构建HashMap对象。

//构造一个具有指定初始容量和负载因子的空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);
}
//造一个具有指定初始容量和默认加载因子 (0.75) 的空HashMap 
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空HashMap 。
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
}
//构造一个与指定Map具有相同映射的HashMap (ashMap用加载因子0.75和足以容纳指定Map中的映射的初始容量创建)
public HashMap(Map m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

在Hash中同一个hashCode的不同元素保存在同一个哈希桶中，它是通过一个内部类 Node implements Map.Entry保存的

//每个元素
static class Node implements Map.Entry {
    final int hash;		//哈希值
    final K key;		//键
    V value;			//值
    Node next;		//保存的下一元素
    .......一些方法.......
}
//计算key的hash值
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//

hashmap通过put方法存储数据：

//存储数据
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
//参数：hash（key的哈希值）、key 、value、onlyIfAbsent(如果为真，则不更改现有值)、evict（如果为 false，则表处于创建模式）
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node[] tab; 
    Node p; 
    int n, i;
    //将属性table赋值给当前的局部变量 tab，判断tab是不是空或者长度是不是 0，
    //如果为空或者数组长度为0，则进行表初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;	//n就是哈希表的长度
     //将哈希表中与要插入数据的位置对应的数据取出来赋值给p，i就是要插入的数据应该在哈希表中的位置，如果没找到，代表哈希表中当前的位置是空的，否则就代表找到数据了。
    //如果要插入的位置没有数据，直接创建新节点放在这个位置
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    //如果要插入的位置有数据
    else {
        Node e; 
        K k;
        //第一种情况，key一样时，将其复制给e，方便下面做替换
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
       //第二种情况，key不存在，先判断是不是树节点，如果是，就创建一个树形节点，存放数据
        else if (p instanceof TreeNode)	
            e = ((TreeNode)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);	
                    //判断节点数量，看是否需要转换成红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) 
                        treeifyBin(tab, hash);	//转换成红黑树
                    break;
                }
                //如果当前遍历到的数据和要插入的数据的 key 是一样的，将其复制给e，方便下面做替换
                if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //如果当前的节点不等于空,则会替换其value值
        if (e != null) { 
            V oldValue = e.value;	//将当前节点的值赋值给 oldvalue
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;	//将当前要插入的 value 替换当前的节点里面值
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;	//增加长度
    //判断put后size是否达到了临界值threshold，如果达到了临界值就要进行扩容
    if (++size > threshold)
        resize();	//扩容方法
    afterNodeInsertion(evict);
    return null;
}

根据上面的put方法，总结数据插入原理：（也是根据键的hashcode存储数据）

1. 首先计算要插入数据 key 的hash值（hash(key)）。
2. 判断数组是否为空，为空则初始化数组（第一次插入节点时才会进行初始化），不为空，计算其索引位置（(n - 1) & hash）
3. 查看索引位置是否存在其他数据节点，不存在则新创建一个节点存放
4. 若存在数据节点，先判断插入的key是否和头结点的key相等，若相等，替换其value即可
5. 若不相等，则判断头结点是不是红黑树节点，是，从根节点开始遍历，看能否查找到和插入的key相等的节点，如果找到和插入的key相同的节点，则替换其value，否则新建一个红黑树节点存放数据，并进行平衡调整
6. 若头节点不是红黑树，则表明为链表，此时遍历链表的节点，看能否查找到和key相等的节点
7. 如果找到和key相同的节点，则替换其value，否则在链表尾部新建节点。
8. 插入完成之后判断当前节点数是否超过8个，且数组大小是否超过64，若超过则转换为红黑树。
9. 最后判断数组是否应该扩容

final Node[]//如果原Node数组的长度>0) {
    Node[] oldTab = table;		//老的HashMap
    int oldCap = (oldTab == null) ? 0 : oldTab.length;		//老表的长度
	//如果初始化的时候传入了容量参数，则threshold为用户设定的值，否则为0
    int oldThr = threshold;		
    int newCap, newThr = 0;		//新表的长度和阈值
    //如果原Node数组的长度>0
    if (oldCap > 0) {
        //判定Node数组是否已达到极限大小，若判定成功将不再扩容，直接将原Node数组返回
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //如果新Node数组的大小(oldCap*2)小于数组极限大小，并且原Node数组的长度大于等于数组初始化大小
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            //则将原扩容阀值，乘以2，当作新的扩容阀值
            newThr = oldThr << 1; 
    }
	//如果用户传递了容量参数，则使用用户传递的
    else if (oldThr > 0) 
        newCap = oldThr;
	//如果用户没有传递，则使用默认的
    else {          
        //默认容量大小(16赋给newCap
        newCap = DEFAULT_INITIAL_CAPACITY;
        //将(负载因子)0.75f * (默认的容量大小)DEFAULT_INITIAL_CAPACITY的计算结果，赋值给newThr(新的扩容阀值)
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
	//如果初始化的时候用户传入了容量参数和负载因子或者只传入了容量参数，
	//那么oldCap==0、oldThr>0，代表上面的else不会执行，那么此时newThr(新的扩容阀值)仍然==0：
    if (newThr == 0) {
        //此时计算，用户传入的容量参数 * 用户传入的负载因子loadFactor(也可能是默认的负载因子)，
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
	//扩容后新的扩容阀值
    threshold = newThr;
	//新建一个容量为newCap的新Node数组；
    @SuppressWarnings({"rawtypes","unchecked"})
    Node[] newTab = (Node[])new Node[newCap];
    table = newTab;
	//到这里新的表已经创建成功了，下面是复制数据了
	//如果原来的表不为null
    if (oldTab != null) {
        //遍历原Node数组
        for (int j = 0; j < oldCap; ++j) {		
            Node e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;	
                
                //如果该Node元素的下个元素为null，则说明该Node元素为左后一个。
                if (e.next == null)	
                    newTab[e.hash & (newCap - 1)] = e;	//则将该元素直接存于新Node数组的指定位置
                
                //如果该Node元素后边跟着的是一个红黑树结构：
                else if (e instanceof TreeNode)
                    //在新的Node数组中，会进行拆分
					//如果拆分后的子树的节点小于等于6个，则将其转为链表结构
                    ((TreeNode)e).split(this, newTab, j, oldCap);
                
                //如果是链表的情况下，则进行链表数据转移
                else {
                    Node loHead = null, loTail = null;
                    Node hiHead = null, hiTail = null;
                    Node next;
                    do {
                        //对链表进行遍历，其中有需要更换数组下标的，有不需要不需要的
                        next = e.next;
                        //e.hash&oldCap的结果是为0，说明该Node节点所对应的数组下标不需要改变
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)	//没有头结点，则将此作为头节点
                                loHead = e;
                            else				//有头结点则放在最后面即可
                                loTail.next = e;
                            loTail = e;
                        }
                        //结果不为0的，需要更新该Node节点所对应的数组下标
                        else {
                            //再判断是否为头结点
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    //Node节点所对应的数组下标不需要改变，直接把数组下标对应的节点指向新Node数组下标位置链表的头节点
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    //Node节点的数组下标需要改变，重新计算出所对应的数组下标值，然后指向新Node下标位置链表的头节点
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

1. 根据老表的扩容阈值等条件，计算出新表的容量和阈值
2. 然后创建新表，准备进行数据的迁移
3. 如果原Node数组不为空，遍历原Node数组
4. 遍历的该Node元素的下一个为null，则说明该Node元素后边既没有链表又没有红黑树，则将该Node元素直接存于新Node数组的指定位置
5. 如果遍历的该Node元素后边跟着的是一个红黑树结构，则在新的Node数组中，将该红黑树进行拆分，拆分后子树的节点小于等于6个，将其转为链表结构
6. 如果遍历的该Node元素是链表的情况下，对链表进行遍历，将链表中的Node元素迁移到新的Node数组中(分为需要更换数组下标的，和不需要的)；

//回指定键映射到的值，如果此映射不包含该键的映射，则返回null 
public V get(Object key) {
    Node e;
    return (e = getNode(key)) == null ? null : e.value;
}
final Node getNode(Object key) {
    Node[] tab; 
    Node first, e; 
    int n, hash; 
    K k;
    //已经初始化 && 数组对应位置存在对象
    //否则返回null,即没有找到元素
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & (hash = hash(key))]) != null) {
         //如果第一个元素存在，且头元素即是需要查找的元素,直接返回first
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        //如果第一个元素不是所差元素，则需要向后遍历查找
        if ((e = first.next) != null) {
            //看是否为树形节点，是，则按树的方式查询
            if (first instanceof TreeNode)
                return ((TreeNode)first).getTreeNode(hash, key);
            //不是树节点，则按链表的方式查询
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

HashMap、HashTable、ConcurrentHashMap

1、HashMap：存储不了大数据，线程不安全

2、HashTable：线程安全，sycn，但是会影响性能（不推荐，可用ConcurrentHashMap代替）

3、ConcurrentHashMap：采用了分段锁，不会影响全部，只影响hash值一样的，即只在链表或者红黑树的首节点加锁，只要不发生hash冲突就不会产生并发，相对于HashTable大大的提升了性能。