Java集合类（三）

Java集合类(三)

Map接口实现类的特点和常用方法
Map接口的六大遍历方式
Map小结及HashMap底层源码分析
Hashtable基本介绍

Map接口实现类的特点和常用方法

Map接口的特点

注意：这里讲的是Jdk8的Map接口特点

Map与Collection并列存在。用于保存具有映射关系的数据：key-value
Map中的key和value可以是任何引用类型的数据，会封装到HashMao$Node对象中
Map中的key不允许重复，原因和HashSet一样
Map中的value可以重复
Map的key可以为null，value也可以为null，但是key为null的结点只能有一个，value为null的结点可以有多个
常用String类作为Map的key

key和value之间存在单向一对一关系，即通过指定的key总能找到对应的value

代码演示

package com.conllection_.maps;

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

public class Map_ {
    public static void main(String[] args) {
        Map map = new HashMap();

        //key不可以重复，重复的会被等价替换
        //value可以重复
        map.put("no1","成志恒");//k-v
        map.put("no2","张无忌");//k-v
        map.put("no1","张三丰");//当有相同的key，就等于等价替换
        map.put("no3","成志恒");//k-v
        //key只能有一个null
        map.put(null,null);
        map.put(null,"abc");//等价替换
        //value可以多个为null
        map.put("no4",null);
        map.put("no5",null);//value可以多个为null
        map.put(1,"赵敏");

        //通过get方法，传入key，会返回对应的value
        System.out.println(map.get("no3"));

        System.out.println("map = " + map);
    }
}

Map接口k-v详解

Map存放数据的key-value示意图，一对k-v是放在一个HashMap$Node中的。因为Node实现了Entry接口，所以有些书上也说一对k-v就是一个Entry。
k-v 数据最后是存放在HashMap$Node node = newNode(hash,key,value,null) 这个对象里面的。
k-v 为了方便程序员的遍历，还会创建EntrySet集合，该集合存放的元素的类型是Entry。而一个Entry对象本身就具有key，value值。所以有EntrySet<Entry<K,V»，即
```
transient Set<Map.Entry<K,V>> entrySet;
```
EntrySet中，定义的类型是Map.Entry，但是实际上存放的还是HashMap$Node。原因如下
```
static class Node<K,V> implements Map.Entry<K,V> 
```

由于Map.Entry提供了两个重要的方法：K getKey(); V getValue() ，所以当我们把HashMap$Node对象存放到EntrySet就可以方便我们的遍历。

程序演示

package com.conllection_.maps;

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

public class MapSource {
    public static void main(String[] args) {
        Map map = new HashMap();
        map.put("no1","成志恒");//k-v
        map.put("no2","张无忌");//k-v

        Set set = map.entrySet();
        for (Object obj:set) {
            //向下转型
            Map.Entry entry = (Map.Entry)obj;
            System.out.println(entry.getKey() + "-" + entry.getValue());
        }
        System.out.println("Map = " + map);

    }
}

输出结果：

keySet()：与Node封装到EntrySet集合一样，不过他是封装到Set集合，利用该方法可以单独遍历Key值

values：与Node封装到EntrySet集合一样，不过他是封装到Collection集合，利用该方法可以单独遍历Value值

Set set1 = map.keySet();
System.out.println(set1);

Collection values = map.values();
System.out.println(values);

运行结果

Map接口的常用方法

put()：添加元素
remove()：根据键删除映射关系
get()：根据键获取值
size()：获取元素的个数
isEmpty()：判断元素个数是否为0
clear()：清除集合键值对

containsKey()：查找键是否存在

代码演示

package com.conllection_.maps;

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

public class MapMethod {
    public static void main(String[] args) {
        Map map = new HashMap();
//        1. put()：添加元素
        map.put("no1",new Book("小王子",100));
        map.put("no1","成志恒");
        map.put("no2","史森明");
        map.put("no3","李元浩");
        map.put("no4","李元浩");
        map.put(null,"小虎");
        map.put("no5",null);

        System.out.println("map = " + map);
//        2. remove()：根据键删除映射关系
        map.remove("no3");
        System.out.println("map = " + map);
//        3. get()：根据键获取值
        System.out.println(map.get("no1"));
//        4. size()：获取元素的个数
        System.out.println(map.size());
//        5. isEmpty()：判断元素个数是否为0
        System.out.println(map.isEmpty());
//        6. clear()：清除集合键值对
        map.clear();
        System.out.println(map.isEmpty());
        System.out.println(map.size());
//        7. containsKey()：查找键是否存在
        map.put("no1",new Book("小王子",100));
        System.out.println(map.containsKey("no1"));
        System.out.println(map.containsKey("no5"));


    }
}
class Book{
    private String name;
    private double price;

