图解Map家族
目录
Map家族图谱
HashMap
设计目的
为put/get方法提供常量级别的时间复杂度。
图解
- 节点是红色或黑色。
- 根是黑色。
- 所有叶子都是黑色(叶子是NIL节点)。
- 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
使用场景
- 适合较大量数据的存储和查找。
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适应的场景:
- <1000对象;
- Map嵌套;
ArrayMap<String, String> map = new ArrayMap<>();
map.put("2", "深圳");
map.put("1", "北京");
遍历顺序:
{1=北京, 2=深圳}