HashMap性能压榨指南（hashmap1.8）

HashMap是我们日常工作中最常用的一个数据结构之一。它的实现原理非常简单，内部是一个数组加链表的数据结构，用于对数据的存储，查找，删除等等。就像这样：

如果我问你HashMap中对数据存和获取的时间复杂度是多少？

我相信不少同学会脱口而出：O(1)啊，哈希不就是O(1)嘛？

那这个答案对吗？其实是不对的，或者说只对了一小半。为什么这样说呢？因为O(1)这个答案只有最好的情况才会出现，就是当完全没有哈希冲突的时候。这种情况下每个哈希桶中都只有一个值，只要通过哈希函数计算，就可以瞬间定位到目标元素的位置。

只可惜，O(1)只是理论上的奢望，哈希冲突才是生活的常态。

一句话，哈希冲突一直是HashMap的痛点，是通往高性能美好生活的主要阻碍。

简单来说，HashMap的性能低主要因为以下几点：

• 哈希冲突导致单个哈希桶元素数量过多。操作元素的时间复杂度甚至退化成O(N)，经红黑树改进后，也得O(logN)。
• 扩容，为啥扩容？还是为了降低哈希冲突！

问题找到了，也就是说，要提高HashMap的性能，主要可以从以下两方面入手：

1. 减少哈希冲突，使得元素在哈希桶中分布更加均匀。

那如何才能减少哈希冲突呢？

HashMap内部的哈希函数是这样的。

//n是内部数组的长度， hash是加入的key元素的hashcode码（经过二次处理过的）
i = (n - 1) & hash

这个位运算，本质上来说，就是一个取余运算，等价于：

i = hash % n;

这种求余运算的哈希函数，加入其中的元素值key的hashcode码呈递增状态，就会分布得越均匀。例如，HashMap内部数组长度为8时，加入key值hashcode为0-15的元素，分布是非常均匀的，如下:

这里我们可以得到什么启示呢？就是日常工作中，尽量使用HashCode递增的值作为key，例如递增的int值，这样可以尽可能减少哈希冲突。

我工作中遇到的问题是这样的，例如以下有一个属性枚举类型：

public enum AttributeType {
    TYPE1(1),
    TYPE2(2),
    TYPE3(3),
    TYPE4(4),
    ;
    int value;
    AttributeType(int value) {
        this.value = value;
    }
}

游戏中这样的属性类型枚举中的实例是非常多的，可以多达几百个。我们经常要以属性类型作为key去存储计算数据，这就涉及一个常见的选择，以下两种存储方式哪种好呢？

（1）Map<Integer, Long> attributeMap = new HashMap<>();
（2）Map<AttributeType, Long> attributeMap = new HashMap<>();

按照我们之前的理论，明显是第一种好的！因为这样key值是递增的，元素分布均匀，而第二种hashcode不一定递增，分布肯定不如第一种均匀。经过测试，结果实际上也验证了我的猜想。

看到这里，有的同学可能会觉得，有必要这样吹毛求疵吗？其实是有必要的，因为游戏中战斗计算时，这个Map结构的操作是极其频繁的，一点点优化，都可以获得很大的收益。

2. 创建Map时，指定好初始容量，防止扩容

工作中，我们常常有这样的代码：

Map<Integer, Long> attributeMap = new HashMap<>();
for (AttributeType type : values()) {
    long attributeValue = 1000;
    attributeMap.put(type.value, attributeValue);
}

如果不指定初始容量的话，很可能导致多次扩容，影响性能。所以我建议大家在知道元素数量的情况下，尽量指定初始容量值，公式如下：

initCapcity = size / 0.75 + 1;

这样就可以减少扩容带来的性能损耗了。