[Java知识库]Java初学笔记19-【Set接口、HashSet类及底层机制、LinkedHashSet类、TreeSet类；Map接口、HashTable类，Properties类；Collections工具类】

【难点】
1.理解集合的底层机制
2.阅读原码
3.何时使用何种集合



【Map存放数据的key-value示意图2】

一、Set接口

1. 介绍

（1）无序(添加和取出数据的顺序不一致)，没有索引，不能用简单的for来遍历，得用迭代器。
（2）不允许重复元素，所以最多包含一个null
（3）JDK API中Set接口的实现类有:
AbstractSet ， ConcurrentHashMap.KeySetView ， ConcurrentSkipListSet ， CopyOnWriteArraySet ， EnumSet ， HashSet ， JobStateReasons ， LinkedHashSet ， TreeSet

2. Set 接口的常用方法

（以HashSet类为例）

（1）add(E e)

将指定的元素添加到此集合（如果尚未存在）

（2）contains(Object o)

如果此集合包含指定的元素，则返回 true 。

（3）isEmpty()

如果此集合不包含元素，则返回 true 。

（4）iterator()

返回此集合中元素的迭代器。

（5）remove(Object o)

如果存在，则从该集合中删除指定的元素。

二、HashSet类

1. 介绍

（1）HashSet类实现了Set接口
（2）HashSet实际上是HashMap<E,Object> map = new HashMap<>();
（3）可以存放null值，但是只能有一个null
（4）HashSet不保证元素是有序的,取决于hash后，再确定索引的结果。(即，不保证存放元素的顺序和取出顺序一致)
（5）不能有重复元素/对象。

2. HashSet底层机制

（1）低层机制：数组 + 链表 + 红黑树
之所以不把数据全部存在数组中，是考虑到随着数据增多，存取效率会变慢，所以接着采用链表和红黑树。
（2）HashSet底层是：HashMap；
（3）添加一个元素时，调用哈希算法，先得到hash值，再有hash值转化成出索引值；
（4）找到存储数据表table（table数组）,看这个索引
位置是否已经存放了元素；
（5）如果没有，直接加入该元素；
（6）如果有，调用equals比较，如果相同，就放弃添加，如果不相同，则添加到最后。
（7）在JDK8中，如果一条链表的元素个数到达 TREEIFY THRESHOLD(默认是8)，并且table数组的大小>=MIN TREEIFY CAPACITY(默认64)，就会进行树化(变成红黑树)。

3. 底层源码分析

1. 主方法中执行
   

2. 执行HashSet类中的构造器HashSet()。
   
   map为HashSet类中有一个属性
   

3. 执行完后，此时set为空null
   

4. 第一次执行add()添加元素
   

5. 调用 add（）方法，此时传入的参数 e 为“爱吃凉拌辣芒果”，PRESENT为HashSet类中的一个静态属性（共享的）new Object（）。
   

6. 进入put方法，此时Key为“爱吃凉拌辣芒果”，value为“new Object（）”
   

7. 执行hash（）方法，hash（）中传入的key 为“爱吃凉拌辣芒果”。
   

8. hash()方法判断传入的对象是否为空，不为空，则由哈希值右移16位异或计算，返回计算后的值；否则对象为空则返回0。
   

9. 执行put方法。传入的实参中，hash为计算后的哈希值，key 为“爱吃凉拌辣芒果”。
   （1）在方法中有辅助变量：节点数组tab Node [ ] tab ; 节点P Node p ; int n ，i ;
   （2）其中table （表） 为HashMap的一个属性
   
   （3）tab = table 为空，进入第一个if判断语句，进入resize()方法，具体参数值如图，最后返回一个16位大小的table数组。全为Null。
   其中，threshold为扩容的临界值，此时为0.75 * 16 = 12。
   
   
   （4）tab接收resize返回的16位空数组，n = 16
   
   （5）将哈希值转换为table数组的一个索引值，并且查看索引所在位置是否有节点。如果没有节点，则将该key“爱吃凉拌辣芒果”存入。修改的modCount++ ，结果返回null。
   

重点分析：
【1】如果算出的索引位置处，节点为空，则直接添加新节点。此时P指向table表的该索引元素所在处。

【2】否则不为空的话，开始比较
(1)比较哈希值是否相等
(2)比较加入元素的值是否相等，此时着重看equals方法。即，可以直接比较字符串内容，也可以直接比较对象，就看是否重写了equals方法。若相等，则节点插入失败。

