高性能场景下，HashMap的优化使用建议

   <p>如果不追求性能，这篇文章可以不看的，JDK本身已写得足够优秀，大家随便用就好。</p>    <h3><strong>1. HashMap 在JDK 7 与 JDK8 下的差别</strong></h3>    <p>顺便理一下HashMap.get(Object key)的几个关键步骤，作为后面讨论的基础。</p>    <p><strong>1.1 获取key的HashCode并二次加工</strong></p>    <p>因为对原Key的hashCode质量没信心，怕会存在大量冲突，HashMap进行了二次加工。</p>    <p>JDK7的做法：</p>    <p>h ^= (h >>> 20) ^ (h >>> 12);</p>    <p>return h ^ (h >>> 7) ^ (h >>> 4);</p>    <p>JDK8 因为对自己改造过的哈希大量冲突时的红黑树有信心，所以简单一些，只是把高16位异或下来。</p>    <p>return h ^ (h >>> 16);</p>    <p>所以即使Key比较均匀无哈希冲突，JDK8也比JDK7略快大原因大概于此。</p>    <p>顺便科普一下，Integer的HashCode就是自己，Long要把高32位异或下来变成int， String则是累计结果＊31＋下一个字符，不过因为String是不可变对象，所以生成完一次就会自己cache起来。</p>    <p><strong>1.2 落桶</strong></p>    <p>index = hash & (array.length-1);</p>    <p>桶数组大小是2的倍数的好处，通过一次&就够了，而不是代价稍大的取模。</p>    <p><strong>1.3 最后选择Entry</strong></p>    <p>判断Entry是否符合，都是首先哈希值要相等，但因为哈希值不是唯一的，所以还要对比key是否相等，最好是同一个对象，能用＝＝对比，否则要走equals()。 比如String，如果不是同一个对象，equals()起来要一个个字符做比较也是挺累的。</p>    <p>if (e.hash == hash && ((k = e.key) == key || key.equals(k)))</p>    <p>return e.value;</p>    <p>更累的是存在哈希冲突的情况，比如两个哈希值取模后落在同一个桶上，或者两条不同的key有相同的哈希值。</p>    <p>JDK7的做法是建一条链表，后插入的元素在上面，一个个地执行上面的判断。</p>    <p>而JDK8则在链表长度达到8，而且桶数量达到64时，建一棵红黑树，解决严重冲突时的性能问题。</p>    <h3><strong>2. 很多人忽视的加载因子Load Factor</strong></h3>    <p>加载因子存在的原因，还是因为减缓哈希冲突，如果初始桶为16，等到满16个元素才扩容，某些桶里可能就有不止一个元素了。所以加载因子默认为0.75，也就是说大小为16的HashMap，到了第13个元素，就会扩容成32。</p>    <p><strong>2.1 考虑加载因子地设定初始大小</strong></p>    <p>相比扩容时只是System.arraycopy()的ArrayList，HashMap扩容的代价其实蛮大的，首先，要生成一个新的桶数组，然后要把所有元素都重新Hash落桶一次，几乎等于重新执行了一次所有元素的put。</p>    <p>所以如果你心目中有明确的Map 大小，设定时一定要考虑加载因子的存在。</p>    <p>Map map = new HashMap(srcMap.size())这样的写法肯定是不对的，有25%的可能会遇上扩容。</p>    <p>Thrift里的做法比较粗暴， Map map = new HashMap( 2* srcMap.size()), 直接两倍又有点浪费空间。</p>    <p>Guava的做法则是加上如下计算</p>    <p>(int) ((float) expectedSize / 0.75F + 1.0F);</p>    <p><strong>2.2 减小加载因子</strong></p>    <p>在构造函数里，设定加载因子是0.5甚至0.25。</p>    <p>如果你的Map是一个长期存在而不是每次动态生成的，而里面的key又是没法预估的，那可以适当加大初始大小，同时减少加载因子，降低冲突的机率。毕竟如果是长期存在的map，浪费点数组大小不算啥，降低冲突概率，减少比较的次数更重要。</p>    <h3><strong>3. Key的设计</strong></h3>    <p>对于String型的Key，如果无法保证无冲突而且能用==来对比，那就尽量搞短点，否则一个个字符的equals还是花时间的。</p>    <p>甚至，对于已知的预定义Key，可以自己试着放一下，看冲不冲突。比如，像”a1”,”a2”,”a3” 这种，hashCode是个小数字递增，绝对是不冲突的：）</p>    <h3><strong>4. EnumMap</strong></h3>    <p>对于上面的问题，有些同学可能会很冲动的想，这么麻烦，我还是换回用数组，然后定义一下下标的常量算了。其实不用自己来，EnumMap就是可读性与性能俱佳的实现。</p>    <p>EnumMap的原理是，在构造函数里要传入枚举类，那它就构建一个与枚举的所有值等大的数组，按Enum. ordinal()下标就能访问数组。</p>    <p>美中不足的是，因为要实现Map接口，而 V get(Object key)中key是Object而不是泛型K，所以安全起见，它每次访问都要先对Key进行类型判断。在JMC里录得不低的采样命中频率。所以也可以自己再port一个类出来，不实现Map接口，或者自己增加fastGet(),fastPut()的函数。</p>    <h3><strong>5. IntObjectHashMap</strong></h3>    <p>Netty以及其他 <a href="/misc/goto?guid=4959708176378817760" rel="nofollow,noindex">FastUtils</a> 之类的原始类型map，都支持key是int或 long。但两者的区别并不仅仅在于int 换 Integer的那点空间，而是整个存储结构和Hash冲突的解决方法都不一样。</p>    <p>HashMap的结构是 Node[] table; Node 下面有Hash，Key，Value，Next四个属性。</p>    <p>而IntObjectHashMap的结构是int[] keys 和 Object[] values.</p>    <p>在插入时，同样把int先取模落桶，如果遇到冲突，则不采样HashMap的链地址法，而是用开放地址法（线性探测法）index＋1找下一个空桶，最后在keys[index]，values[index]中分别记录。在查找时也是先落桶，然后在key[index++]中逐个比较key。</p>    <p>所以，对比整个数据结构，省的不止是int vs Integer，还有每个Node的内容。</p>    <p>而性能嘛，IntObjectHashMap还是稳赢一点的，随便测了几种场景，耗时至少都有24ms vs 28ms的样子，好的时候甚至快1/3。</p>    <h3>优化建议</h3>    <ol>     <li>考虑加载因子地设定初始大小</li>     <li>减小加载因子</li>     <li>String类型的key，不能用==判断或者可能有哈希冲突时，尽量减少长度</li>     <li>使用定制版的EnumMap</li>     <li>使用IntObjectHashMap</li>    </ol>    <p> </p>    <p>来自：http://calvin1978.blogcn.com/articles/hashmap.html</p>    <p> </p>