理解Map

1.Map

Map用于保存具有映射关系的数据，因此Map集合中保存着两组值，一组值用于保存Map里的key，另外一组值用于保存Map里的value，key和value都可以是任何引用类型的数据。Map的key不允许重复，即同一个Map对象的任何两个key通过equals()方法比较总是返回false。

如果把Map里的所有key放在一起来看，它们就组成了一个Set集合(所有的key没有顺序，key和key之间不能重复)，实际上，Map确实包含了一个keySet()方法，用于返回Map里所有的key组成的Set集合。

如果把Map里的所有value放在一起看，它们又非常类似于一个List：元素与元素之间可以重复，每个元素可以根据索引来查找，只是Map中的索引不再使用整数值，而是以另一个对象作为索引。如果需要从Map中取出元素，需要提供该元素的key索引。因此，Map有时也被称为字典，或关联数组。

Map接口中定义的常用方法有：

这里要注意的是V put(K key, V value)方法，该方法用于给Map中添加新的键值对，如果放入重复的key时，新的value会覆盖原有的value；如果新的value覆盖了原有的value，该方法会返回被覆盖的value。当然，如果没有key重复，也就没有覆盖，该方法返回null。

测试如下：

public static void main(String[] args) {
    HashMap<String, String> hm = new HashMap<>();
    hm.put("a", "123");
    System.out.println(hm.put("b", "456"));
    System.out.println(hm.put("a", "789"));
}

输出如下：

null
123

第一次输出，并没有覆盖，所以方法返回null；第二次输出，由于Map中已经有了a这个键，所以原有的123被覆盖并返回。

2.HashMap与Hashtable

HashMap和Hashtable都是Map接口的典型实现类，它们之间的关系完全类似于ArrayList和Vector的关系：Hashtable是一个古老的Map实现类，它从JDK1.0起就出现了，当它出现时，Java还没有提供Map接口。

HashMap与Hashtable存在两点典型区别：

• 1.Hashtable是一个线程安全的Map实现，但HashMap是线程不安全的实现，所以HashMap比Hashtable的性能高一点；但如果有多个线程访问同一个Map对象时，使用Hashtable实现类会更好。
• 2.Hashtable不允许使用null作为key和value，但HashMap可以。

为了成功地在HashMap、Hashtable中存储、获取对象，用作key的对象必须实现hashCode()方法和equals()方法。

与HashSet集合不能保证元素顺序一样，HashMap和Hashtable也不能保证其中的key-value对的顺序。类似于HashSet，HashMap和Hashtable判断两个key相等的标准也是：两个key的hashCode值相等，两个key通过equals()方法比较返回true。

除此之外，HashMap和Hashtable中还包含一个containsValue()方法，用于判断是否包含指定的value。那么HashMap和Hashtable判断两个value相等的标准是什么呢？这个标准更简单一点：只要两个对象通过equals()方法比较返回true即可。

我们可以做如下测试：

class A {
    private int count;

    public A(int count){
        this.count = count;
    }

    // 根据count的值来判断两个对象是否相等
    public boolean equals(Object obj){
        if(this == obj){
            return true;
        }
        if(obj == null){
            return false;
        }
        if(this.getClass() != obj.getClass()){
            return false;
        }
        A a = (A)obj;
        return this.count == a.count;
    }

    // 根据count来计算hashCode值
    public int hashCode(){
        return this.count;
    }
}

class B{
    @Override
    public boolean equals(Object obj) {
        return true;
    }
}

public class HashtableTest {

    public static void main(String[] args) {
        Hashtable ht = new Hashtable<>();
        ht.put(new A(1000),"Java");
        ht.put(new A(2000),"Python");
        ht.put(new A(3000),new B());

        //由于Hashtable中有一个B对象，它与任何对象通过equals()方法比较都返回true
        // 所以这里不管测试的字符串是什么，它都会返回true
        System.out.println(ht.containsValue("123"));

        // 对于key来说，如果两个A对象的hashCode值相等，并且通过equals()方法比较返回true
        // 那么它们就是相等的，就是相同的key
        System.out.println(ht.containsKey(new A(1000)));
    }
}

程序输出：

true
true

