问题

HashMap、HashTable和TreeMap有什么不同

答案

• HashMap允许使用 null 值和 null 键，不保证映射的顺序恒久不变。 迭代HashMap 实例所需时间与其容量及当前关系数量大小成比例。HashMap 的实例有两个参数影响其性能：初始容量 和加载因子。容量是哈希表中桶【可以理解为分区】的数量，初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。默认加载因子为0.75是在寻求时空的平衡，该因子过大，则查询就慢，该因子过小，则需反复rehash。此实现不是同步的。若要实现HashMap同步，需要使用：

Map m = Collections.synchronizedMap(new HashMap(...));

• HashMap中设置值的过程如下：第一步首先将k,v封装到Node对象当中（节点）。第二步它的底层会调用K的hashCode()方法得出hash值。第三步通过哈希表函数/哈希算法，将hash值转换成数组的下标，下标位置上如果没有任何元素，就把Node添加到这个位置上。如果说下标对应的位置上有链表。此时，就会拿着k和链表上每个节点的k进行equal。如果所有的equals方法返回都是false，那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true，那么这个节点的value将会被覆盖。jdk7使用的是数组+链表来实现，而jdk8使用数组+链表+红黑树实现。那为什么要引入红黑树呢，原因就是哪怕将hash的碰撞降到最低，也不能避免链表会越来越长。
• HashTable与HashMap类似，但HashTable的大多数方法都是同步的，例如put和get两方法都被修饰了synchronized关键字。
• TreeMap实现了SortedMap，基于红黑树实现，使得containsKey、get、put 和 remove 操作提供log(n) 时间开销下的排序，即在这些方法执行时完成基于key的自然排序或者根据Comparator重写的方法进行自定义排序。此实现不是同步的，如要使得TreeMap同步，需要使用：

SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));