【韩顺平讲Java】Java集合专题 -ArrayList HashMap HashSet List Map TreeMap

01----集合的理解和好处

1. 可以动态保存任意多个对象，比较方便。
2. 提供了一系列操作对象的方法：add(), remove(), set(), get()。

02----集合的框架体系

• 单列集合
• 双列集合

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cotMTIEA-1640566300154)(E:[HanShunping] Java Collection\笔记\01.png)]

03----集合的常用方法

import java.util.ArrayList;
import java.util.List;

public class CollectionMethod {

    public static void main(String[] args) {
        List list = new ArrayList();
        //add 添加元素
        list.add("jack");
        list.add(10);
        list.add(true);
        //remove 删除元素
        list.remove(0); //删除第一个元素
        list.remove(true);
        System.out.println(list);
        //contains 查找元素是否存在
        System.out.println(list.contains("jack"));
        //size 获取元素个数
        System.out.println(list.size());
        //isEmpty 判断是否为空
        System.out.println(list.isEmpty());
        //clear 清空
        list.clear();
        //addAll 添加多个元素
        List list2 = new ArrayList();
        list2.add("wang");
        list2.add(100);
        list.addAll(list2);
        //cintainsAll 查找多个元素是否都存在
        list.containsAll(list2);
        //removeAll 删除多个元素
        list.removeAll(list2);

    }
}

04----迭代器遍历

iterator.hasNext()：判断是否有下一个元素。

import java.util.ArrayList;
import java.util.Iterator;

public class CollectionIterator {

    public static void main(String[] args) {

        ArrayList arrayList = new ArrayList();
        arrayList.add("Wang");
        arrayList.add("Zhao");
        arrayList.add("Qian");
        //生成迭代器
        Iterator iterator = arrayList.iterator();
		
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }
}

05----增强 for 循环

增强 for 底层仍然是迭代器。

for(Object obj : arrayList){
		System.out.println(obj);
}

07----List 接口方法

1. 有序可重复（添加，取出顺序一致）
2. 支持索引
3. 可根据序号存取容器中的元素
4. ArrayList 线程不安全，效率高
5. Vector线程安全
6. LinkedList线程不安全

add(int index, Object ele)：在 index 位置插入 ele 元素

addAll(int index, Collection eles)：从 index 位置开始将 eles 中所有元素添加进去

get(int index)：获取指定位置的元素

indexOf(Object obj)：返回 obj 首次出现的位置

lastIndexOf()：

remove(int index)：删除指定位置的元素，并返回此元素

set(int index, Object ele)：设置指定位置的元素为 ele

subList(int fromIndex, int toIndex)：返回从 fromIndex 到 toIndex 位置的子集合

12----ArrayList 底层结构和源码分析

1. ArrayList中维护了一个Object类型的数组elementData, transient Object[] elementData。
2. 当创建ArrayList对象时，如果使用的是无参构造器，则初始elementData容量为0，第一次添加数据时扩容elementData为10，如需要再次扩容，则按照 1.5倍 增加。
3. 当使用指定大小的构造器时，则初始elementData容量为指定大小，如需要扩容，则按照 1.5倍 增加。

16----Vector 底层结构和源码分析

1. Vector中维护了一个Object类型的数组elementData, transient Object[] elementData。
2. 当创建Vector对象时，如果使用的是无参构造器，则默认elementData容量为10，如需要扩容，则按照 2倍 增加。
3. 当使用指定大小的构造器时，则初始elementData容量为指定大小，如需要扩容，则按照 2倍 增加。

17----LinkedList 底层结构和源码分析

- LinkedList的底层操作机制

1. LinkedList底层维护了一个双向链表
2. 维护了两个属性first和last分别指向首节点和尾节点
3. 每个节点Node对象里面又维护了prev,next,item三个属性，其中通过prev指向前一个，next指向后一个节点，最终实现双向链表
4. 所以LinkedList的元素的添加和删除不是通过数组完成的，相对说效率较高

20----Set接口和常用方法

1. 无序不可重复
2. 没有索引

21----HashSet

1. HashSet实现了Set接口
2. HashSet实际上是HashMap
3. 可以存放null值，但只能有一个
4. HashSet不保证元素是有序的，取决于hash后，再确定索引结果
5. 元素，对象不可重复

经典Java面试题：

Set set = new HashSet();

