简单谈谈HashMap

# 概述 面试Java基础，HashMap可以说是一个绕不过去的基础容器，哪怕其他容器都不问，HashMap也是不能不问的。 除了HashMap，还有HashTable跟ConcurrentHashMap，两个都是线程安全的哈希容器，但是HashTable是JDK1.0就有的容器，线程安全是通过`synchronized`关键字来实现的，而且锁住的是整个table对象，虽然线程安全，但是并发性能并不高。因此在JDK1.5里面并发大师Doug Lea操刀写了个ConcurrentHashMap，通过粒度更细的锁来实现更高的性能。 # HashMap的历史 在不同版本的JDK中，HashMap是在不停优化的。 - 比如JDK1.6里面new HashMap时，开辟了内存空间，如果不使用，则浪费内存；JDK1.7里面改成了懒加载，new HashMap并没有开辟内存空间，节约了内存空间 - 1.8优化了hashCode算法：高16位异或（XOR）低16位 主要是为了增加扰动，减少碰撞几率 - 1.8里面优化了hash碰撞较多情况下的性能问题（链表长度限制为8，过长时请将链表转换为TreeNode(红黑树)） # 配置常量 ```Java static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 static final int MAXIMUM_CAPACITY = 1 << 30; static final float DEFAULT_LOAD_FACTOR = 0.75f; static final int TREEIFY_THRESHOLD = 8; static final int UNTREEIFY_THRESHOLD = 6; static final int MIN_TREEIFY_CAPACITY = 64; ``` HashMap容器初始化的容量为16，默认负载因子为0.75，树化阈值为8，反树化阈值为6。 # put流程 - 对key的hashCode()做hash运算，计算index； - 如果没碰撞直接放到bucket里； - 如果碰撞了，以链表的形式存在buckets后； - 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树(JDK1.8中的改动)； - 如果节点已经存在就替换old value(保证key的唯一性) - 如果bucket满了(超过load factor*current capacity)，就要resize。 # get流程 - 对key的hashCode()做hash运算，计算index; - 如果在bucket里的第一个节点里直接命中，则直接返回； - 如果有冲突，则通过key.equals(k)去查找对应的Entry； - 若为树，则在树中通过key.equals(k)查找，O(logn)； - 若为链表，则在链表中通过key.equals(k)查找，O(n)。 # Hash算法 ```Java static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } ``` HashMap中可以存放key为null的值，放在首位。 将高16位与低16位异或运算，通过这样一个扰动函数，减小了hash冲突的概率。然后再通过这个hash值与数组的长度进行取模运算，决定这个键值对该放入哪个bin中。 > (n - 1) & hash 这个算法是当bin为bull的时候，直接将Node放入table中；当扩容的时候，存在两种情况，要么放在原来的位置，要么往后移动原来的容量大小的位置，这时候使用的是下面这个算法： > e.hash & oldCap 如果得到的结果为零，则在原位置；反之，则将其向高位移动oldCap大小的位置。 # 拓展 String的Hash算法如下： ```Java public int hashCode() { int h = hash; if (h == 0 && value.length > 0) { char val[] = value; for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h; } ``` String类中的hashCode计算方法还是比较简单的，就是以31为权，每一位为字符的ASCII值进行运算，用自然溢出来等效取模。 哈希计算公式可以计为s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] 那为什么以31为质数呢? 主要是因为31是一个奇质数，所以`31*i=32*i-i=(i<<5)-i`，这种位移与减法结合的计算相比一般的运算快很多。