Map是映射表的实现，是关联数组，维护着键与值的关联关系，因此可以根据键找到对应的值。
Java中有几种不同的Map实现，体现了各自不同的优势，或者是注重查找性能的HashMap、或者注重线程安全的ConcurrentHashMap，亦或Key有序排列的TreeMap等等。
而本节要讲的正是HashMap，是基于散列表的实现，插入和查询“键值对”操作具有近似O(1)的时间复杂度，并提供了通过调整容量和负载因子的手段来优化Map的性能。
HashMap的实现是数组+链表，很是简单，本文就不够多赘述，而是侧重从工程实践出发，陈述些HashMap使用的注意点或容易忽视且容易想当然的出错点。
null的处理
编程中，最长见的异常，就有NPE（NullPointerException ），那么HashMap是如何处理key或者value为null的情况呢？
1. Key为null
在HashMap中 ,Key是用来定位数组索引的，若Key为Null，则索引为0，也就是说键值对会放到数组的第一个桶位，若被占据，则链表链接，插入的逻辑和非null一模一样。
2. value为null
插入其实就是寻找位置的过程，此过程value不起任何作用。但是如果使用putIfAbsent()（JDK1.8之后）方法，就有需要注意的地方了。如果仅从字面上理解，可能会认为，如果通过key查找不到相等的元素，就插入新元素，反之，则不插入。其实不然，此方法解读应该是：元素不存在则作为新元素插入，当元素存在但是value==null时，也替换value值。
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
}
定位算法
HashMap中数组下标的计算并不是通过hash%length，而是(length - 1) & hash（两个数与计算，最终的结果肯定小于或者等于最小的那个值，最后肯定不越界）。这种方式明细不直观，不符合常规思维，难道是这种方式有更优的性能吗？
不妨用JMH微机准测试下：
static int length = 32;
@Benchmark
public void wellHelloThere() {
int i = RandomUtils.nextInt() % length;
}
@Benchmark
public void wellHelloThere1() {
int i = RandomUtils.nextInt() & (length - 1);
}
public static void main(String[] args) throws RunnerException {
Options opt = new OptionsBuilder()
.include(JMHTest.class.getSimpleName())
.forks(1)
.mode(Mode.Throughput)
.warmupIterations(2)
.measurementIterations(2)
.build();
new Runner(opt).run();
}
我的机器上执行，吞吐量ops几乎相等，这几乎可以排除性能的原因，那到底有何用意？下面详细分析。
数组扩容
HashMap有两个重要的属性，容量和负载因子。容量为数组的长度，而负载因子是一个衡量什么时候数组扩容的指标，默认值为0.75。
由数组容量和负载因子计算出的扩容阈值Threshold是最终的度量，当Map中元素数量大于Threshold时，此时HashMap需要实例化新数组（容量为原来2倍）然后把老Map的元素放到新的Map中，可以肯定，这个过程是整个HashMap中最耗时的，涉及所有元素的位置调整。
元素转移最简单的思路可能就是将所有的元素重新调用put方法，这会重新hash计算，定位桶位，遍历链表，有严重的性能问题，那么实际的操作又是怎样的呢？
扩容实现
HashMap底层数组长度始终是2的次方，不管你初始化设置数组容量为多少，例如：赋值为7，实际则是8，赋值为17，则为32。
下图展示扩容重新下标计算：
所有，只需要把原数组每个节点的链表按照高位是否为1进行拆分为2个链表，高位为1的链接到新的位置，也就是（原位置+原数组长度），为0的链接到新数组中原来的位置。
从而得出结论，(length - 1) & hash的算法选择是为了降低扩容时的性能损耗考虑的。
初始容量和负载因子对性能的影响
初始容量
当HashMap元素数量达到阈值，rehashing就会发生，频繁的发生会造成很大的开销。选择合适的初始容量将会很大程度上减少rehashing的发生，会改善HashMap的写入性能。
凡是有两面性，如果容量很大，且元素很少时，迭代操作将会产生额外的开销，所以当需要经常的进行迭代操作，就需要节点分布适当的紧促了，也就是说初始容量不能过大。
负载因子
过大的负载因子会减少空间的使用，但会造成查询（包括get和put）的耗时增加，默认值0.75是考虑了空间成本和时间成本后的一种折中方案，是一权衡。如果过小，也会造成迭代操作的消耗增加。
线程是否安全
HashMap是非线程安全的，多线程访问时如果有一个线程是写操作，则需要进行外部同步操作，否则其他线程将观察到对象内部的不一致状态，或者写入操作根本就不能被其他线程看见。
在多线程环境下，应该使用同步的Map，最好使用ConcurrentHashMap，而不是包装 Collections.synchronizedMap(new HashMap(...))以及Hashtable。
fail-fast
如同其他的非并发容器一样，HashMap的遍历也是快速失败机制，当iterator被创建后，任何对于底层数据结构的改变（put，remove）都可能会导致 ConcurrentModificationException异常的产生，由于没有使用同步，所有异常并不是一定会产生，这只是提供一种定位bug的参考。
与Hashtable区别
Hashtable是线程安全的，而HashMap并不是，在单线程环境下HashMap性能更优，毕竟锁是有开销的。
Hashtable不允许key或者value为null，HashMap则可以。
以上大概就是实际使用中需要了解，也需要注意的点了，为了代码的健壮，理解原理还是必要的。
网友评论