Java中Map

Java从入门到精（Java数据结构--Map集合）
Map接口说明(双列集合)
Map接口主要提供的方法
entrySet的使用
实现遍历map集合
实现类HashMap
说明
实现类Hashtable
说明（HashMap，Hashtable的一些区别对比）
实现类LinkedHashMap
说明
实现类TreeMap
说明
于是我做了一个sb的自排序（泛型是不能随便传的。大佬为我指点迷津）
我自己做了一部分查阅了解（我看了一些源码）
Map接口说明(双列集合)

JavaApi对Map接口作了部分概述

将键映射到值的对象。一个映射不能包含重复的键；每个键最多只能映射到一个值。
Map 接口提供三种collection 视图，允许以键集、值集或键-值映射关系集的形式查看某个映射的内容。映射顺序 定义为迭代器在映射的 collection 视图上返回其元素的顺序。某些映射实现可明确保证其顺序，如 TreeMap 类；另一些映射实现则不保证顺序，如 HashMap 类。

完整的接口定义为：

public interface Map<K,V>
1
接口很多是定义一些未实现的方法，在jdk8之前接口是不可以写实现方法的，但是后面的版本是可以实现的。并且定义的一些没有实现的方法是供后面的实现类使用的。
通常接口也就定义了一些方法。
jdk8后面使用到了default修饰，使得接口可以实现方法。

Map集合是一个双列集合，当然是相对于Collection而言。很显著的特点就是Collection是单列的，只能直接存放值，在Map这个集合上面可以有key(键)和value(值)

API明确说明了这个key和value的关系，按照映射来说其实就是一种单射的关系。

主要提供的基本方法如下

Map接口主要提供的方法

说明一下entrySet()方法

首先需要了解到的就是Entry是Map中的一个内部类，查看Map源码就可以查找到。

可以了解到，其实是映射到了key,和value。所以其实也就可以认为Map.Entry里面具有getKey()和getValue（）的方法。

entrySet的使用
在Map中看一下entrySet()方法，我们得到的信息如下：

说明了entrySet当然也就键值组成，同时里面包装的类型也就是Map.Entry。
同时我们可以得出entrySet实现了Set接口。
既然entrySet里面是Map.Entry类型，而Entry提供了获取键值的方法。那么其实我们可以使用entrySet实现对map的遍历。

我们可以这样（演示一下如何使用）

package java_practice;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class Map_demo {

public static void main(String args[])
{
    Map<String, String> map = new HashMap<String,String>();
    map.put("Hello","world");
    map.put("let","go");
    map.put("all","right");
    Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();
    while(it.hasNext())
    {
       // System.out.println(it.next());
        Map.Entry<String, String> entry = it.next();
        System.out.println(entry.getKey()+entry.getValue());
    }


}

}

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
实现遍历map集合
第一种就是上面配合迭代器进行遍历，另外我们还可以采用增强for循环

package java_practice;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

public class Map_demo {

public static void main(String args[]) {
    Map<String, String> map = new HashMap<String, String>();
    map.put("Hello", "world");
    map.put("let", "go");
    map.put("all", "right");

// Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();
// while(it.hasNext())
// {
// // System.out.println(it.next());
// Map.Entry<String, String> entry = it.next();
// System.out.println(entry.getKey()+entry.getValue());
// }

    Set<Map.Entry<String, String>> entries = map.entrySet();
    for (Map.Entry<String, String> entry : entries) {
        System.out.println(entry.getKey() + entry.getValue());
    }

}

}

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

还有一种就是通过keyset()进行获取键，然后用map.get()获取键对应的值，这个非常简单方便。

package java_practice;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

public class Map_demo {

public static void main(String args[]) {
    Map<String, String> map = new HashMap<String, String>();
    map.put("Hello", "world");
    map.put("let", "go");
    map.put("all", "right");

// Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();
// while(it.hasNext())
// {
// // System.out.println(it.next());
// Map.Entry<String, String> entry = it.next();
// System.out.println(entry.getKey()+entry.getValue());
// }
// Set<Map.Entry<String, String>> entries = map.entrySet();
// for (Map.Entry<String, String> entry : entries) {
// System.out.println(entry.getKey() + entry.getValue());
// }

    for(String key:map.keySet())
    {
        System.out.println(key+map.get(key));
    }
}

}

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