【3】若在【2】比较后，与table表中该索引处元素不想等，则在链表中依次往后找，找到最后位置插入进去新节点，立马结束循环；

【4】若在【3】中，依次往后链表找的过程中，发现有节点与之相等，则立马结束循环，节点插入失败。

10. 此时若返回null，则add方法返回true，则表示添加元素成功。否则，添加失败。
    

例题：

没重写equals的时候，“爱吃凉拌辣芒果”为两个对象，调用的equals继承父类equals，比较的是两个对象是否一样。明显不一样，故两个都add了。

重写equals的时候，“爱吃凉拌辣芒果”为两个对象，调用的equals，比较的是两个对象的name是否一样。明显一样，故第二个add添加失败。

4. HashSet扩容机制和转成红黑树机制

（1）HashSet底层是HashMap,第一次添加时,table数组扩容到16，临界值(threshold)是16*加载因子(loadFactor)是0.75 = 12
（2）如果table数组使用到了临界值12,就会2倍扩容到16×2=32,新的临界值就是32×0.75 =24。依次类推
（3）在Java8中,如果【1】一条链表的元素个数到达TREEIFY_THRESHOLD(默认是8).。并且【2】table的大小>=MIN TREEIFY CAPACITY(默认64)，就会进行树化(红黑树)，否则仍然采用数组扩容机制。

5.练习题

三、LinkedHashSet类

1. 介绍

（1）LinkedHashSet 是HashSet的子类
（2）LinkedHashSet底层是一个 LinkedHashMap，底层维护了一个数组+双向链表
（3）LinkedHashSet根据元素的hashCode值来决定元素的存储位置,同时使用链表维护元素的次序，这使得元素看起来是以插入顺序保存的。即，遍历时候取出来的元素顺序与存入的顺序是一样的。
（4）LinkedHashSet不允许添重复元素
【LinkedHashSet】

2. LinkedHashSet底层机制

（1）低层机制：数组 + 双链表
（2）在LinkedHastSet中维护了一个hash表（数组）和双向链表( LinkedHashSet有head和tail )
（3）每一个节点有before和after属性,这样可以形成双向链表
（4）在添加一个元素时，先求hash值，在求索引，确定该元素在table的位置，然后将添加的元素加入到双向链表(如果已经存在，不添加，原则和hashset一样)
tail.next = newElement
newElement.pre = tail
tail = newEelment;
（5）这样的话，我们遍历LinkedHashSet也能确保插入顺序和遍历顺序一致

四、Map接口

1. 介绍

（1）比Set接口更实用。
（2）Map与Collection并列存在，二者并无关系。用于保存具有映射关系的数据：Key-Value。
（3）Map中的key和 value可以是任何引用类型的数据，会封装到HashMap$Node对象中。而在Set中，value是一个常量 new Object（）。
（4）Map中的key不允许重复，原因和HashSet一样。不能有重复元素/对象。当有相同的Key，就等价于保持key不变，替换了value。
（5）Map 中的value可以重复
（6）Map 的key 可以为null, value也可以为null，注意key为null，只能有一个；value为null ,可以多个。
（7）常用String类作为Map的key
（8） key和 value之间存在单向一对一关系，即通过指定的key 总能找到对应的value。
（9）Map存放数据的key-value，一对k-v是放在一个Node中的，有因为Node实现了Entry 接口。
（10）HashMap是 Map 接口使用频率最高的实现类。HashMap是以 key-val对的方式来存储数据(HashMap $Node类型)。
（11）HashMap与HashSet一样，不保证映射的顺序，因为底层是以hash表的方式来存储的。(jdk8的hashMap底层数组+链表+红黑树)
（12）HashMap没有实现同步，因此是线程不安全的，方法没有做同步互斥的操作,没有synchronized。

2. Map接口实现类的特点

（使用实现类 HashMap类为例）

（1）Map接口中有Entry<K,V>接口。
Entry接口中有常用方法：
【1】K getKey();【2】V getValue();【3】V setValue(V value);
【4】int hashCode();【5】boolean equals(Object o);；
（2）HashMap类中有内部类Node<K,V>，该类实现了Entry<K,V>接口，且该类里面有属性：int hash；K key；V value；Node<K,V> next;即k-v最后是存在于Node<K,V>类的对象中。
（3）k-v为了方便程序员的遍历，还会创建EntrySet集合，该集合存放的元素的类型 Entry，而一个Entry对象里面就有k ,v 。EntrySet<Entry<K , V>>即: transient Set<Map.Entry<K, V>> entrySet;
（3）entrySet 中，定义的类型是Map.Entry ，但是实际上存放的还是 HashMap$Node这时因为 static class Node<K, V> implements Map.Entry<K, V>
（4）当把HashHap $ Node对象存放到entrySet就方便我们的遍历，因为 Map.Entrfy提供了重要方法K getKey( ); v getValue( );
【Map存放数据的key-value示意图】