    public Book(String name, double price) {
        this.name = name;
        this.price = price;
    }

    @Override
    public String toString() {
        return "Book{" +
                "name='" + name + '\'' +
                ", price=" + price +
                '}';
    }
}

Map接口的六大遍历方式

遍历以下Map接口的元素

import java.util.Set;

public class MapFor {
    public static void main(String[] args) {
        Map map = new HashMap();
        map.put("no1","成志恒");
        map.put("no2","史森明");
        map.put("no3","李元浩");
        map.put("no4","李元浩");
        map.put(null,"小虎");
        map.put("no5",null);
    }
}

使用keySet()+增强for遍历k-v

System.out.println("=====第一种遍历方式=====");
Set keySet = map.keySet();

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

运行结果

使用keySet()+迭代器遍历k-v

System.out.println("=====第二种遍历方式=====");
Iterator iterator = keySet.iterator();
while (iterator.hasNext()) {
    Object next =  iterator.next();
    System.out.println(next+"="+map.get(next));
}

运行结果

使用values()+增强for遍历value（因为value不能映射key，所以只能遍历value）

System.out.println("=====第三种遍历方式=====");
Collection values = map.values();
for (Object value : values) {
    System.out.println(value);
}

运行结果

使用values()+迭代器遍历

System.out.println("=====第四种遍历方式=====");
Iterator iterator1 = values.iterator();
while (iterator1.hasNext()) {
    Object next =  iterator1.next();
    System.out.println(next);
}

运行结果

使用EntrySet()+增强for遍历

System.out.println("=====第五种遍历方式=====");
Set entrySet = map.entrySet();

for (Object obj : entrySet) {
    //将obj转成Map.Entry
    Map.Entry entry = (Map.Entry)obj;
    System.out.println(entry.getKey()+"-"+entry.getValue());
}

运行结果

使用EntrySet()+迭代器遍历

System.out.println("=====第六种遍历方式=====");
Iterator iterator2 = entrySet.iterator();
while (iterator2.hasNext()) {
    Object next =  iterator2.next();
    Map.Entry entry = (Map.Entry)next;
    System.out.println(entry.getKey()+"-"+entry.getValue());
}

运行结果

HashMap练习题

使用HashMap添加三个元素对象，要求：

键：员工ID，值：员工对象
遍历显示工资>18000的员工（遍历方法两种）
员工类：姓名、工资、员工id

员工类Staff代码如下

class Staff{
    private String name;
    private double wages;
    private int id;

