前言

在面试与被面之间游荡，把面试作为一项事情来做。

营养早餐

HashMap、Hashtable和TreeMap的区别

都实现了Map接口，（Key，Value）元组存储逻辑概念，内部采用Hash（rehash）算法提供高效的访问速度。
Hash的计算依赖于Key的hashCode和equals实现。
HashMap允许null作为Key和Value出现，而Hashtable不允许，对于null键值会抛异常。（补充HashMap的null键值对应的value会被存储到内部条目Array的0位，业务层面可以作为默认值的用途来使用，个人意见是不建议使用，使用业务含义清晰的Key常量作为默认值也许会是更好的选择）。
Hashtable的方法是线程安全的，内部方法之间使用Synchronized同步保护；而HashMap和TreeMap需要使用者自己保障线程安全机制。
因为线程机制的原因，Hashmap的操作会比Hashtable更高效一些（对于Web环境编程的小白来说，正常业务上，建议直接使用Hashtable，除非遇到性能集中爆发的地方，再考虑HashMap吧。补充，Java5提供了一个ConcurrentHashMap，没有太多调查和详细对比，从JDK的API文档来看，是建议使用这个类替代Hashtable的）。
Hashtable和HashMap的iterator、keySet()、values()都是（类）视图方式返回，即fail-fast模式，这种模式下，除非用返回对象直接remove来变更Map，其他方式或进程对Map的修改，都会在下一次hasNext或者next方法的时候（有可能会）触发ConcurrentModificationException。Hashtable提供的keys()和elements()返回的Enumeration不是fail-fast模式的视图化操作模式，是clone模式。
迭代访问数据的顺序时，HashMap和Hashtable不保证数据的顺序，并且不能保证数据顺序根据时间保持不变；TreeMap能够根据键值的比较器迭代访问整个条目。
对于TreeMap，如果比较器不允许空值，使用null的Key会引发异常。
三个详细比较

                 | HashMap | Hashtable | TreeMap
-------------------------------------------------------
iteration order  | no      | no        | yes
null key-value   | yes-yes | no-no     | no-yes
synchronized     | no      | yes       | no
time performance | O(1)    | O(1)      | O(log n)
implementation   | buckets | buckets   | red-black tree

fail-fast与fail-safe