【Map存放数据的key-value示意图2】

3. Map接口常用方法

Map map = new HashMap();

（1）put 增加

map.put("邓超", new Book("", 100));//OK
map.put("邓超", "孙俪"); //替换-> 一会分析源码
map.put("王宝强", "马蓉");//OK
map.put("宋喆", "马蓉");//OK
map.put("刘令博", null);//OK
map.put(null, "刘亦菲");//OK 
map.put("鹿晗", "关晓彤");//OK
map.put("大志", "小梅");

（2）remove：根据键删除映射关系

map.remove(null);

（3）get：根据键获取值

Object val = map.get("鹿晗");

（4）size：获取元素个数

System.out.println("k-v=" + map.size());

（5）isEmpty：判断个数是否为 0

System.out.println(map.isEmpty());

（6）clear：清除 k-v

map.clear();

（7）containsKey：查找键是否存在

System.out.println("结果=" + map.containsKey("大志"));

4. Map遍历方式

（1）containsKey：查找键是否存在

（2）keySet：获取所有的键

（3）values：获取所有的值

（4）entrySet：获取所有关系k-v

	    Map map = new HashMap();
        map.put("邓超", "孙俪");
        map.put("王宝强", "马蓉");
        map.put("宋喆", "马蓉");
        map.put("刘令博", null);
        map.put(null, "刘亦菲");
        map.put("鹿晗", "关晓彤");
（1）方式一：先取出 所有的 Key , 通过 Key 取出对应的 Value。
        Set keyset = map.keySet();
【1】增强 for
        System.out.println("-----第一种方式-------");
        for (Object key : keyset) {
            System.out.println(key + "-" + map.get(key));
        }
【2】 迭代器
        System.out.println("----第二种方式--------");
        Iterator iterator = keyset.iterator();
        while (iterator.hasNext()) {
            Object key = iterator.next();
            System.out.println(key + "-" + map.get(key));
        }
（2）方式二：把所有的 values 取出
        Collection values = map.values();
        这里可以使用所有的 Collections 使用的遍历方法
【1】增强 for
        System.out.println("---取出所有的 value 增强 for----");
        for (Object value : values) {
            System.out.println(value);
        }
【2】迭代器
        System.out.println("---取出所有的 value 迭代器----");
        Iterator iterator2 = values.iterator();
        while (iterator2.hasNext()) {
            Object value = iterator2.next();
            System.out.println(value);
        }
（3）方式三：通过 EntrySet 来获取 k-v
        Set entrySet = map.entrySet();//EntrySet<Map.Entry<K,V>>
【1】增强 for
        System.out.println("----使用 EntrySet 的 for 增强(第 3 种)----");
        for (Object entry : entrySet) {
//将 entry 转成 Map.Entry
            Map.Entry m = (Map.Entry) entry;
            System.out.println(m.getKey() + "-" + m.getValue());
        }
【2】迭代器
        System.out.println("----使用 EntrySet 的 迭代器(第 4 种)----");
        Iterator iterator3 = entrySet.iterator();
        while (iterator3.hasNext()) {
            Object entry = iterator3.next();
//System.out.println(next.getClass());//HashMap$Node -实现-> Map.Entry (getKey,getValue)
//向下转型 Map.Entry
            Map.Entry m = (Map.Entry) entry;
            System.out.println(m.getKey() + "-" + m.getValue());
        }

5. Map三大遍历方式示例

package exercise.chapter14;

import java.util.*;

/**
 * @Package: exercise.chapter14
 * @ClassName: map02
 * @Author: 爱吃凉拌辣芒果
 * @CreateTime: 2021/10/21 23:04
 * @Description:  HashMap练习题
 * 使用HashMap添加3个员工对象, 要求键:员工id  值:员工对象
 * 并遍历显示工资>18000的员工(遍历方式最少两种)
 * 员工类:姓名、工资、员工id
 */
