一、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中的其他方法有兴趣可以自行补充.
public class TestMyHashMap {
public static void main(String[] args) {
MyHashMap<Integer, String> m = new MyHashMap<>();
m.put(1, "A");
m.put(1, "C");
m.put(2, "B");
System.out.println(m.get(1));
}
}
class MyHashMap<K,V>{
int size = 0;
@SuppressWarnings("unchecked")
MyLinkedList <K,V>[] arr = new MyLinkedList[999];//存放数据的数组
public void put(K key,V value){
int hash = key.hashCode()%999; //根据当前key计算hashC并对999取余，
if(arr[hash]==null){ //如果对应arr[hash]为空则创建一个链表对象。
MyLinkedList<K,V> l = new MyLinkedList<>();
arr[hash] = l; //将创建好的链表添加到数组中
arr[hash].add(key, value);//并且将key，value添加到链表中
}else{
if(arr[hash].isKeyValue(key, value)); //遍历链表，如果有相同的key则用新的value覆盖原有的value
else{
arr[hash].add(key, value); //如果没有重复的key，则直接将数据添加到链表后面。
}
}
}
public V get(K key){ //通过key获取value
return arr[key.hashCode()].KeygetValue(key);//进去arr[key.hashCode()]中遍历，
} //如果有指定的key则返回对应value。
} //如果没有则返回null
class MyLinkedList<K,V>{/这个详细解释可参照https://www.cnblogs.com/huang-changfan/p/9583784.html int size = 0;
private Node<K,V> first;
private Node<K,V> last;
public void add(K key,V value){
if(first == null){
Node<K,V> n = new Node<K,V>();
n.setKey(key);
n.setValue(value);
n.setFirst(null);
n.setLast(null);
first = n;
last = n;
size++;
}else{
Node<K,V> n = new Node<K,V>();
n.setFirst(last);
last.setLast(n);
n.setKey(key);
n.setValue(value);
n.setLast(null);
last = n;
size++;
}
}
public boolean isKeyValue(K key,V value){//遍历链表，如果有key相等则覆盖原有value
Node<K,V> f = new Node<K,V>();
f= first; //获取链表头结点
if(f.getKey().equals(key)){//判断当前结点key的值是否等于传递进来的key
f.value = value; //如果相等，替换原有value并返回true
return true;
}
while(f.getLast()!= null){ //判断链表下一结点是否为空
f = f.getLast(); //不为空则指向下一结点继续判断。
if(f.getKey().equals(key)){
f.value = value;
return true;
}
}
return false; //如果链表遍历结束，没有相同项则返回false
}
public V KeygetValue(K key){//通过key返回value
Node<K,V> f = new Node<K,V>();//与上述差不过，遍历链表相同则返回对应的value。
f= first;
if(f.getKey().equals(key))
return f.value;
while(f.getLast()!= null){
f = f.getLast();
if(f.getKey().equals(key))
return f.value;
}
return null;
}
}
class Node<K,V>{ //链表中的结点
private Node<K,V> first;//记录头结点的位置
private K key; //存放key value
V value;
private Node<K,V> last; //记录尾结点位置
public Node(){};
public Node(K key,V value){//下面是构造方法和一些set，get方法。
this.key = key;
this.value = value;
}
public Node<K, V> getFirst() {
return first;
}
public void setFirst(Node<K, V> first) {
this.first = first;
}
public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
public Node<K, V> getLast() {
return last;
}
public void setLast(Node<K, V> last) {
this.last = last;
}
}
运行结果：
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排序结果相同。