    public Staff(String name, double wages, int id) {
        this.name = name;
        this.wages = wages;
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public double getWages() {
        return wages;
    }

    public void setWages(double wages) {
        this.wages = wages;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    @Override
    public String toString() {
        return "Staff{" +
                "name='" + name + '\'' +
                ", wages=" + wages +
                ", id=" + id +
                '}';
    }
}

测试类MapExercise代码如下

package com.conllection_.maps;

import java.util.*;

public class MapExercise {
    public static void main(String[] args) {
        Map map = new HashMap();
        map.put("01",new Staff("成志恒",19000,01));
        map.put("02",new Staff("史森明",20000,02));
        map.put("03",new Staff("小虎",17000,03));
        map.put("04",new Staff("李元浩",18000,04));


        System.out.println("===第一种方式===");
        //使用entrySet方法返回映射中包含的映射的 Set 视图
        Set entrySet = map.entrySet();
        //利用增强for循环遍历
        for (Object o : entrySet) {
            //向下转型，为了能调用父类的方法
            Map.Entry entry = (Map.Entry)o;
            //把value对象指向从entry集中取出来的value
            Object value = entry.getValue();
            //向下转型，这样可以使用Staff对象的getWages方法。
            Staff staff = (Staff) value;
            if(staff.getWages()>18000){
                System.out.println(staff.toString());
            }

        }
        System.out.println("===第二种方式===");
        //使用keySet()方法返回封装到Map封装到Set里面的结点的Key值
        Set set = map.keySet();
        //创建迭代器
        Iterator iterator = set.iterator();
        while (iterator.hasNext()) {
            //获取迭代器中的数据
            Object next =  iterator.next();
            //向下转型，吧staff对象指向从map里面取到的value对象。
            Staff staff1 = (Staff) map.get(next);
            if (staff1.getWages()>18000){
               System.out.println(staff1);
            }
        }


    }
}

运行结果：

上述题目中，数据的封装情况如下图

所以当我们需要取出value值时，我们需要先通过EntrySet取出Entry，然后通过Entry的指向取到HashSet$Node的值。

Map小结及HashMap底层源码分析

Map小结

Map接口的常用实现类：HashMap、Hashtable和Properties
HashMap是Map接口使用频率最高的实现类
HashMap是以key-value对的方式来存储数据的
key不能重复，但是value可以重复，允许使用null键（只能有一个）和null值（可以多个）

如果添加相同的可以，则会覆盖原来的key-value，等同于修改。（key不会替换，value会替换）

if (e != null) { // existing mapping for key
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
        //此处e指向替换前的Node，所以 e.value = value;即可完成替换
        e.value = value;
    afterNodeAccess(e);
    return oldValue;
}

与HashSet一样，不保证映射的顺序，因为底层是以hash表的方式来存储的。
HashMap没有实现同步，因此线程是不安全的。方法没有做同步互斥的操作，没有synchronize

HashMap底层机制及源码剖析

HashMap底层机制示意图

（key，value）是一个Node实现了Map$Entry<K,V>
HashMap的扩容机制[和HashSet扩容机制相同]
- HashMap底层维护了Node类型的数组table，默认为null
- 当创建对象时，将加载因子(loadfactor)初始化为0.75
- 当添加key-value是，通过key的hash值得到在table的索引。然后判断该索引处是否有元素，如果没有元素直接添加。如果该索引处有元素，继续判断该元素的key和准备加入的key是否相等，如果相等，则直接替换value；如果不相等需要判断是树结构还是链表结构，做出相应处理。如果添加时发现容量不够，则需要扩容。
- 第一次添加时，会将需要扩容的table容量扩容到16，临界值(threshold)为12
- 如果需要再次扩容，会将需要扩容的table容量扩容到原来的2倍（32），临界值为原来的2倍（24）依次类推。
- 在Java8中，如果一条链表的元素个数到达TREEIFY_THRESHOLD(默认是8)，并且table的大小>=MIN_TREEIFY_CAPACITY(默认是64)，就会进行树化（转换红黑树），否则任然采用数组扩容机制
源码分析

创建MapSource类
```
package com.conllection_.maps;

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

public class MapSource {
    public static void main(String[] args) {
        Map map = new HashMap();
        map.put("no1","成志恒");//k-v
        map.put("no2","张无忌");//k-v
        map.put("no1","张无忌");//k-v
    }
}
```
调试程序，执行HashMap的无参构造器，=。
```
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
```
将负载因子(loadFactor)初始化并且创建一个空的table。

向HashMap集合添加元素，执行put方法
```
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
```
通过hash方法计算key的Hash值，然后返回给putVal方法。
```
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
```
执行putVal方法，程序首先判断table是否为null，如果为null就table的容量扩容到16
```
if ((tab = table) == null || (n = tab.length) == 0){
	n = (tab = resize()).length;
}
```
实现扩容的方法为risize()方法。

继续调试，程序会判断当前hash值对应的table索引位置上是否已经存在值，如果不存在值，就把当前Hash值的结点赋值进去。
```
if ((p = tab[i = (n - 1) & hash]) == null){
    tab[i] = newNode(hash, key, value, null);
}
```
然后modCount++（记录修改的次数），size++（记录已添加元素的个数）；

倘若当前hash值对应的table索引位置上已存在值，首先会判断当前索引位置上的hash值是否与需要添加的key值对应的hash值相同且满足以下两个条件之一：
- 准备添加的key值与p指向的Node结点的key是同一个对象
- p指向的Node结点的key的equals()和准备假如的key比较后相同。
如果上述条件皆成立，直接让e指向p（p为当前索引位置上的结点）,e为辅助变量
```
if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k)))){
    e = p;
}
```
然后继续执行，把需要添加的key值对应的value值替换掉原先存在的key值的value值
```
if (e != null) { // existing mapping for key
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    afterNodeAccess(e);
    return oldValue;
}
```
返回修改后的value值。

倘若上述条件不成立，程序会继续进行判断，判断需要添加的结点是否为树结点
```
else if (p instanceof TreeNode){
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
}
```
如果是树结点，会执行putTreeVal()方法，把需要添加的树节点添加到红黑树上。

如果不是树节点，程序会继续调试，进入到下一个else。
```
else {
    for (int binCount = 0; ; ++binCount) {
        if ((e = p.next) == null) {
            p.next = newNode(hash, key, value, null);
            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                treeifyBin(tab, hash);
            break;
        }
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            break;
        p = e;
    }
}
```
在此处程序会进入一个死循环，直至找到对应索引位置上的尾结点或者找到key相同的结点才会退出。详细见HashSet底层添加元素源码分析的最后一步。

模拟HashMap触发扩容、树化情况，并debug验证

创建测试类MapSource01

package com.conllection_.maps;

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

public class MapSource01 {
    public static void main(String[] args) {
        Map map = new HashMap();
        for (int i=0; i<12;i++){
          map.put(new A(i),"hello");
        }
        System.out.println(map);
    }
}

创建A类，重写HashCode方法，让他们有统一的Hash值

class A{
    private int no;

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

    public int getNo() {
        return no;
    }

    @Override
    public int hashCode() {
        return 100;
    }

    public void setNo(int no) {
        this.no = no;
    }

    @Override
    public String toString() {
        return "\nA{" +
                "no=" + no +
                '}';
    }
}

运行调试，直至添加到第9个元素，因为达到树化的条件（一条链表的元素个数到达8个），但table的大小<MIN_TREEIFY_CAPACITY(默认是64)，所以table会扩容。

继续调试，table再次扩容，直至table扩容到容量为64时，该链表会发生树化

Hashtable

Hashtable的基本介绍

Hashtable存放的元素时键值对：即K-V
Hashtable的键和值都不能为null，否则会抛出NullPointerException
```
if (value == null) {
    throw new NullPointerException();
}
```
Hashtable使用方法基本上和HashMap一样
Hashtable是线程安全的（synchronize），HashMap是线程不安全的

Hashtable底层的简单剖析

底层有数组 Hashtable$Entry[]，初始化大小为11

临界值 threshold = 8 （11*0.75）

创建HashtableSource类调试

package com.conllection_.maps;

import java.util.Hashtable;

public class HashtableSource {
    public static void main(String[] args) {
        Hashtable hashtable = new Hashtable();

        hashtable.put("john",100);
        hashtable.put("jack",100);
        hashtable.put("mary",200);
        hashtable.put("tom",300);
        hashtable.put("smith",500);
        hashtable.put("minster",600);
        hashtable.put("chris",200);
        hashtable.put("ssm",500);

        System.out.println("hashtable = " + hashtable);
    }
}

调试程序，我们可以发现

Hashtable按照自己的扩容机制进行扩容

继续调试HashtableSource，执行put方法，可以发现该接口添加元素时执行了addEntry方法把添加的K-V封装到Entry

private void addEntry(int hash, K key, V value, int index) {
    modCount++;

    Entry<?,?> tab[] = table;
    //当增加的元素数量大于或等于临界值时，执行rehash方法进行扩容
    if (count >= threshold) {
        // Rehash the table if the threshold is exceeded
        rehash();

        tab = table;
        hash = key.hashCode();
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    // Creates the new entry.
    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>) tab[index];
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
}

执行rehash方法进行扩容。下面截取部分rehash源码。

protected void rehash() {
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;

    // overflow-conscious code
    //进行扩容
    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            // Keep running with MAX_ARRAY_SIZE buckets
            return;
        newCapacity = MAX_ARRAY_SIZE;
    }
    //指向扩容后的Entry
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
    }

我们可以发现，当容量达到临界值时，rehash方法会通过 **int newCapacity = (oldCapacity « 1) + 1;**这条语句进行扩容。所以hashtable第一次扩容后的容量为23（11*2+1）；

HashMap与Hashtable对比

Properties

Properties类继承于Hashtable类并实现了Map接口，也是使用一种键值对的形式来保存数据
他的使用特点和Hashtable类似
Properties还可以用了从xxx.properties文件中，加载数据到Properties类对象，并进行读取和修改

xxx.properties文件通常作为配置文件，详解见Java读取properties配置文件

Properties的简单使用

Properties_类

package com.conllection_.maps;

import java.util.Properties;

public class Properties_ {
    public static void main(String[] args) {
        //Properties 继承了Hashtable
        //Properties 也是通过k-v存储数据，当然key与value都不能为null
        Properties properties = new Properties();

        //添加元素
        properties.put("jack",1);
        properties.put("john",2);
        properties.put("tom","2");

        System.out.println("properties = "+properties);

        //删除元素
        properties.remove("jack");
        System.out.println("properties = "+properties);

        //修改元素
        properties.put("jack",3);//替换
        System.out.println("properties = "+properties);

        //查找元素
        System.out.println(properties.get("jack"));
        System.out.println(properties.getProperty("tom"));
    }
}

运行结果

需要注意的是，使用getPeoperties时，当put进去的值不是String类型的时候，会返回null

例如在Properties类中添加以下代码

properties.put("jack",1);
System.out.println(properties.getProperty("jack"));

阅读getProperty源码，我们可以发现其中原理

public String getProperty(String key) {
    //把oval指向key对应的value
    Object oval = super.get(key);
    //使用三目运算符，当oval是String类型时，返回强转为String类型的oval，否则为null
    String sval = (oval instanceof String) ? (String)oval : null;
    //当sval为null，且设定了defaults的值时，返回defaultsValue，否则返回sval
    return ((sval == null) && (defaults != null)) ? defaults.getProperty(key) : sval;
}