public class map02 {
    public static void main(String[] args) {
        Map map = new HashMap();
        map.put("001",new staff("大志", 15000, "001"));
        map.put("002",new staff("芒果", 20000, "002"));
        map.put("003",new staff("小梅", 25000, "003"));
        //遍历/
    }
}
class staff{
    private String name;
    private double salary;
    private String id;

    public staff(String name, double salary, String id) {
        this.name = name;
        this.salary = salary;
        this.id = id;
    }

    @Override
    public String toString() {
        return "员工：" +
                "name='" + name + '\'' +
                ", salary=" + salary +
                ", id='" + id + '\'' ;
    }

    public String getName() {
        return name;
    }

    public double getSalary() {
        return salary;
    }

    public String getId() {
        return id;
    }
}

方法一：KeySet

（1）使用迭代器

		Set set = map.keySet();
        Iterator ite = set.iterator();
        while (ite.hasNext()) {
            Object next =  ite.next();
            staff sta = (staff) map.get(next);
            if(sta.getSalary()>=18000){
                System.out.println(map.get(next));
            }
        }

（2）使用增强for循环

		//Set set = map.keySet();
        for (Object obj : set) {
            staff sta =(staff)map.get(obj);
            if(sta.getSalary() >= 18000){
                System.out.println(obj+"-"+map.get(obj));
            }
        }

方法二：values

（1）使用迭代器

		Collection values = map.values();
        Iterator iterator = values.iterator();
        while (iterator.hasNext()) {
            staff sta =  (staff)iterator.next();
            if(sta.getSalary() >= 18000){
                System.out.println(sta);
            }
        }

（2）使用增强for循环

		//Collection values = map.values();
		for (Object object : values) {
            staff sta = (staff)object;
            if(sta.getSalary() >= 18000){
                System.out.println(sta);
            }
        }

方法三：entrySet

（1）使用迭代器

		Set set = map.entrySet();
        Iterator iterator = set.iterator();
        while (iterator.hasNext()) {
            Map.Entry ne =  (Map.Entry)iterator.next();
           staff sta = (staff) ne.getValue();
           if(sta.getSalary()>=18000){
               System.out.println(sta);
           }
        }

（2）使用增强for循环

		//Set set = map.entrySet();
		for (Object object : set) {
            Map.Entry ne = (Map.Entry)object;  //这里的ne实际就是一个Node节点，因为Node类
            staff sta = (staff) ne.getValue(); //因为Node类实现了Entry接口。
            if(sta.getSalary()>=18000){
                System.out.println(sta);
            }
        }

6. HashMap底层机制

【HashMap底层机制】

7. HashMap扩容机制

（1）与HashSet相同【 参考HashSet底层源码分析】
（2）HashMap底层维护了Node类型的数组table，默认为null
（3）当创建对象时，将加载因子(loadfactor)初始化为0.75.
（4）当添加key-val时，通过key的哈希值得到在table的索引。然后判断该索引处是否有元素,如果没有元素直接添加。如果该索引处有元素，继续判断该元素的key和准备加入的key相是否等，如果相等，则直接替换val；如果不相等需要判断是树结构还是链表结构，做出相应处理。如果添加时发现容量不够，则需要扩容。
（5）第1次添加，则需要扩容table容量为16，临界值(threshold)为12(16*0.75)
（6）以后再扩容，则需要扩容table容量为原来的2倍(32)，临界值为24，依次类推
（7）在Java8中,如果一条链表的元素个数超过TREEIFY_THRESHOLD(默认是8)，如果此时table的大小>= MIN_TREEIFY_CAPACITY(默认64)，就会进行树化(红黑树)；如果table的大小不超过64，则table表继续以2倍扩容。

五、HashTable类

1. 介绍

（1）存放的元素是键值对：即K-V
（2）hashtable的键和值都不能为null，否则会抛出NullPointerException
（3）hashTable使用方法基本上和HashMap一样
（4）hashTable是线程安全的(synchronized)，hashMap是线程不安全的。

2. 底层机制

（1）底层有数组Hashtable$Entry[ ]来存放节点，初始化大小为11。其中Entry为HashTable的内部类。
（2）临界值 threshold 8 = 11 * 0.75。超过临界值时。扩容为原来的2倍加1

六、Hashtable和 HashMap对比

七、Properties类

1. 介绍

（1）Properties类继承自Hashtable类并且实现了Map接口，也是使用一种键值对的形式来保存数据。
（2）他的使用特点和Hashtable类似
（3）Properties还可以用于从 xxx.properties配置文件中，加载数据到Properties类对象,并进行读取和修改
（4）Properties 继承 Hashtable，可以通过 k-v 存放数据，当然 key 和 value 不能为 null