set.add(new Dog("tom"));	//Ok
set.add(new Dog("tom"));	//Ok

set.add(new String("hsp"));	//Ok
set.add(new String("hsp"));	//false

---

22----数组链表模拟

Node[] table = new Node[16];

Node john = new Node("john", null);
table[2] = john;
Node jack = new Node("jack", null);
john.next = jack;	//jack挂载到john后

class Node{
    Object item;
    Node next;	//单向链表
    public Node(Object item, Node next){
        this.item = item;
        this.next = next;
    }
}

23----HashSet扩容机制

• 分析HashSet的添加元素底层是如何实现的（hash()+equals()）

  1. HashSet底层是HashMap
  2. 添加一个元素时，先得到hash值，然后转成索引值
  3. 找到存储数据表table，看这个索引值位置是否已经存放有元素
  4. 如果没有，则直接存入
  5. 如果有，调用equals比较，如果相同就放弃添加，若果不同，则向后添加
  6. 在java8中，如果一条链表的元素个数超过默认8，且table的大小大于等于默认64时，则进行树化（红黑树）

• 分析HashSet的扩容和转成红黑树的机制

  1. HashSet底层是HashMap，第一次添加时，table数组扩容到16，临界值是16*0.75（加载因子）=12
  2. 如果table数组到了临界值12，就会扩容到16×2（2倍扩容）=32，新的临界值就是24，以此类推
  3. 在java8中，只有一条链表的元素个数超过默认8，且table的大小大于等于默认64时，才会进行树化（红黑树），否则仍采用数组扩容机制

• 加载因子为何是0.75？

  1. 加载因子越大hash表（table）数据密度越大，发生碰撞的几率越高，数组（table）中的链表越容易长，造成查询或插入时的比较次数增多，性能会下降。
  2. 加载因子越小，就越容易触发扩容，数据密度也越小，意味着发生碰撞的几率越小，数组中的链表也就越短，查询和插入时比较的次数也越小，性能会更高。但是会浪费一定的内存空间。而且经常扩容也会影响性能。
  3. 源码中有：在理想情况下,使用随机哈希码,节点出现的频率在hash桶中遵循泊松分布，当桶中元素到达8个的时候，概率已经变得非常小，也就是说用0.75作为加载因子，每个碰撞位置的链表长度超过８个是几乎不可能的。

28----HashSet最佳实战

import java.util.HashSet;
import java.util.Objects;

public class HashSetExc {
    public static void main(String[] args) {

        HashSet hashSet = new HashSet();
        hashSet.add(new Employee("milan",18));
        hashSet.add(new Employee("jackie",28));
        hashSet.add(new Employee("milan",18));
        // 若果不重写equals方法，则三个对象是不同对象都能被添加
        // 重写后名字年龄相同的对象视为相同对象，则第三个对象无法添加
        System.out.println("hashSet == "+ hashSet);
    }

}

class Employee{
    private String name;
    private int age;

    public Employee() {
    }

