画重点，面试加分
先贴出HashMap源码普及一下几个概念：
public class HashMap<K,V>extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable{ // 默认的初始容量（容量为HashMap中桶的数目）是16，且实际容量必须是2的整数次幂。 static final int DEFAULT_INITIAL_CAPACITY = 16; // 最大容量（必须是2的幂且小于2的30次方，传入容量过大将被这个值替换） static final int MAXIMUM_CAPACITY = 1 << 30; // 默认加载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 存储数据的Entry数组，长度是2的幂。 // HashMap是采用拉链法实现的，每一个Entry本质上是一个单向链表 transient Entry[] table; // HashMap的大小，它是HashMap保存的键值对的数量 transient int size; // HashMap的阈值，用于判断是否需要调整HashMap的容量（threshold = 容量*加载因子） int threshold; // 加载因子实际大小 final float loadFactor; // HashMap被改变的次数 transient volatile int modCount;
通过以上源码可以看到在源码中定义了一下几个常量：
- 默认加载因子：这东西说白了就是用来划分整个HashMap容量的百分比，这里默认0.75就是说占用总容量的75%
- 默认初始容量：如果你不在构造函数中传值，new一个HashMap,他的容量就是2的4次方（16），并且增长也得是2的整数次方（幂）
- 阀值：首先这个值等于默认加载因子和初始容量的乘机；他的作用是用来预警的，如果HashMap中的容量超过这个阀值了，那就会执行扩容操作，低于则没事
很多人忽视的加载因子Load Factor
加载因子存在的原因，还是因为减缓哈希冲突，如果初始桶为16，等到满16个元素才扩容，某些桶里可能就有不止一个元素了。所以加载因子默认为0.75，也就是说大小为16的HashMap，到了第13个元素，就会扩容成32。
2.1 考虑加载因子地设定初始大小
相比扩容时只是System.arraycopy()的ArrayList，HashMap扩容的代价其实蛮大的，首先，要生成一个新的桶数组，然后要把所有元素都重新Hash落桶一次，几乎等于重新执行了一次所有元素的put。
所以如果你心目中有明确的Map 大小，设定时一定要考虑加载因子的存在。
建议你在知道你要存储的容量的时候，直接这样定义：
Map mapBest = new HashMap((int) ((float) 拟存的元素个数 / 0.75F + 1.0F));
这样一次到位，虽然存在些资源浪费，但是比起重新扩容还是效率高很多
Map map = new HashMap(srcMap.size())这样的写法肯定是不对的，有25%的可能会遇上扩容。
Thrift里的做法比较粗暴， Map map = new HashMap( 2* srcMap.size()), 直接两倍又有点浪费空间。
Guava的做法则是加上如下计算
(int) ((float) expectedSize / 0.75F + 1.0F);
2.2 减小加载因子
在构造函数里，设定加载因子是0.5甚至0.25。
如果你的Map是一个长期存在而不是每次动态生成的，而里面的key又是没法预估的，那可以适当加大初始大小，同时减少加载因子，降低冲突的机率。毕竟如果是长期存在的map，浪费点数组大小不算啥，降低冲突概率，减少比较的次数更重要。
3. Key的设计
对于String型的Key，如果无法保证无冲突而且能用==来对比，那就尽量搞短点，否则一个个字符的equals还是花时间的。
甚至，对于已知的预定义Key，可以自己试着放一下，看冲不冲突。比如，像”a1”,”a2”,”a3” 这种，hashCode是个小数字递增，绝对是不冲突的：）
看一下获取key对应value的源码
// 获取key对应的value public V get(Object key) { if (key == null) return getForNullKey(); // 获取key的hash值 int hash = hash(key.hashCode()); // 在“该hash值对应的链表”上查找“键值等于key”的元素 for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null; }
由源码可知，如果hashCode 不冲突，那查找效率很高，但是如果hashCode一旦冲突，叫调用equals一个字节一个自己的去比较
- 所以你把key设计的尽量短，一旦冲突也会少用点时间
- 建议采用String,Integer 这样的类作为键，原因如下：
特别是String，他是不可变的，也是final的，而且已经重写了equals 和hashCode 方法，这个和HashMap 要求的计算hashCode的不可变性要求不谋而合，核心思想就是保证键值的唯一性，不变性，
其次是不可变性还有诸如线程安全的问题，以上这么定义键，可以最大限度的减少碰撞的出现
转载整理自
网友评论