2. 常用方法

Properties properties = new Properties();

（1）put 增加

//properties.put(null, “abc”);//抛出 空指针异常
//properties.put(“abc”, null); //抛出 空指针异常
properties.put(“john”, 100);//k-v
properties.put(“lucy”, 100);
properties.put(“lic”, 100);
properties.put(“lic”, 88);//如果有相同的 key ， value 被替换

（2）get 通过 k 获取对应值

System.out.println(properties.get(“lic”));//88

（3）remove 删除

properties.remove(“lic”);
System.out.println(“properties=” + properties);

（4）修改

properties.put(“john”, “约翰”);
System.out.println(“properties=” + properties);

八、如何选择集合实现类

1. 先判断存储的类型(一组对象[单列]或一组键值对[双列])

2. 一组对象[单列]：Collection接口

（1）允许重复节点：List
【1】增删多：LinkedList [底层维护了一个双向链表]
【2】改查多：ArrayList [底层维护Object类型的可变数组]
（2）不允许重复：Set
【1】插入和取出没有顺序：HashSet [底层是HashMap，维护了一个哈希表，即数组+链表+红黑树]
【2】可以排序：TreeSet
【3】插入和取出顺序一致：LinkedHashSet，维护数组+双向链表

3. 一组键值对[双列]：Map接口

（1）键无序: HashMap [底层是:哈希表 jdk7：数组+链表，jdk8：数组+链表+红黑树]
（2）键排序：TreeMap
（3）键插入和取出顺序一致：LinkedHashMap
（4）读取文件：Properties

九、TreeSet类

1. 介绍

（1）最大的特点：可以排序
（2）当使用无参构造器没有排序能力；得使用有参的构造器，该有参是实现了comparator接口的对象，涉及到匿名内部类。

2. 底层机制为TreeMap

（1）构造器把传入的比较器对象，赋给了 TreeSet 的底层的 TreeMap 的属性 this.comparator

（2）在调用 treeSet.add(“AAA”), 在底层会执行，其中cpr为我们传入的匿名内部类

（3）由动态绑定机制，跳回到我们传入的匿名内部类中执行compare

十、Collections工具类

1. 介绍

（1）Collections是一个操作Set、List和Map等集合的工具类，包含对集合进行操作的方法。
（2）Collections中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作
（3）如果提供给它们的集合或类对象为null，则此类的方法都抛出一个NullPointerException

2. 方法

List list = new ArrayList();
list.add("tom");
list.add("smith");
list.add("king");
list.add("milan");
list.add("tom");

（1）reverse(List)：反转 List 中元素的顺序

Collections.reverse(list);

（2）shuffle(List)：对 List 集合元素进行随机排序

Collections.shuffle(list);

（3）sort(List)：根据元素的自然顺序对指定 List 集合元素按升序排

Collections.sort(list);

（4）sort(List，Comparator)：根据指定的 Comparator 产生的顺序对 List 集合元素进行排序

Collections.sort(list, new Comparator() {
@Override
public int compare(Object o1, Object o2) {
//可以加入校验代码. 
return ((String) o2).length() - ((String) o1).length();
}
});

（5）swap(List，int， int)：将指定 list 集合中的 i 处元素和 j 处元素进行

Collections.swap(list, 0, 1);

（6）Collections.max(list)：根据元素的自然顺序，返回给定集合中的最大元素

（7）max(Collection，Comparator)：根据 Comparator 指定的顺序，返回给定集合中的最大元素

比如，我们要返回长度最大的元素
Object maxObject = Collections.max(list, new Comparator() {
@Override
public int compare(Object o1, Object o2) {
return ((String)o1).length() - ((String)o2).length();
}
});

（8）Collections.frequency(list, “tom”)：返回指定集合中指定元素的出现次数

（9）Collections.copy(dest, list)：拷贝数组

前提是dest不能为空，否则抛出异常
ArrayList dest = new ArrayList();
//为了完成一个完整拷贝，我们需要先给 dest 赋值，
//大小和 list.size()一样
for(int i = 0; i < list.size(); i++) {
dest.add("");
}
Collections.copy(dest, list);

（10）Collections.replaceAll(list, “tom”, “汤姆”)：使用新值替换 List 对象的所有旧值

如果 list 中有 tom 就替换成汤姆
Collections.replaceAll(list, "tom", "汤姆");

十一、集合练习题