引言
java集合框架图
基于Java集合框架图，本文针对Map集合的主要实现类从实现原理、特点、核心功能实现细节角度进行分析总结，目的是深入的了解其性能特点和适应场景，合理的优化使用；学习它们的架构设计思想和算法思想，编写更高效的代码。
HashMap的结构特点？
JDK中HashMap是一种将元素以Key-Value形式存储的非线程安全、自动扩容的集合。其特点是利用java对象的hashCode唯一性作为元素的key，基于数组结构，使用哈希函数（除留取余法，hash(key)%n，n为数组长度），将非固定长度的key，映射为数组下标。进而通过下标位置存储key对应的哈希值value。
可以说没有数组就没有哈希表。HashMap中的HashTable存储的元素是单链表，利用单链表解决哈希冲突，HashMap的HashTable是一个单链表数组结构。
HashMap
HashMap的哈希存储及查找原理？
首先来看下HashMap的key的hash计算方法
hash
如图，h>>>16将32位int值保留高16位，使用java对象hashCode异或操作，目的是使key值更随机。
然后，看下put()方法的具体实现，在此之前先了解下，Node结点实现：HashMap内部使用单链表来存储元素，其中hash/key/value均为链表结点的数据属性。而HashTable就是存储单链表的数组。
Node
其中627-628是在进行扩容判断，629判断当前结点不在hash表中，则创建结点放入HashTable中。（其中 (n -1) &hash 等价于 hash%n ，n为HashTable长度，利用二进制按位&操作代替取余操作来提高在HashTable中定位元素的查找效率）。如果当前结点在HashTable中存在，则通过key原值比较，进而判断HashTable中存在的结点和当前结点是否相同，如果不是相同结点，此时发生哈希冲突，则将当前结点也放入链表尾部即可。当链表长度大于规定阀值8时，JDK1.8将单链表转换为红黑树存储元素，从而避免极端情况下散列到HashTable一个桶内，造成单链表过长性能退化。
putVal
HashMap的初始化及其扩容机制？为什么每次扩容为旧容量的2倍，而不是1.5倍或其他倍数呢？
HashMap初始默认容量为16，初始扩容因子为0.75，初始化容量阀值=容量*扩容因子，即16*0.75=12。
扩容逻辑是：插入元素后，容量是否超过当前容量阀值。每次扩容为原容量的2倍，并重新分配内存，对旧hash表中的数据，重新计算hash值，并迁移到新的hash表中。也就是说当HashMap采用默认初始化后，新增元素超过12时，会进行第一次扩容，扩容后的容量为16*2。之后每次都扩容为原容量的2倍，也就是说HashMap的容量始终是2的N次幂。
HashMap定位和存储元素在hash表中的位置都是通过hash(key)%n实现的（除留取余法）这种方式如果除数不是2的N次幂，则无法利用位&操作，散列函数性能会大打折扣。这正是HashMap每次扩容为旧容量的2倍的原因。
由于HashMap扩容条件，会导致浪费其自身%25的存储空间，以牺牲空间的代价来降低哈希冲突的概率，以此达到空间换性能的做法。如果一个容器存储1万个元素，则需要扩容7次。那么如何降低扩容的性能损耗呢？如果事先能够预见数据量大小，可以指定容量的方式初始化固定容量的集合，以此降低不必要的被动扩容性能损耗。
下面对HashMap存储1万个元素，分别使用默认构造方法和指定容量（Capacity=10390，不扩容）方式构造，进行JMH吞吐量测试。从下图测试结果反馈，第一条指定容量比第二条未指定容量，ops高出不少。可见频繁被动扩容性能消耗不小，指定容量减少扩容可以提升性能。
HashMapJMH
小结：
HashMap基于数组支持按下标随机访问的特性，利用除留取余的哈希算法，将key映射到数组下标，并将key对应的value值存储到下标位置。HashMap采用链表法解决哈希冲突，同时引入红黑树优化链表过长导致的哈希碰撞攻击。通常情况下认为HashMap的查询、插入和删除操作的时间复杂度均为O(1)，适合快速精确无序查找的场景。
LinkedHashMap特点？为什么散列表经常和链表一起使用？
LinkedHashMap是通过双向链表和散列表这两种数据结构组合实现的。LinkedList中的“Linked”实际上不仅仅指它是通过链表法来解决哈希冲突的，它还指双向链表实现的缓冲LRU策略，使HashMap支持按插入顺序或操作顺序遍历的含义。
虽然散列表作为一种动态数据结构其插入、删除、查找操作的性能较高，但散列表中的数据都是通过散列函数之后，无序存储的。也就是说它不支持按某种顺序查找元素，为了使其有序遍历。每次遍历都要先排序的话，那效率势必会很低。为了解决这个问题，通常将散列表和链表（或者跳表）一起使用。
网友评论