HashMap

1. 特点2.存储过程3.HashMap集合类的成员4.扩容5.遍历HashMap

1. 特点

存取无序键和值都可以是null，但是只能有一个null键JDK 1.8之前是数组+链表的组合实现，JDK1.8以后数组+链表+红黑树阈值问题：只有同时满足链表长度大于8、数组长度大于等于64时，链表会被转化为红黑树，即数组+链表+红黑树，其他情况还是使用数组+链表。（比如当hashmap满足数组长度大于64，有部分key的链表小于8，那么它也是采用的链表的形式，只有链表长度大于8的链表，才使用红黑树）

2.存储过程

调用HashMap的构造函数，创建一个长度为16的Entry[]数组存储键值对；而在jdk1.8以后，不在构造函数初始化存储键值对的数组，而是在第一次执行put时创建（延迟加载的概念），并且不是Entry[]数组，而是Node[]数组（符合链表的概念）执行put时，先根据key，调用类的hashCode()计算hash，然后结合数组长度计算索引（多种算法），如果计算出的索引空间没有数据，直接将键值对放入。

面试题：哈希表采用何种算法计算索引？还有哪些算法可以计算出索引？ 答：hashCode计算hash值，结合数组长度进行计算，具体算法有 1.无符号右移(>>>) 2.按位异或(^) 3.按位与(&) 备选（效率较低） 1.平方取中 2.取余 3.伪随机数

如果根据hashCode计算得到的hash根据算法算出来的索引处存在数据，则比较两者的hash，如果不一样，则在此索引空间新建一个Node将键值对存储，并将Node放到该索引空间中，与之前存在的数据构成一个链表（拉链法）如果索引一样，hash也一样，则发生哈希碰撞，那么会调用类的成员方法equals比较两个键是否一样，如果一样，则使用后者的值覆盖；如果不一样，则继续依次比较该索引空间上的链表上的键，如果都不相等，如第3步，拉链处理 完整过程如下图：

3.HashMap集合类的成员

面试题：HashMap的容量为什么是2的n次幂？ 在进行hash运算时使用位与(&)方式计算索引，公式hashCode&(length-1)，2的n次幂减1，进行位与运算后可以保留低位，最大程度上计算出的索引的均匀性，也就可以最大程度上保证数组中各索引空间的均匀分布，避免造成空间浪费，也可以避免过多数据插入时发生hash碰撞，减少链表、红黑树长度等。总之，可以最大化的提高效率。 上面讨论的是位与(&)运算计算索引的方式，如果是取余：hashCode%length，则不需要考虑数组长度为2的n次幂，但是这种算法开销比较大，效率不高。

面试题：如果用户创建HashMap的时候输入的容量不是2的n次幂，会发生什么现象？ 会扩容到比输入容量稍大的2的n次幂的容量，具体做法是容量减1，然后进行右移1、2、4、8、16，每一次右移会执行或运算，得出的结果再进行下一次的右移、或运算，直到hashmap的最大容量2^30。这样可以保证即使用户输入不是2的2次幂，容量也被保证为2的n次幂。

面试题：如果用户创建HashMap的时候输入的容量不是2的n次幂，会发生什么现象？ 会扩容到比输入容量稍大的2的n次幂的容量，具体做法是容量减1，然后进行右移1、2、4、8、16，每一次右移会执行或运算，得出的结果再进行下一次的右移、或运算，直到hashmap的最大容量2^30。这样可以保证即使用户输入不是2的2次幂，容量也被保证为2的n次幂。

面试题：为什么链表长度大于等于8才转为红黑树，小于6又转化为链表的结构? 根据官方解释，根据统计学泊松分布的公式，假设在hashCode的离散性比较理想的情况，链表长度等于8的概率非常小，但是jdk无法保证用户计算hashCode的算法是能够保证理想的离散性的，因此基于空间和时间的考虑，选择了8这个数字作为threshold。 另外一种通俗的理解是如果长度为8，红黑树的平均查找长度为log(8)=3，链表的平均查找长度为n/2=4，对数开始比多项式效率高。如果链表长度为6，红黑树的平均查找长度为log(8)=2.6，链表的平均查找长度为n/2=3，虽然速度也很快，但是红黑树需要转化为树和生成树的时间并不会太短，因此综合考虑会选择8作为threshold，其实这也是泊松分布的具体表现。

面试题：为什么负载因子为0.75？ 负载因子决定HashMap中node数量达到整体的一定情况进行扩容，大量测试得出的结论0.75是一个折中、高效的选择。

面试题：HashTable和HashMap的区别？ HashTable不允许键为null，原因是HashTable在进行push操作的时候会直接调用key的hashCode方法，如果为null会报空指针异常，HashMap中对key为null的情况会把0的结果返回。

面试题：为什么进行hashCode调用完后还需要右移16位，取异或的结果？ 避免高位变化很大，低位变化很小的情况，在这种情况下很容易导致最后计算出的索引是大概率相同的，大大增加hash碰撞的概率。

4.扩容

resize()：扩容的核心，当数组中的节点个数大于等于数组长度*loadFactor、链表长度小于6并且数组长度小于64时会优先执行扩容操作，此操作比较耗时，一般在程序设计之处最好知道HashMap大小，尽量减少扩容次数。扩容的计算：数组长度n*2，然后执行hash & (n-1)。最后的结果只有两种：索引不变和原索引+旧数组的容量，这两种结果取决于hash & (n-1)的多出的1bit是1还是0，计算结果为0则是前者，为1则是后者。因此，jdk8以后，在扩容的时候不需要重新计算hash，只需要看旧数组容量的二进制那一位和hash按位与(&)的结果即可。计算过程和resize示意图如下：

5.遍历HashMap

分别遍历key和values import java.io.IOException; import java.util.HashMap; import java.util.Map; public class Test { public static void main(String[] args) throws IOException { Map<Integer, Integer> map = new HashMap<Integer, Integer>(); map.put(1, 10); map.put(2, 20); // 迭代键 for (Integer key : map.keySet()) { System.out.println("Key = " + key); } // 迭代值 for (Integer value : map.values()) { System.out.println("Value = " + value); } } } 使用Iterator迭代器迭代 import java.io.IOException; import java.util.HashMap; import java.util.Iterator; import java.util.Map; public class Test { public static void main(String[] args) throws IOException { Map<Integer, Integer> map = new HashMap<Integer, Integer>(); map.put(1, 10); map.put(2, 20); Iterator<Map.Entry<Integer, Integer>> entries = map.entrySet().iterator(); while (entries.hasNext()) { Map.Entry<Integer, Integer> entry = entries.next(); System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue()); } } } 通过get方式(不建议使用)

说明：根据阿里手册，不建议使用，因为迭代两次。keySet获取Iterator一次，还有通过get又迭代一次，降低性能

jdk8以后使用Map集合的默认方法 import java.io.IOException; import java.util.HashMap; import java.util.Map; public class Test { public static void main(String[] args) throws IOException { Map<Integer, Integer> map = new HashMap<Integer, Integer>(); map.put(1, 10); map.put(2, 20); map.forEach((k, v) -> System.out.println("key: " + k + " value:" + v)); } }