    public Employee(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

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

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Employee employee = (Employee) o;
        return age == employee.age && Objects.equals(name, employee.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

33----Map接口特点

1. Map用于保存具有映射关系的数据：Key-Value
2. Map中的Key和Value可以是任何引用类型的数据
3. Map中的Key不允许重复，原因和HashSet一样
4. Map中的Value可以重复
5. Map中的Key可以为null，value也可以为null，注意key为null只能有一个
6. 常用String类作为Map中的key
7. key和value存在单向一一对应关系，即通过指定key总能找到对应的value
8. Map的k-v存放在Node中

35----Map的常用方法

1. put：添加
2. remove：根据key删除映射关系
3. get：根据key获取值
4. size：获取元素个数
5. isEmpty：判断是否为空
6. clear：清除
7. containsKey：查找key是否存在

39----HashMap扩容机制

• 扩容机制和HashSet相同
  1. HashMap底层维护了Node类型的数组table，默认为null
  2. 当创建HashMap对象时，将加载因子（loadfactor）初始化为0.75
  3. 当添加k-v时，通过key的hash值得到在table的索引，然后判断该索引处是否有元素，如果么有则直接添加；如果有则继续判断该元素的key是否和准备加入的元素key相等，如果相等则替换value，如果不相等需要判断是树结构还是链表结构做出相应处理。如果添加时发现容量不够，则需要扩容
  4. 第一次添加元素则需要扩容table容量为16，临界值12
  5. 以后再扩容，按照***2倍***增加
  6. 在java8中，如果一条链表的元素个数超过默认8，且table的大小大于等于默认64时，则进行树化（红黑树）

42----HashTable基本介绍

1. 存放的元素是键值对：k-v
2. 键和值都不能为null
3. 使用方法与HashMap基本一致
4. HashMap线程不安全，HashTable线程安全（加了同步synchronized）

43----HashTable扩容

1. 底层有数组Hashtable$Entry[]，初始化大小为11
2. 临界值：11*0.75=8
3. 当大于临界值时，按照***2倍+1***的方式扩容

HashMap与HashTable的对比：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-W4RRxSla-1640566300157)(https://www.bilibili.com/video/BV1YA411T76k?p=43)]

45----开发中如何选择集合实现类

1. 先判断存储的类型（一组对象【单列】或一组键值对【双列】）
2. 一组对象：Collection接口
   • 允许重复：List (有序可重复)
     • 增删多：LinkedList【底层维护了一个双向链表】
     • 改查多：ArrayList【底层维护了Object类型的可变数组】
   • 不许重复：Set (无序不可重复)
     • 无序：HashSet【底层是HashMap，维护了哈希表，即数组+链表+红黑树】
     • 排序：TreeSet
     • 插入和取出顺序一致：LinkedHashSet【维护了数组+双向链表】
3. 一组键值对：Map
   • 键无序：HashMap【底层是哈希表（jdk1.7：数组+链表，jdk1.8：数组+链表+红黑树）】
   • 键排序：TreeMap
   • 键插入和取出顺序一致：LinkedHashMap
   • 读取文件：Properties

46----TreeSet介绍

1. 当使用无参构造器new TreeSet()时，仍然是无序的
2. 使用TreeSet提供的一个构造器，可以传入比较器，从而使得其有序

47----TreeMap介绍

与TreeSet基本一致，区别在于TreeMap存入的是键值对k-v

1. 当使用无参构造器new TreeSet()时，仍然是无序的
2. 使用TreeSet提供的一个构造器，可以传入比较器，从而使得其有序

48----Collections工具类

1. Collections是一个操作Set，List，Map等集合的工具类
2. 提供了一系列方法

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;

public class Collections_ {
    public static void main(String[] args) {

        ArrayList arrayList = new ArrayList();
        arrayList.add("Jack");
        arrayList.add("Tom");
        arrayList.add("Moon");
        arrayList.add("McGrady");
        System.out.println(arrayList);

        //reverse(List):翻转其中元素
        Collections.reverse(arrayList);
        System.out.println(arrayList);
        //shuffle(List):随机排序
        Collections.shuffle(arrayList);
        System.out.println(arrayList);
        //sort(List):根据元素自然顺序排序
        Collections.sort(arrayList);
        System.out.println(arrayList);
        //sort(List,Comparator):根据指定的比较器对其排序
        Collections.sort(arrayList, new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                return ((String)o1).length() - ((String)o2).length();
            }
        });
        System.out.println("按字符串长度排序："+arrayList);
        //swap(List,int,int):交换i和j处的元素
        Collections.swap(arrayList,0,3);
        System.out.println(arrayList);
        
        
        //Object max(Collection):根据元素自然排序，返回集合中最大元素
        //Object max(Collection,Comparator):
        //Object min(Collection):
        //Object min(Collection,Comparator):
        //int frequency(Collection,Object):返回指定元素的出现次数
        //void copy(List dest,List src):将src内容复制到dest中，注意dest必须大于等于src的长度
        //boolean replaceAll(List list, Object oldVal, Object newVal):用新值替换list中的旧值

    }
}

50----作业

作业一：

import java.util.ArrayList;

@SuppressWarnings({"all"})
public class Homework01 {
    public static void main(String[] args) {
        ArrayList arrayList = new ArrayList();
        arrayList.add(new News("新冠确诊病例超千万，数百万印度教信徒赴恒河\"圣浴\"引民众担忧"));
        arrayList.add(new News("男子突然想起2个月前钓的鱼还在网兜里，捞起一看赶紧放生"));

        int size = arrayList.size();
        //倒序遍历
        for (int i = size - 1; i >= 0; i--) {
            //System.out.println(arrayList.get(i));
            News news = (News)arrayList.get(i);
            System.out.println(processTitle(news.getTitle()));
        }

    }
    //专门写一个方法，处理现实新闻标题 process处理
    public static String processTitle(String title) {

        if(title == null) {
            return "";
        }

        if(title.length() > 15) {
            return title.substring(0, 15) + "..."; //[0,15)
        } else {
            return title;
        }

    }
}

/**
 * 按要求实现：
 * (1) 封装一个新闻类，包含标题和内容属性，提供get、set方法，重写toString方法，打印对象时只打印标题；
 * (2) 只提供一个带参数的构造器，实例化对象时，只初始化标题；并且实例化两个对象：
 * 新闻一：新冠确诊病例超千万，数百万印度教信徒赴恒河“圣浴”引民众担忧
 * 新闻二：男子突然想起2个月前钓的鱼还在网兜里，捞起一看赶紧放生
 * (3) 将新闻对象添加到ArrayList集合中，并且进行倒序遍历；
 * (4) 在遍历集合过程中，对新闻标题进行处理，超过15字的只保留前15个，然后在后边加“…”
 * (5) 在控制台打印遍历出经过处理的新闻标题；
 */
class News {
    private String title;
    private String content;