当然你也可以直接去map.values()进行遍历值

实现类HashMap
说明
JavaApi里面的部分如下

基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变
在线程同步上面，也有说明
注意，此实现不是同步的。如果多个线程同时访问一个哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须 保持外部同步。

HashMap作为实现类，我们来看它的完整定义

public class HashMap<K,V>extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable
1
数据结构

HashMap的底层数据结构是数组加链表，这种结构也可以认为是一种列表散列。
这种数据结构决定了HashMap的某些特性
比如在获取键值以及添加的速度是比较快的，也就是存储和查找比较方便的。有关hash的说明，已经在Collection集合中有部分概述，所以就不再赘述。

同时HashMap是一种无序的散列表，也就是说，并不会记录插入的顺序。简单演示一下说明。

package java_practice;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

public class Map_demo {

public static void main(String args[]) {

// Map<String, String> map = new HashMap<String, String>();
// map.put("Hello", "world");
// map.put("let", "go");
// map.put("all", "right");

    Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();
    while(it.hasNext())
    {
       // System.out.println(it.next());
        Map.Entry<String, String> entry = it.next();
        System.out.println(entry.getKey()+entry.getValue());
    }
    Set<Map.Entry<String, String>> entries = map.entrySet();
    for (Map.Entry<String, String> entry : entries) {
        System.out.println(entry.getKey() + entry.getValue());
    }

// for(String key:map.keySet())
// {
// System.out.println(key+map.get(key));
// }

    HashMap<String, String> hm = new HashMap<String,String>();
    hm.put("Hello","world");
    hm.put("blos","jgdabc");
    hm.put("java","javase");
    System.out.println(hm);
}

}

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
32
33
34
35
36

可以看到它是不会记录你插入的顺序的。

同样的遍历方式不再赘述。与上相同。

忍不住去看了一点点源码

单单从keySet方法我们就可以发现，其实HashMap的key是Set类型，Set类型的一个特性就是不允许重复。
所以Key也是不允许重复的。

主要的方法也就这些，entrySet()已经在map中说明了，HashMap实现了Map的全部方法。当然，同样也可以去用entrySet进行遍历。

所以也同样Key对应类一定重写了hashCode和equals方法。

实现类Hashtable
说明（HashMap，Hashtable的一些区别对比）
完整的类定义

// An highlighted block
public class Hashtable<K,V>extends Dictionary<K,V>implements Map<K,V>, Cloneable, Serializable
1
2
摘录api部分

此类实现一个哈希表，该哈希表将键映射到相应的值。任何非 null 对象都可以用作键或值。
为了成功地在哈希表中存储和获取对象，用作键的对象必须实现 hashCode 方法和 equals 方法。

数据结构的实现
同样也是由数组加链表组成，和HashMap一样。
那么在某些特性上面肯定是和HashMap相似的。增删改查同样很方便。

当然和HashMap相比较还是有一些区别。比如在线程同步的问题上。HashMap是不安全的，因为它提供的put（），get()方法是没有任何保护的。多个线程的情况下很容易出现数据不一致的问题。很好理解。但是Hashtable就不一样了，它的线程是同步的，在读写上面进行了加锁的操作。
另外HashMap是允许存放空值的，但是Hashtable是绝对不允许这样做。

翻看一下源码

可以看到在put和set上面都进行了加锁的操作。

另外在并发修改异常上的区别，HashTable的迭代器也会出现并发修改异常，并发修改异常，在介绍Collection集合中已经详细说明。其实这种机制又被陈为fail-fast机制，是集合中的一种错误机制。HashMap会出现，因为它的迭代器就是这种迭代器。看似加锁安全的Hashtable也会出现这种异常。
HashMap的并发修改异常

通常还会有一个问题就是有关hash碰撞问题
hash碰撞就是两个不同的值经过hash计算后，可能会得到相同的hash值，这样可能就会导致数组中数据位置存放发生冲突。这样就被称之为碰撞。

Hashtable采用了链表去解决这种冲突，叫做分离链接法。HashMap呢，会在出现冲突的地方挂一个链表。链表太长的化，会转换为红黑树。红黑树会降低时间复杂度。关于红黑树此文不做详解。

