5.2类集（java学习笔记）Map，Set接口

一、Map接口

Map接口中存储数据是通过key->value的方式成对存储的，可以通过key找到value。

二、Map接口常用子类

1.HashMap

HashMap是无序存放的，key不允许重复，但值可以重复。如果key重复，后来的value会覆盖之前的value。

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

public class TestHashMpa {
    public static void main(String[] args) {
        Map<Integer,String> m = new HashMap<Integer,String>();
        m.put(3,"C");
        m.put(1,"A");
        m.put(2,"B");
        m.put(3,"D");
        m.put(4,"A");
        System.out.println("1="+ m.get(1)+" 2="+m.get(2)+" 3="+m.get(3)+" 4="+m.get(4));
    }
}

运行结果：

1=A 2=B 3=D 4=A

这里面有两个方法一个是public V put(K key,V value),此处的K,V泛型。put方法向map中放入k—>v.并返回value。

还有一个是public V get(Object K),获得key对应的value。

上面代码中键值3重复了，所以先添加进去C被后添加进去的D覆盖，此时get（3）得到的是D。

value有两个A，但是它们的键没有重复所以不影响。

三、常用方法简介

1.判断内容是否存在

1.1 public boolean containsKey(Object key)判断key是否存在。

1.2 public boolean containsValue(Object key)判断value是否存在。

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

public class TestHashMpa {
    public static void main(String[] args) {
        Map<Integer,String> m = new HashMap<Integer,String>();
        m.put(3,"C");
        m.put(1,"A");
        m.put(2,"B");
        m.put(3,"D");
        m.put(4,"A");
        System.out.println(m.containsKey(1));//判断key为1是否存在，此处为true
        System.out.println(m.containsKey(5));
        System.out.println(m.containsValue("A"));//判断Value"A"是否存在，此处为true
        System.out.println(m.containsValue("E"));
    }
}

运行结果：
true
false
true
false

2.根据key删除value

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

public class TestHashMpa {
    public static void main(String[] args) {
        Map<Integer,String> m = new HashMap<Integer,String>();
        m.put(3,"C");
        m.put(1,"A");
        m.put(2,"B");
        m.put(3,"D");
        m.put(4,"A");
        System.out.println("1="+ m.get(1)+" 2="+m.get(2)+" 3="+m.get(3)+" 4="+m.get(4));
        m.remove(4);
        System.out.println("1="+ m.get(1)+" 2="+m.get(2)+" 3="+m.get(3)+" 4="+m.get(4));
    }
}

1=A 2=B 3=D 4=A
1=A 2=B 3=D 4=null

根据键值删除对应的value。

3.public void putAll(Map<? extends K,? extends V> t)

将一个Map集合中的内容加入到另一个Map

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

public class TestHashMpa {
    public static void main(String[] args) {
        Map<Integer,String> m = new HashMap<Integer,String>();
        Map<Integer,String> ma = new HashMap<Integer,String>();
        m.put(3,"C");
        m.put(1,"A");
        m.put(2,"B");
        m.put(3,"D");
        m.put(4,"A");
        ma.put(5, "D");
        ma.put(6, "E");
        ma.putAll(m);
        System.out.println("1="+ ma.get(1)+" 2="+ma.get(2)+" 3="+ma.get(3)+" 4="+ma.get(4)+
                " 5="+ ma.get(5)+" 6="+ ma.get(6));
    }
}

运行结果：
1=A 2=B 3=D 4=A 5=D 6=E

m本身有A、B、D，ma有A、D、E，将m添加到ma后，ma就有A、B、D、A、D、E。

四、HashMap底层实现

我们不妨想一想HashMap底层如何实现，

假如我们用数组，这样好像也可以，但是我们用数组的话。检查Key是否重复，包括根据Key查找Value每次都要从头开始遍历，这样效率太低浪费资源。

我们能否有一种更好的方式，可以减少查询时间？

当然是有的，同时也是HashMap的实现方式，数组+链表。

数组中每一个元素存放一个链表。

这里还需要用到hashCode（），计算hash码的函数，我们暂且先不管这些。

我们先来假设下：

假设有一个无限大的数组arr，向这个数组放入东西必须成对放入（key，value）。

假设有一个方法h，可以根据key计算出一个值，且不同key计算出来的值不一样，相同key计算出来的值一样。

那么我们放数据的时候，先通过key.h()计算一个值，然后判断arr[key.h()]是否为空，如果为空则直接放入，

如果不为空则将原有的value替换成新来的value.

要通过key获得value时，直接返回arr[key.h()].value.

假设上列说明是HashMap的底层实现,是不是感觉很方便，取出数据基本只需要一次操作，读取非常快。

上面的思路之所以快取决于两点的相互配合，一是数组无穷大的，二、每一个不同的key都有一个不同值。