1.因为HashMap、Hashtable保存key的方式与HashSet保存集合元素的方式完全相同，所以HashMap、Hashtable对key的要求与HashSet对集合元素的要求完全相同。
2.也就是说，当使用自定义类作为HashMap、Hashtable的key时，如果重写该类的equals(Object obj)和hashCode()方法，则应该保证两个方法的判断标准一致：当两个key通过equals()方法比较返回true时，两个key的hashCode()返回值也应该相同。

3.LinkedHashMap

HashSet有一个LinkedHashSet子类，HashMap也有一个LinkedHashMap子类。LinkedHashMap使用双向链表来维护key-value对的次序（其实只需要考虑key的次序），该链表负责维护Map的迭代顺序，迭代顺序与key-value对的插入顺序保持一致。

LinkedHashMap需要维护元素的插入顺序，因此性能略低于HashMap的性能；但因为它以链表来维护内部顺序，所以在使用迭代器访问全部元素时有比较好的性能。

public class LinkedHashMapTest {
    public static void main(String[] args) {
        LinkedHashMap<String, Integer> scores = new LinkedHashMap<>();

        scores.put("语文", 90);
        scores.put("数学", 100);
        scores.put("英语", 95);
        // 调用forEach()方法遍历scores里所有的key-value对
        scores.forEach((key,value) -> System.out.println(key + "-->" + value));
    }
}

程序输出：

语文-->90
数学-->100
英语-->95

4.SortedMap接口和TreeMap实现类

正如Set接口派生出SortedSet子接口，SortedSet接口有一个TreeSet实现类一样，Map接口也派生出一个SortedMap子接口，SortedMap接口也有一个TreeMap实现类。

TreeMap就是一个红黑树数据结构，每个key-value对即作为红黑树的一个节点。TreeMap存储key-value对时，需要根据key对节点进行排序。TreeMap可以保证所有的key-value对处于有序状态。TreeMap也有两种排序方式：

• 1.自然排序：TreeMap的所有key必须实现Comparable接口，而且所有的key应该是同一个类的对象，否则将会抛出ClassCastException异常。
• 2.定制排序：创建TreeMap时，传入一个Comparator对象，该对象负责对TreeMap中的所有key进行排序。采用定制排序不需要Map的key实现Comparable接口。

类似于TreeSet中判断两个元素相等的标准，TreeMap中判断两个key相等的标准是：两个key通过compareTo()方法返回0。

与TreeSet类似的是，TreeMap中也提供了一系列根据key顺序访问key-value对的方法：

针对这些方法做测试如下：

class R implements Comparable{

    int count;

    public R(int count) {
        this.count = count;
    }

    //根据count值判断两个对象是否相等
    @Override
    public boolean equals(Object obj) {
        if(this == obj) return true;
        if(obj == null || this.getClass() != obj.getClass()) return false;
        R r = (R)obj;
        return this.count == r.count;
    }

    // 根据count属性值来判断两个对象的大小
    @Override
    public int compareTo(Object o) {
        R r = (R)o;
        return this.count > r.count ? 1: this.count < r.count ? -1 : 0;
    }

    @Override
    public String toString() {
        return "R [count=" + count + "]";
    }
}

public class TreeMapTest {
    public static void main(String[] args) {
        TreeMap tm = new TreeMap<>();
        tm.put(new R(3),"Java");
        tm.put(new R(-5),"Python");
        tm.put(new R(9),"C++");

        System.out.println(tm);
        // 返回第一个键值对
        System.out.println(tm.firstEntry());
        // 返回最后一个键
        System.out.println(tm.lastKey());
        // 返回比new R(2)大的最小的key-value对
        System.out.println(tm.higherEntry(new R(2)));
        // 返回比new R(2)小的最大key值
        System.out.println(tm.lowerKey(new R(2)));
        // 返回key在new R(-1)和new R(4)之间的子Map
        System.out.println(tm.subMap(new R(-1), new R(4)));
    }
}

程序输出:

{R [count=-5]=Python, R [count=3]=Java, R [count=9]=C++}
R [count=-5]=Python
R [count=9]
R [count=3]=Java
R [count=-5]
{R [count=3]=Java}