Hashtable和HashMap的继承类是不一样的。
HashMap继承的AbstractMap抽象类，Hashtable继承的Dictionay抽象类
哈希表扩容算法不一样：HashMap的容量扩容按照原来的容量2，而Hashtable的容量扩容按照原来的容量2+1
容量(capacity)默认值不一样：HashMap的容量默认值为16，而Hashtable的默认值是11
在put方法上面HashMap是将节点插入到链表的尾部，而Hashtable是将节点插入到链表的头部

同时若考虑到底层的原理，HashMap采用了数组+链表+红黑树，而Hashtable采用数组+链表。红黑树的引入和版本有关系。
这戏都是可以通过分析源码得到，如果自己有精力，会在后面继续细化。

要解Hashtable表吗？这里找到一篇可以参考的文章
解析文

实现类LinkedHashMap
说明
JavaApi的完整定义

public class LinkedHashMap<K,V>extends HashMap<K,V>implements Map<K,V>
1

说明

Map 接口的哈希表和链接列表实现，具有可预知的迭代顺序。此实现与 HashMap 的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序通常就是将键插入到映射中的顺序（插入顺序）。注意，如果在映射中重新插入 键，则插入顺序不受影响。（如果在调用 m.put(k, v) 前 m.containsKey(k) 返回了 true，则调用时会将键 k 重新插入到映射 m 中。）
此实现可以让客户避免未指定的、由 HashMap（及 Hashtable）所提供的通常为杂乱无章的排序工作，同时无需增加与 TreeMap 相关的成本。使用它可以生成一个与原来顺序相同的映射副本，而与原映射的实现无关：

另外在线程同步和并发的操作上也有说明

注意，此实现不是同步的。如果多个线程同时访问链接的哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须 保持外部同步。这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedMap 方法来“包装”该映射。最好在创建时完成这一操作，以防止对映射的意外的非同步访问：
Map m = Collections.synchronizedMap(new LinkedHashMap(…));结构修改是指添加或删除一个或多个映射关系，或者在按访问顺序链接的哈希映射中影响迭代顺序的任何操作。在按插入顺序链接的哈希映射中，仅更改与映射中已包含键关联的值不是结构修改。在按访问顺序链接的哈希映射中，仅利用 get 查询映射不是结构修改。）
Collection（由此类的所有 collection 视图方法所返回）的 iterator 方法返回的迭代器都是快速失败 的：在迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器自身的 remove 方法，其他任何时间任何方式的修改，迭代器都将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不冒将来不确定的时间任意发生不确定行为的风险。

LinkedHashMap继承了HashMap，在很多方面具有HashMap的特性。其实是拥有HashMap的所有开放的功能，在1.8前后的源码上LinkedHashMap底层源码又大有不同。

数据结构特点
在数据结构上面，LinkedHashMap是采用了双向链表的结构，这种结构在key,value上面。使其变得有序。维护了map的迭代次序。

package java_practice;