这两点在实际中很难做到，近乎可以说不可能做到。

但这种思路确实很方便。

那么我们能否根据这个思路想一个折中的方法？

首先，数组不可能无穷大，那我们只能定义一有限长度的数组。

其次，每一个不同的key都有一个不同值，这个也不好实现，我们就允许不同的key可以出现相同值.

基本思路确定了，我们就要解决这个思路中有问题的部分，既然不同的key可以出现相同值，那我们存放

数据时怎么存放呢？答案是用链表。首先通过计算key.h（）确定数组下标，然后遍历链表比较key，

如果有相同的key则替换其中的value，如果没有则将数据添加到链表中。

这样效率虽然没有无穷数组的快，但也提升了不少。

假设这里的数组长度为1000，每一个数组元素存放一个链表。

我们有10000个数据，假设均匀分布，那么最坏的情况也只需要遍历10次，

如果不是均匀分布的也比遍历10000次会好很多。

数组+链表

上面的h（）方法就是hashCode（），hashCode()方法就是根据当前对象采用一定的算法计算出一个值。

通过这个值来减少查找等操作的次数。

要注意一点:

比较对象是否相等一般是用过equals方法。

如果hashCode不相等，则equals为false。

如果hashCode相等，则equals不定，可能false也可能为true.

hashCode（）可参考：http://www.cnblogs.com/dolphin0520/p/3681042.html

下面我们来实现一个简易的HashMap（只写了put，get方法），该实现只为便于理解HashMap，

与JDK中具体实现HashMap有差异，由于是简易版的有很多不足，只为理解数组加链表的思想。

为了便于理解程序，链表中只提供了实现HashMap(put，get)所需要的方法。

MyHashMap及MyLinkedList中的其他方法有兴趣可以自行补充.

  1 public class TestMyHashMap {
  2     public static void main(String[] args) {
  3        MyHashMap<Integer, String> m = new MyHashMap<>();
  4        m.put(1, "A");
  5        m.put(1, "C");
  6        m.put(2, "B");
  7        System.out.println(m.get(1));
  8     }
  9 }
 10 
 11 
 12 class MyHashMap<K,V>{
 13     int size = 0;
 14     @SuppressWarnings("unchecked")
 15     MyLinkedList <K,V>[] arr = new MyLinkedList[999];//存放数据的数组
 16     
 17     public void put(K key,V value){
 18         int hash = key.hashCode()%999;  //根据当前key计算hashC并对999取余，
 19         if(arr[hash]==null){ //如果对应arr[hash]为空则创建一个链表对象。
 20             MyLinkedList<K,V> l = new MyLinkedList<>();
 21             arr[hash] = l;   //将创建好的链表添加到数组中
 22             arr[hash].add(key, value);//并且将key，value添加到链表中
 23         }else{
 24             if(arr[hash].isKeyValue(key, value)); //遍历链表，如果有相同的key则用新的value覆盖原有的value
 25             else{
 26                 arr[hash].add(key, value);  //如果没有重复的key，则直接将数据添加到链表后面。
 27             }
 28         }
 29     }
 30     public V get(K key){ //通过key获取value       
 31         return arr[key.hashCode()].KeygetValue(key);//进去arr[key.hashCode()]中遍历，
 32     }                                               //如果有指定的key则返回对应value。
 33 }　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 //如果没有则返回null
 34 
 35 
 36 class MyLinkedList<K,V>{/这个详细解释可参照https://www.cnblogs.com/huang-changfan/p/9583784.html
 37     int size = 0;
 38     private Node<K,V> first;
 39     private Node<K,V> last;
 40     public void add(K key,V value){
 41         if(first == null){
 42             Node<K,V> n = new Node<K,V>();
 43             n.setKey(key);
 44             n.setValue(value);
 45             n.setFirst(null);
 46             n.setLast(null);
 47             first = n;
 48             last = n;
 49             size++;
 50         }else{
 51             Node<K,V> n = new Node<K,V>();
 52             n.setFirst(last);
 53             last.setLast(n);
 54             n.setKey(key);
 55             n.setValue(value);
 56             n.setLast(null);
 57             last = n;
 58             size++;
 59         }
 60     }
 61     
 62     public boolean isKeyValue(K key,V value){//遍历链表，如果有key相等则覆盖原有value
 63         Node<K,V> f = new Node<K,V>();
 64         f= first; //获取链表头结点
 65         if(f.getKey().equals(key)){//判断当前结点key的值是否等于传递进来的key
 66             f.value = value;     //如果相等，替换原有value并返回true
 67             return true;
 68         }
 69         while(f.getLast()!= null){  //判断链表下一结点是否为空
 70             f = f.getLast();        //不为空则指向下一结点继续判断。
 71             if(f.getKey().equals(key)){
 72                 f.value = value;
 73                 return true;
 74             }
 75         }
 76         return false; //如果链表遍历结束，没有相同项则返回false
 77     }
 78     
 79     public V KeygetValue(K key){//通过key返回value
 80         Node<K,V> f = new Node<K,V>();//与上述差不过，遍历链表相同则返回对应的value。
 81         f= first;
 82         if(f.getKey().equals(key))
 83             return f.value;
 84         while(f.getLast()!= null){
 85             f = f.getLast();
 86             if(f.getKey().equals(key))
 87                 return f.value;
 88         }
 89         return null;
 90     }
 91     
 92 }
 93 
 94 class Node<K,V>{ //链表中的结点
 95     private Node<K,V> first;//记录头结点的位置
 96     private K key;  //存放key value
 97     V value;
 98     private Node<K,V> last; //记录尾结点位置
 99     public Node(){};
100     public Node(K key,V value){//下面是构造方法和一些set，get方法。
101         this.key = key;
102         this.value = value;
103     }
104     public Node<K, V> getFirst() {
105         return first;
106     }
107     public void setFirst(Node<K, V> first) {
108         this.first = first;
109     }
110     public K getKey() {
111         return key;
112     }
113     public void setKey(K key) {
114         this.key = key;
115     }
116     public V getValue() {
117         return value;
118     }
119     public void setValue(V value) {
120         this.value = value;
121     }
122     public Node<K, V> getLast() {
123         return last;
124     }
125     public void setLast(Node<K, V> last) {
126         this.last = last;
127     }    
128 }

