java数据结构之Map

偏执的太偏执、 2022-05-14 11:21 236阅读 0赞

Java中的List和Map是使用频率非常高的数据结构。这里介绍下常用的Map实现。  
先来看下类图：  
![76935559.jpg][]

## HashMap的实现原理 ##

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总结][ConcurrentHashMap]、[Java集合—ConcurrentHashMap原理分析][Java_ConcurrentHashMap]

## LinkedHashMap——有序的HashMap ##

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

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

public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
    }

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

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));
    }

输出如下：

hello->hello
    world->world
    !->!

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

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

错误信息：

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方法：

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时出错了。

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

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

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

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

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

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接口，所以会做一个转换，就出错了。

示例代码：

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：

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);
        }
    });

输出：

1001:王五
    1002:李四
    1003:张三

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

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

[76935559.jpg]: http://omh46px9n.bkt.clouddn.com/18-4-17/76935559.jpg
[HashMap]: http://tommy88.top/2018/03/20/HashMap%E7%9A%84%E5%AE%9E%E7%8E%B0%E5%8E%9F%E7%90%86%E5%88%86%E6%9E%90/
[ConcurrentHashMap]: http://www.importnew.com/22007.html
[Java_ConcurrentHashMap]: http://www.importnew.com/21786.html