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跟新得话，源码也可能会有变化，所以还是得多多去了解。看源码有时候真的很必要。
其实自己会想到，很多时候我们会还是对对象的属性进行比较。单列的比较器好像比双列的比较器容易一点。没有那么难理解。现在双列的比较器也理解了好多。希望记录下来。以后自己该补充就补充。不断去了解才能真正的学到。
其实我想到这里，我知道还是有很多没有涉及到。但是其实这篇文加上我自己写代码，查资料。看源码，我花了整整两天。没那么简单。单纯会用和理解是不一样的。想到这里，又是一口老血。
就写这么多吧！以后遇到问题再添加内容。
