图解Map家族

目录

• Map家族图谱

• HashMap

  1. 设计目的
  2. 图解
  3. 使用场景

• LinkedHashMap

  1. 设计目的
  2. 图解
  3. 使用场景

• ConcurrentHashMap

  1. 设计目的
  2. 图解
  3. 使用场景

• TreeMap

  1. 设计目的
  2. 图解
  3. 使用场景

• ArrayMap

  1. 设计目的
  2. 图解
  3. 使用场景

• Map的选择总结

Map家族图谱

HashMap

设计目的

为put/get方法提供常量级别的时间复杂度。

图解

红黑树(维基百科)

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

使用场景

1. 适合较大量数据的存储和查找。

HashMap<String, String> map = new HashMap<>();
map.put("2", "深圳");
map.put("1", "北京");

遍历顺序：

{1=北京, 2=深圳}

LinkedHashMap

设计目的

在HashMap的基础上提供按插入顺序迭代的特性。

图解

LinkedHashMap数据结构和HashMap基本一致，不同的是多了一个双向链表结构：

使用场景

如果期望遍历顺序和插入顺序一致，则可用LinkedHashMap。

HashMap<String, String> map = new LinkedHashMap<>();
map.put("2", "深圳");
map.put("1", "北京");

遍历顺序：

{2=深圳, 1=北京}

ConcurrentHashMap

设计目的

线程安全的HashMap。

图解

和HashMap一样。

使用场景

并发环境下使用。

ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();
map.put("2", "深圳");
map.put("1", "北京");

遍历顺序：

{1=北京, 2=深圳}

TreeMap

设计目的

按key排序。

图解

使用场景

需要按key排序。

TreeMap<String, String> map = new TreeMap<>();
map.put("c", "重庆");
map.put("b", "北京");
map.put("a", "安庆");

遍历顺序：

{a=安庆, b=北京, c=重庆}

String实现了Comparable接口：

public interface Comparable<T> {
  public int compareTo(T o);
}

"a".compareTo("b") == -1;
"b".compareTo("a") == 1;
"a".compareTo("a") == 0;

或者使用Comparator作为构造参数：

    TreeMap<MyObject, String> map = new TreeMap<>(new Comparator<MyObject>() {
        @Override
        public int compare(MyObject o1, MyObject o2) {
            if (o1 == o2) {
                return 0;
            }
            if (o1 == null) {
                return -1;
            }
            if (o2 == null) {
                return 1;
            }
            return o1.i - o2.i;
        }
    });
    map.put(new MyObject(3), "3");
    map.put(new MyObject(1), "1");
    map.put(new MyObject(2), "2");

    static class MyObject {
        private int i;

        public MyObject(int i) {
            this.i = i;
        }

        @Override
        public String toString() {
            return "MyObject{" +
                    "i=" + i +
                    '}';
        }
    }

map.toString()输出：

{MyObject{i=1}=1, MyObject{i=2}=2, MyObject{i=3}=3}

ArrayMap

设计目的

more memory efficient，比HashMap更省内存，但是查找效率比HashMap低，时间换空间。

图解

使用两个数组，一个int数组存放每个Item的hash值，一个Object数组存放键值对：

    int[] mHashes;
    Object[] mArray;

使用场景

因为数组的插入、删除、扩容效率低，ArrayMap适应的场景：

1. <1000对象；
2. Map嵌套；

ArrayMap<String, String> map = new ArrayMap<>();
map.put("2", "深圳");
map.put("1", "北京");

遍历顺序：

{1=北京, 2=深圳}

Map的选择总结