    public News(String title) {
        this.title = title;
    }

    public String getTitle() {
        return title;
    }

    public void setTitle(String title) {
        this.title = title;
    }

    public String getContent() {
        return content;
    }

    public void setContent(String content) {
        this.content = content;
    }

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

作业二：

import java.util.ArrayList;
import java.util.Iterator;

@SuppressWarnings({"all"})
public class Homework02 {
    public static void main(String[] args) {

        ArrayList arrayList = new ArrayList();
        Car car = new Car("宝马", 400000);
        Car car2 = new Car("宾利",5000000);
        //1.add:添加单个元素
        arrayList.add(car);
        arrayList.add(car2);
        System.out.println(arrayList);
        //* 2.remove:删除指定元素
        arrayList.remove(car);
        System.out.println(arrayList);
        //* 3.contains:查找元素是否存在
        System.out.println(arrayList.contains(car));//F
        //* 4.size:获取元素个数
        System.out.println(arrayList.size());//1
        //* 5.isEmpty:判断是否为空
        System.out.println(arrayList.isEmpty());//F
        //* 6.clear:清空
        //System.out.println(arrayList.clear(););
        //* 7.addAll:添加多个元素
        System.out.println(arrayList);
        arrayList.addAll(arrayList);//2个宾利
        System.out.println(arrayList);
        //* 8.containsAll:查找多个元素是否都存在
        arrayList.containsAll(arrayList);//T
        //* 9.removeAll：删除多个元素
        //arrayList.removeAll(arrayList); //相当于清空
        //* 使用增强for和 迭代器来遍历所有的car , 需要重写 Car 的toString方法

        for (Object o : arrayList) {
            System.out.println(o);//
        }
        System.out.println("===迭代器===");
        Iterator iterator = arrayList.iterator();
        while (iterator.hasNext()) {
            Object next =  iterator.next();
            System.out.println(next);

        }

    }
}
/**
 * 使用ArrayList 完成对 对象 Car {name, price} 的各种操作
 * 1.add:添加单个元素
 * 2.remove:删除指定元素
 * 3.contains:查找元素是否存在
 * 4.size:获取元素个数
 * 5.isEmpty:判断是否为空
 * 6.clear:清空
 * 7.addAll:添加多个元素
 * 8.containsAll:查找多个元素是否都存在
 * 9.removeAll：删除多个元素
 * 使用增强for和 迭代器来遍历所有的car , 需要重写 Car 的toString方法
 */
class Car {
    private String name;
    private double price;

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

    public String getName() {
        return name;
    }

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

    public double getPrice() {
        return price;
    }