这是对Java的Collections相关类的操作接口的一个实现和使用概念；
白话来说，fail-fast是以View（视图）的模式对原有Collection数据的访问，这个时候除了直接用View（通常是Iterator接口）进行remove对象，其他方式对原有Collection的增删改都可能会触ConcurrentModificationException](https://docs.oracle.com/javase/8/docs/api/java/util/ConcurrentModificationException.html)。
而fail-safe则不是以View模式，而是以Clone模式。
fail-fast能够访问到最新的数据内容；fail-safe只能访问到clone时点的数据。
fail-fast通过算法框架控制访问，没有空间需求；fail-safe会clone数据，有空间需求，对于大的数据集合，需要注意。
简单的来说java.util下面的Collection对象都是使用fail-fast模式（不完全准确，个别特殊接口除外，例如Hashtable的keys()和elements()接口），常见例如：HashMap、Vector、ArrayList、HashSet；java.util.concurrent包下都是用fail-safe模式，例如：CopyOnWriteArrayList、ConcurrentHashMap。

红黑树（Red-black Tree）

红黑树（Red–black tree）同AVL（根据发明者Adelson-Velsky 和 Landis命名）都是一种自平衡二叉查找树，都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。除了O(log n)的时间之外，红黑树的持久版本对每次插入或删除需要 O(log n)的空间。

红黑树的特点：

节点是红色或黑色。
根是黑色。
所有叶子都是黑色（叶子是NIL节点）。
每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

这些约束确保了红黑树的关键特性：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

Map相关常用操作

遍历数据

for(Entry entry: map.entrySet()) {
  // get key
  K key = entry.getKey();
  // get value
  V value = entry.getValue();
}

Iterator itr = map.entrySet().iterator();
while(itr.hasNext()) {
  Entry entry = itr.next();
  // get key
  K key = entry.getKey();
  // get value
  V value = entry.getValue();
}

根据Key排序（需要业务保障Key不能出现null）

List list = new ArrayList(map.entrySet());
Collections.sort(list, new Comparator() {
 
  @Override
  public int compare(Entry e1, Entry e2) {
    return e1.getKey().compareTo(e2.getKey());
  }
});

使用TreeMap排序

SortedMap sortedMap = new TreeMap(new Comparator() {
 
  @Override
  public int compare(K k1, K k2) {
    return k1.compareTo(k2);
  }
});
sortedMap.putAll(map);

根据Value进行排序

List list = new ArrayList(map.entrySet());
Collections.sort(list, new Comparator() {
 
  @Override
  public int compare(Entry e1, Entry e2) {
    return e1.getValue().compareTo(e2.getValue());
  }
 
});

静态Map

public class Test {
 
  private static final Map map;  //并能真的内容静态，使用的代码仍然能够使用put方法操作Map对象的内容
  static {
    map = new HashMap();
    map.put(1, "one");
    map.put(2, "two");
  }
}

public class Test {
 
  private static final Map map;
  static {
    Map aMap = new HashMap();
    aMap.put(1, "one");
    aMap.put(2, "two");
    map = Collections.unmodifiableMap(aMap);  //固化保护Map的内容是静态
    						//如果使用put方法，将会抛出UnsupportedOperationException
  }
}

双向映射Map

有时，我们需要一组键对，互相映射，允许通过Key查找，也允许通过Value“反向查找”。JDK不支持双向映射，需要使用两个Map对象来进行保存和处理。

Apache Common Collections 和 Guava 的 BidiMapand BiMap都实现了这类功能。

Map拷贝

多数Map实现类都实现了使用构造方法，传入另外一个Collection对象来实现数据的内容的复制，但是这个复制不是同步的，会出现上面的fail-fast问题（TODO 需要探究或验证）。

正确的用法是使用Collections.synchronizedMap()。

空Map

很少会有需要，但是某个时候调用一些接口需要Map，但是不需要数据的时候创建一个空Map也是需要的。

1
2
3

map = Collections.emptyMap();  //返回的是内容也不可变的Map

map = new HashMap();

LinkedHashMap

同TreeMap和HashMap一样，特殊的是其迭代顺序是其插入的顺序；并且根据这个博客来看，每次通过Get操作访问其内的元素，会把其访问的元素放到最尾的地方，改变迭代的顺序（如下示例验证）。

import java.util.LinkedHashMap;
import java.util.Set;

import org.springframework.util.Assert;

public class LinkedHashMapTest {

    public static void main(final String[] args) {
        final LinkedHashMap<Integer, String> map = new LinkedHashMap<>(16, .75f, true);
        map.put(1, null);
        map.put(2, null);
        map.put(3, null);
        map.put(4, null);
        map.put(5, null);

        final Set<Integer> keys = map.keySet();
        Assert.isTrue("[1, 2, 3, 4, 5]".equals(keys.toString()), "");

        map.get(4);
        Assert.isTrue("[1, 2, 3, 5, 4]".equals(keys.toString()), "");

        map.get(1);
        Assert.isTrue("[2, 3, 5, 4, 1]".equals(keys.toString()), "");

        map.get(3);
        Assert.isTrue("[2, 5, 4, 1, 3]".equals(keys.toString()), "");

        System.out.println("OK");
    }
}

其时间复杂度，同HashMap一样，内部使用buckets实现，但是其迭代的时间复杂度因为有Link的存在，仅与其元素个数有关，而HashMap的迭代时间复杂度跟其容量有关。

~黑哈瑞之家~

面试故事-Java的Map篇

前言