Java中的List和Map是使用频率非常高的数据结构。这里介绍下常用的Map实现。
先来看下类图:

HashMap的实现原理

HashMap的实现原理参考:HashMap的实现原理

HashMap与HashTable的异同

HashTable与HashMap的存储机制基本相同,都是采用数组+链表。
不同点:
1.HashMap是非线程安全的,HashTable是线程安全的。它的大多数方法都加了synchronized。
2.HashMap允许key和value的值为null,HashTable不允许null值的存在。在HashTable的put方法中,如果V为null,直接抛出NullPointerException。
3.因为HashTable加了同步处理,所以HashMap效率高于HashTable。

HashTable与ConcurrentHashMap有何不同?

HashTable与ConcurrentHashMap都是线程安全的Map,有何不同?
HashTable使用的synchronized对方法加锁,实际锁住的是整个对象;而ConcurrentHashMap使用的是lock,这样在操作的时候锁住的不是这个对象。
而且ConcurrentHashMap采用了分段锁的设计,只有在同一个分段内才存在竞态关系,不同的分段锁之间没有锁竞争。相比于对整个Map加锁的设计,分段锁大大的提高了高并发环境下的处理能力。

ConcurrentHashMap使用多个子Hash表,即Segment。每个Segment是一个子Hash表。

ConcurrentHashMap要避免调用size()和containsValue()方法,会对整个Map进行扫描。

参考:ConcurrentHashMap总结Java集合—ConcurrentHashMap原理分析

LinkedHashMap——有序的HashMap

LinkedHashMap继承自HashMap,在HashMap的基础上增加了一个链表,用以存放元素的顺序。

LinkedHashMap提供2种类型的顺序:一是元素插入时的顺序;二是最近访问的顺序。
可以通过下面的构造函数指定排序行为:

1
2
3
4
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
}

accessOrder为true时表示按照元素访问时间排序;为false时表示按照元素插入的顺序排序。默认是false。
示例代码:

1
2
3
4
5
6
7
8
Map<String,String> map = new LinkedHashMap<>(16,0.75f,false);
map.put("hello","hello");
map.put("world","world");
map.put("!","!");
for (Iterator<String> iterator = map.keySet().iterator();iterator.hasNext();) {
    String key = iterator.next();
    System.out.println(key + "->" + map.get(key));
}

输出如下:

1
2
3
hello->hello
world->world
!->!

按照元素插入的顺序输出。
如果把上面的构造函数的最后一个参数accessOrder改为true,则在迭代器遍历时会报错。

1
Map<String,String> map = new LinkedHashMap<>(16,0.75f,true);

错误信息:

1
2
3
4
5
6
7
8
9
Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.LinkedHashMap$LinkedHashIterator.nextEntry(LinkedHashMap.java:390)
	at java.util.LinkedHashMap$KeyIterator.next(LinkedHashMap.java:401)
	at com.tommy.core.test.Test.main(Test.java:54)
	at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.lang.reflect.Method.invoke(Method.java:601)
	at com.intellij.rt.execution.application.AppMain.main(AppMain.java:140)

ConcurrentModificationException异常一般是在对集合迭代的过程中被修改时抛出。不仅仅是LinkedHashMap,所有的集合都不允许在迭代器中修改集合的结构。

因为我们将accessOrder改为true,表示按照最后访问的时间排序。在迭代器中遍历时会将访问的元素移动链表到尾部,发生了修改操作。

我们看下LinkedHashMap的get方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public V get(Object key) {
    Entry<K,V> e = (Entry<K,V>)getEntry(key);
    if (e == null)
        return null;
    e.recordAccess(this);
    return e.value;
}
void recordAccess(HashMap<K,V> m) {
    LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
    if (lm.accessOrder) {
        lm.modCount++;
        remove();
        addBefore(lm.header);
    }
}

可以看到,在get方法中调用了e.recordAccess()方法,recordAccess方法中如果accessOrder=true会有修改操作。所以在迭代器中循环get时出错了。

但是,如果把遍历的代码改一下,运行就正常了。

1
2
3
4
for (Iterator<Map.Entry<String,String>> iterator = map.entrySet().iterator();iterator.hasNext();) {
    Map.Entry<String,String> entry = iterator.next();
    System.out.println(entry.getKey() + "->" + entry.getValue());
}

没报错是因为没有对数据结构修改,因为直接调用的getKey和getValue方法。

TreeMap——另一种排序的Map

TreeMap实现了SortedMap接口,这意味着它可以对元素进行排序。

但TreeMap与LinkedHashMap的排序不同,它是通过指定的Comparator或Comparable确定。

为了确定Key的排序算法,可以通过2种方式制定:
1.在TreeMap的构造函数中注入一个Comparator

1
2
3
public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

2.使用实现了Comparable接口的Key。

如果不指定Comparable或Compartor,则在put时会报ClassCastException。

1
2
3
4
5
6
7
8
9
Exception in thread "main" java.lang.ClassCastException: com.tommy.core.test.Test$Student cannot be cast to java.lang.Comparable
	at java.util.TreeMap.compare(TreeMap.java:1188)
	at java.util.TreeMap.put(TreeMap.java:531)
	at com.tommy.core.test.Test.main(Test.java:62)
	at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.lang.reflect.Method.invoke(Method.java:601)
	at com.intellij.rt.execution.application.AppMain.main(AppMain.java:140)

因为构造函数没有传入Comparator,TreeMap认为你的Key(即这里的Student)应该实现了Comparable接口,所以会做一个转换,就出错了。

示例代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Student implements Comparable<Student>{
    private int id;
    private String name;
    public Student(int id, String name) {
        this.id = id;
        this.name = name;
    }
    @Override
    public int compareTo(Student o) {
        if (o == null || this.id > o.id
                ) {
            return 1;
        }
        if (this.id == o.id) {
            return 0;
        }
        return -1;
    }
}

TreeMap<Student,Student> map = new TreeMap<>();
Student s1 = new Student(1003,"张三");
Student s2 = new Student(1002,"李四");
Student s3 = new Student(1001,"王五");
map.put(s1,s1);
map.put(s2,s2);
map.put(s3,s3);
for(Iterator<Student> iterator = map.keySet().iterator();iterator.hasNext();) {
    Student student = iterator.next();
    System.out.println(student.id+":"+student.name);
}

或者TreeMap的初始化指定Comparator:

1
2
3
4
5
6
7
8
9
TreeMap<Student, Student> map = new TreeMap<>(new Comparator() {
    @Override
    public int compare(Object o1, Object o2) {
        Student s1 = (Student) o1;
        Student s2 = (Student) o2;
        boolean f1 = s1 == null && s2 == null;
        return (f1 || s1.id == s2.id) ? 0 : (s1.id > s2.id ? 1 : -1);
    }
});

输出:

1
2
3
1001:王五
1002:李四
1003:张三

此外,TreeMap还提供了一系列有用的方法,用于获取大于,小于,以及2个Key直接的子Map的功能。

如果需要使用Map,并且需要实现排序的功能,建议使用TreeMap。