HashMap 是无序的，TreeMap 可以按照 key 进行排序，LinkedHashMap 可以维护插入的顺序。

HashMap、TreeMap、LinkedHashMap的相同点 & 不同点

相同点

  • 三者在特定的情况下，都会使用红黑树；
  • 底层的 hash 算法相同；
  • 在迭代的过程中，如果 Map 的数据结构被改动，都会抛出 ConcurrentModificationException

不同点

  • HashMap 数据结构以数组为主，查询非常快，TreeMap 数据结构以红黑树为主，利用了红黑树左小右大的特点，可以实现 key 的排序，LinkedHashMap 在 HashMap 的基础上增加了链表的结构，实现了插入顺序访问和最少访问删除两种策略；
  • 由于三种 Map 底层数据结构的差别，导致了三者的使用场景的不同，TreeMap 适合需要根据 key 进行排序的场景，LinkedHashMap 适合按照插入顺序访问，或需要删除最少访问元素的场景，剩余场景使用 HashMap

  • 由于三种 Map 的底层数据结构的不同，导致上层包装的 api 略有差别

    Map 的 hash 算法

    一个优秀的 hash 算法应该有的特点

  • 快速性：速度快，效率高

  • 不可逆性
  • 敏感性
  • 低碰撞性

Java 中的 hash 算法

  • Object.hashCode()：直接获取内存地址
  • Integer.hashCode()：直接返回 IntValue
  • String.hashCode()：根据字符串生成 hashCode，保证字符串相同 hashCode 也相同
  • HashMap 类中的 hash 算法

HashMap 的 hash 算法如下：

  1. // Java 8 中的 hash()
  2. static final int hash(Object key) {
  3.     int h;
  4.     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  5. }
  7. // Java 7 中的 hash()
  8. final int hash(Object k) {
  9.     int h = 0;
  10.     if (useAltHashing) {
  11.         if (k instanceof String) {
  12.             return sun.misc.Hashing.stringHash32((String) k);
  13.         }
  14.         h = hashSeed;
  15.     }
  17.     h ^= k.hashCode();
  19.     // This function ensures that hashCodes that differ only by
  20.     // constant multiples at each bit position have a bounded
  21.     // number of collisions (approximately 8 at default load factor).
  22.     h ^= (h >>> 20) ^ (h >>> 12);
  23.     return h ^ (h >>> 7) ^ (h >>> 4);
  24. }
  26. key 对应的节点在数组中索引位置 index = (n - 1) & hash

这其实是个数学问题，首先计算出 key 的 hashCode，因为 key 是 Object，所以会根据 key 的不同类型进行 hashCode 的计算，接着计算 h ^ (h >>> 16) ，这么做是使大多数场景下，算出来的 hash 值比较分散。
hash 值算出来之后，要计算当前 key 在数组中的索引下标位置时，可以采用取模的方式，就是索引下标位置 index = hash 值 % 数组大小，这样做的好处，就是可以保证计算出来的索引下标值可以均匀的分布在数组的各个索引位置上，但取模操作对于处理器的计算是比较慢的
数学上有个公式，当 b 是 2 的幂次方时，a % b == a & (b-1)，所以此有了源码中的索引位置的计算方式

为什么不用 key % 数组大小，而是用 key 的 hash 值 % 数组大小。
答：如果 key 是数字，直接用 key % 数组大小是完全没有问题的，但我们的 key 还有可能是字符串，是复杂对象，这时候用字符串或复杂对象 % 数组大小是不行的，所以需要先计算出 key 的 hash 值。

计算 hash 值时，为什么需要右移 16 位
答：hash 算法是 h ^ (h >>> 16)，为了使计算出的 hash 值更分散，所以选择先将 h 无符号右移 16 位，然后再于 h 异或时，就能达到 h 的高 16 位和低 16 位都能参与计算，减少了碰撞的可能性。

为什么把取模操作换成了 & 操作
答：取模操作处理器计算比较慢，处理器对 & 操作就比较擅长，换成了 & 操作，为了提高处理器处理的速度。

为什么提倡数组大小是 2 的幂次方
答：因为只有数组大小是 2 的幂次方时，才能使 hash 值 % n(数组大小) == (n-1) & hash 公式成立。

解决 hash 冲突的办法

答：

  • 好的 hash 算法，细问的话复述一下上题的 hash 算法
  • 自动扩容，当数组快满时，采取自动扩容，可以减少 hash 冲突
  • hash 冲突发生时，采用链表来解决（拉链法）
  • hash 冲突严重时，链表自动转化成红黑树，提高遍历速度

网上列举的一些其它办法，如开放寻址法，尽量不要说，因为这些方法资料很少，实战用过的人更少

DTO 作为 Map 的 key 时，需要注意的点

答：DTO 就是一个数据载体，可以看做拥有很多属性的 Java 类，我们可以对这些属性进行 get()、set() 操作。
需要看是什么类型的 Map，
如果是 HashMap 的话，一定需要重写 equals() 和 hashCode()，因为在 get 和 put 时，需要通过 equals() 进行相等的判断；
如果是 LinkedHashMap 的话，和 HashMap 一样的；
如果是 TreeMap 的话，DTO 需要实现 Comparable 接口，因为 TreeMap 会使用 Comparable 接口进行判断 key 的大小。

Java8新增的Map的好用方法

具体介绍见 jkd_api 中 Map 接口的 default 方法