    public void setPrice(double price) {
        this.price = price;
    }

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

作业三：

import java.util.*;

@SuppressWarnings({"all"})
public class Homework03 {
    public static void main(String[] args) {

        Map m = new HashMap();
        m.put("jack", 650);//int->Integer
        m.put("tom", 1200);//int->Integer
        m.put("smith", 2900);//int->Integer
        System.out.println(m);

        m.put("jack", 2600);//替换，更新
        System.out.println(m);

        //为所有员工工资加薪100元；
        //keySet
        Set keySet = m.keySet();
        for (Object key : keySet) {
            //更新
            m.put(key, (Integer)m.get(key) + 100);
        }
        System.out.println(m);

        System.out.println("=============遍历=============");
        //遍历 EntrySet
        Set entrySet = m.entrySet();
        //迭代器
        Iterator iterator = entrySet.iterator();
        while (iterator.hasNext()) {
            Map.Entry entry =  (Map.Entry)iterator.next();
            System.out.println(entry.getKey() + "-" + entry.getValue());

        }

        System.out.println("====遍历所有的工资====");
        Collection values = m.values();
        for (Object value : values) {
            System.out.println("工资=" + value);
        }

    }
}
/**
 * 按要求完成下列任务
 * 1）使用HashMap类实例化一个Map类型的对象m，键（String）和值（int）分别用于存储员工的姓名和工资，
 * 存入数据如下：	jack—650元；tom—1200元；smith——2900元；
 * 2）将jack的工资更改为2600元
 * 3）为所有员工工资加薪100元；
 * 4）遍历集合中所有的员工
 * 5）遍历集合中所有的工资
 */

作业四：试分析HashSet和TreeSet分别如何实现去重？

1. HashSet的去重机制：hashcode()+equals()，底层先通过存入的对象运算得到一个hash值，通过hash值得到对应的索引，如果发现table索引值所在的位置没有数据，就直接存放；如果有数据，就使用equals()比较，比较后如果不相同就加入，否则不加入。
2. TreeSet的去重机制：如果传入了一个Comparator匿名对象，就使用实现的compare()去重，如果方法返回0，就认为是相同的元素，不添加；如果没有传入Comparator匿名对象，则以添加的对象实现的Comparable接口的compareTo()方法去重。

import com.hspedu.map_.TreeMap_;

import java.util.TreeMap;
import java.util.TreeSet;

@SuppressWarnings({"all"})
public class Homework04 {
    public static void main(String[] args) {

        TreeSet treeSet = new TreeSet();
        treeSet.add("hsp");
        treeSet.add("tom");
        treeSet.add("king");
        treeSet.add("hsp");//加入不了, 因为String的compareTo()方法比较的是内容
        System.out.println(treeSet);

    }
}

作业五：

//import java.util.TreeSet;

//@SuppressWarnings({"all"})
//public class Homework05 {
//    public static void main(String[] args) {
//        TreeSet treeSet = new TreeSet();
//        //分析源码
//        //add 方法，因为 TreeSet() 构造器没有传入Comparator接口的匿名内部类
//        //所以在底层 Comparable<? super K> k = (Comparable<? super K>) key;
//        //即 把 Perosn转成 Comparable类型
//        treeSet.add(new Person());//ClassCastException.
//        treeSet.add(new Person());//ClassCastException.
//        treeSet.add(new Person());//ClassCastException.
//        treeSet.add(new Person());//ClassCastException.
//        treeSet.add(new Person());//ClassCastException.
//
//        System.out.println(treeSet);
//
//    }
//}
//
//class Person implements Comparable{
//
//    @Override
//    public int compareTo(Object o) {
//        return 0;
//    }
//}

作业六：

import java.util.HashSet;
import java.util.Objects;

@SuppressWarnings({"all"})
public class Homework06 {
    public static void main(String[] args) {
        HashSet set = new HashSet();//ok
        Person p1 = new Person(1001,"AA");//ok
        Person p2 = new Person(1002,"BB");//ok
        set.add(p1);//ok
        set.add(p2);//ok
        p1.name = "CC";
        set.remove(p1);	//找不到1001，CC的hash值所表示的索引，因为AA-》CC，不改变1001，AA的hash值
        System.out.println(set);//2
        set.add(new Person(1001,"CC"));
        System.out.println(set);//3
        set.add(new Person(1001,"AA"));
        System.out.println(set);//4

    }
}

class Person {
    public String name;
    public int id;

    public Person(int id, String name) {
        this.name = name;
        this.id = id;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return id == person.id &&
                Objects.equals(name, person.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, id);
    }

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

//===========================结果=================================
/*[Person{name='BB', id=1002}, Person{name='CC', id=1001}]
[Person{name='BB', id=1002}, Person{name='CC', id=1001}, Person{name='CC', id=1001}]
[Person{name='BB', id=1002}, Person{name='CC', id=1001}, Person{name='CC', id=1001}, Person{name='AA', id=1001}]
*/