运行结果：
CB

Map中还有一个子类，是TreeMap,这个子类中的数据是有序的，根据key排序。

但是，如果是放入的key是自己创建的类时需要实现Comparator接口。

因为系统已经定义好的类已经实现了Comparator接口指定了排序规则，而自己定义的类没有

实现Comparator接口指定排序规则会出现问题。有兴趣的可以去了解下比较器。

public class TestMap{
    public static void main(String[] args) {
        Set<String> s  = new HashSet<>();
        Map<String,String> mh = new HashMap<>();
        Map<String,String> mt = new TreeMap<>();
        mh.put("ZS", "张三");
        mh.put("LS","李四");
        mh.put("WW", "王五");
        mh.put("ZL", "赵六");
        mt.put("ZS", "张三");
        mt.put("LS","李四");
        mt.put("WW", "王五");
        mt.put("ZL", "赵六");
        System.out.println(mh);
        System.out.println(mt);
    }
}

运行结果：
{WW=王五, ZL=赵六, LS=李四, ZS=张三}
{LS=李四, WW=王五, ZL=赵六, ZS=张三}

HashMap输出的是无序的，二TreeMap则根据key进行了排序，

可以看出这里的key是根据字母的顺序来进行排序的，L在前面，Z在最后面

当第一个Z相同时，比较后一个字母的顺序，L在S前面所以赵六在张三前面。

这里的规则是系统指定好的，如果是自己创建的类，需要自己实现接口并规定排序方法。

五、Set接口

Set接口中不允许加入重复的元素。

1.Set接口常用子类

　　1.1 HashSet

　　　　大家想一想HashSet和HashMap命名方式很像，而且Set接口中不允许加入重复读的元素。

　　　　我们回忆下Map中的key是不是也不允许重复？那这两者有何关联呢？

　　　　我们看下HashSet的源码：

　　　　HashSet的底层就是新建一个HshMap对象，

　　　　我们来看下添加方法。

　　　　添加方法也是调用map的put方法，不过是把key作为hashSet数据存放位置。

　　　　value存放的是

　　　　所以只用到了key，把key作为Set的数据。

import java.util.HashSet;
import java.util.Set;

public class TestSet {
    public static void main(String[] args) {
        Set<String> s  = new HashSet<>();
        s.add("张三");
        s.add("李四");
        s.add("王五");
        s.add("赵六");
        System.out.println(s);
    }
}

运行结果：
[李四, 张三, 王五, 赵六]

同样HashMap是无序的，上面可以看出HashSet中的add方法就是调用HashMap中的put方法。

HashSet中很多方法其实内部都是通过调用Map来实现的。

　　　　2.2TreeSet

　　　　TreeSet和TreeMap相似，底部也是通过TreeMap来实现的。

import java.util.Set;
import java.util.TreeSet;

public class TestSet {
    public static void main(String[] args) {
        Set<String> s  = new TreeSet<>();
        s.add("ZS");
        s.add("LS");
        s.add("WW");
        s.add("ZL");
        System.out.println(s);
    }
}

运行结果：
[LS, WW, ZL, ZS]

我们会发现这里的排序结果与之前TreeMap排序结果相同。