import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapDemo {

public static void main(String args[]) {
    LinkedHashMap<String, String> lhm = new LinkedHashMap<>();
    lhm.put("Hello", "World");
    lhm.put("just", "that");
    lhm.put("that", "right");
    Iterator<Map.Entry<String, String>> iterator = lhm.entrySet().iterator();
    while (iterator.hasNext()) {
        Map.Entry<String, String> next = iterator.next();
        System.out.println(next.getKey() + next.getValue());
    }
}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

现在这个结构并不是很推荐使用了。

实现类TreeMap
说明
完整类定义如下

public class TreeMap<K,V>extends AbstractMap<K,V>implements NavigableMap<K,V>, Cloneable, Serializable
1

基于红黑树（Red-Black tree）的 NavigableMap 实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。

在线程同步问题上

注意，此实现不是同步的。如果多个线程同时访问一个映射，并且其中至少一个线程从结构上修改了该映射，则其必须 外部同步。（结构上的修改是指添加或删除一个或多个映射关系的操作；仅改变与现有键关联的值不是结构上的修改。）这一般是通过对自然封装该映射的对象执行同步操作来完成的。如果不存在这样的对象，则应该使用 Collections.synchronizedSortedMap 方法来“包装”该映射。

同样的并发异常

注意，迭代器的快速失败行为无法得到保证，一般来说，当存在不同步的并发修改时，不可能作出任何肯定的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此，编写依赖于此异常的程序的做法是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测 bug。

底层数据结构
TreeMap是一种采用了红黑树进行存储数据，红黑树就是一种二叉查找树，具有某些特性的一种树结构。在JAVAAPI中也有说明，TreeMap是具有排序的功能的，同理也在继承实现关系上可以发现，实现了SortedMap接口，所以是一定会按照Key大小对Map中的元素进行排序的。默认的是自然排序，这一点和单列集合的TreeSet很相似。

底层数据结构以及红黑树的理解参考文
数据结构篇：TreeMap的底层实现—红黑树（一）

同样是非同步，如果要进行同步的话，可以进行手动同步。javaapi说的明明白白。用到的方法就是 SortedMap m = Collections.synchronizedSortedMap(new TreeMap(…));
其实就是上锁。

方法还是比较多的。

简单再说明一下未曾见过的方法

putIfAbsent() - 如果映射中不存在指定的键，则将指定的键/值映射插入到map中

同样的也可以使用到前面迭代的时候常用到的方法

entrySet() - 返回TreeMap的所有键/值映射（条目）的集合（此处方法一如以上使用方式）

keySet() - 返回TreeMap的所有键的集合(获取到键)

values() - 返回TreeMap的所有图的集合（获取到值）

jdkapi还有一些说明方法，下面给出较为清晰的说明

HigherKey() - 返回大于指定键的那些键中的最小的键。

HigherEntry() - 返回与所有大于指定键的键中最小的键相关的条目。

lowerKey() - 返回所有小于指定键的最大键。

lowerEntry() - 返回与所有小于指定键的键中最大的键关联的条目。

ceilingKey() - 返回大于指定键的那些键中的最小的键。如果映射中存在作为参数传递的键，则它将返回该键。

ceilingEntry() - 返回与大于指定键的那些键中最小的键相关的条目。如果映射中存在与传递给自变量的键关联的条目，则返回与该键关联的条目。

floorKey() - 返回小于指定键的那些键中最大的键。如果存在作为参数传递的键，它将返回该键。

floorEntry() - 返回与小于指定键的那些键中最大的键相关的条目。如果存在作为参数传递的键，它将返回该键
pollFirstEntry() - 返回并删除与映射的第一个键关联的条目
pollLastEntry() -返回并删除与映射的最后一个键关联的条目

具体的需要应用的话，直接查找api就可以。

既然是树，tree,经常用到它的排序方法。这一点，还是和之前单列集合的文章的默认自然排序的相似。

单列集合的说明中也同样对自己定义的排序方法做了介绍。下面再说明一下。

于是我做了一个sb的自排序（泛型是不能随便传的。大佬为我指点迷津）
我写了这样一个程序。简单的自己比划一下排序这个实现自排序。先把下面的写了一部分后，发现上面的不能再new了。

我可能比较懒惰了。这回没去仔细看源码，后来一位大佬给我提出一种解决方案

为什么会这样？

只能是String啊！我将它的泛型Key还定义为TreeMap类型。好吧！我还是太菜了。

如何进行自定义，如果key一样，然后按照value排序，其实很简单，就是大佬给出的解决办法，但是其实是错的。
他给出的解法是这样的

package java_practice;

import java.util.Collection;
import java.util.Comparator;
import java.util.Set;
import java.util.TreeMap;

public class TreeMapDemo {

public static TreeMap<String,Integer> tm;

public static void main(String[] args) {
    //Comparator comparator;
    tm = new TreeMap(new TreeMapCompare());
    tm.put("lqx",12);
    tm.put("fqy",16);
    tm.put("znk",10);
    tm.put("jgdabc",20);
}



public static class TreeMapCompare implements   Comparator<String>{

    @Override
    public int compare(String key1, String key2) {
        Integer v1 = tm.get(key1);
        Integer v2 = tm.get(key2);
        return v1.compareTo(v2 )==0?
                key1.compareTo(key2)    //如果value相等则比较key
                :
                v1.compareTo(v2 ); //如果value不等则按照value比较


    }
}

}

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
32
33
34
35
36
37
38
39

但是最后这个报了空指针异常了。后来发现这样写去加入值得·比较并不合理。后来大佬改进了一下。

然后我突然有豁然开朗，这样也是可以的。

package java_practice;

import java.util.Comparator;
import java.util.HashMap;
import java.util.TreeMap;

public class TreeMapCompareDemo {

public static void main(String[] args) {
    Comparator comparator;
    HashMap<String,Integer> baseMap = new HashMap();
    baseMap.put("lqx",12);
    baseMap.put("fqy",16);
    baseMap.put("znk",10);
    baseMap.put("aa",15);
    baseMap.put("bb",15);
    baseMap.put("cc",20);
    baseMap.put("dd",20);
    baseMap.put("jgdabc",20);

    TreeMap tm = new TreeMap(new TreeMapCompare(baseMap));
    tm.putAll(baseMap);

    System.out.println(tm);
}



static class TreeMapCompare implements   Comparator<String>{
    private HashMap<String,Integer> baseMap = null;

    public TreeMapCompare(HashMap baseMap) {
        this.baseMap = baseMap;
    }

    @Override
    public int compare(String key1, String key2) {
        Integer v1 = baseMap.get(key1);
        Integer v2 = baseMap.get(key2);
        return v1.compareTo(v2 )==0?
                key1.compareTo(key2)    //如果value相等则比较key
                :
                v1.compareTo(v2 ); //如果value不等则按照value比较


    }
}

}

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

另一位大佬也给出了方法

import java.util.*;

public class TreeMapDemo {

public static void main(String[] args) {
    TreeMapDemo.test();
}

public static void test() {
    HashMap<String, Integer> map = new HashMap<>();
    map.put("lqx", 12);
    map.put("fqy", 16);
    map.put("znk", 10);
    map.put("jgdabc", 20);

    List<Map.Entry<String, Integer>> list = new ArrayList<>(map.entrySet());

    list.sort(new Comparator<Map.Entry<String, Integer>>() {
        @Override
        public int compare(Map.Entry<String, Integer> t0,
                           Map.Entry<String, Integer> t1) {
            Integer v1 = t0.getValue();
            Integer v2 = t1.getValue();
            String k1 = t0.getKey();
            String k2 = t1.getKey();
            return v1.compareTo(v2) == 0 ?
                    k1.compareTo(k2)    //如果value相等则比较key
                    :
                    v1.compareTo(v2); //如果value不等则按照value比较
        }
    });

    Iterator<Map.Entry<String, Integer>> iterator = list.iterator();
    while (iterator.hasNext()) {
        System.out.print(iterator.next()+", ");

    }
}

}

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
32
33
34
35
36
37
38
39
说一句感谢csdn的回答问题的大佬

不知道读者有什么好的方法。

我自己做了一部分查阅了解（我看了一些源码）
如果想要按照值得话，必须需要得到值。我查了资料。可以结合Collections.sort()的方法。API中给出了说明。

然后追溯这个比较器接口

其实通过了解可以了解这个接口的方法

需要注意的是，如果自定义构造器的话，一般需要自己进行重写这个方法。
下面演示一下进行按照值进行排序。代码简单，但是真的蕴含很丰富的内容。

package java_practice;

import java.util.*;

public class TreeMapDemo {

public static void main(String[] args) {
    //Comparator comparator;
    TreeMap<String, Integer> tm;
    tm = new TreeMap<>();
    tm.put("lqx",12);
    tm.put("fqy",16);
    tm.put("znk",10);
    tm.put("jgdabc",20);
    ArrayList<Map.Entry<String, Integer>> list = new ArrayList<>(tm.entrySet());
    System.out.println(tm);
    Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() {
        @Override
        public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
            return o1.getValue().compareTo(o2.getValue());
        }
    });
    System.out.println(list);
}

}

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

上面已经提到过这个Entry，封装了键值。里面的提供了getValue()和getKey（）方法。这样我们就可以自定义比较构造器。这样想想，其实要想彻底了解，还是得多看看源码。并且jdk跟新得话，源码也可能会有变化，所以还是得多多去了解。看源码有时候真的很必要。

其实自己会想到，很多时候我们会还是对对象的属性进行比较。单列的比较器好像比双列的比较器容易一点。没有那么难理解。现在双列的比较器也理解了好多。希望记录下来。以后自己该补充就补充。不断去了解才能真正的学到。
其实我想到这里，我知道还是有很多没有涉及到。但是其实这篇文加上我自己写代码，查资料。看源码，我花了整整两天。没那么简单。单纯会用和理解是不一样的。想到这里，又是一口老血。

就写这么多吧！以后遇到问题再添加内容。