Set与Map

第一章 Set 1 Set 1.1 理解

Set : 无序,不可重复|去重

无序: 存放的顺序与内部真实存储的顺序不一致去重: 集合不包含元素对e1和e2 ，使得e1.equals(e2)和最多一个null元素。 1.2 新增功能

static Set of(E… elements) 返回包含任意数量元素的不可修改集。 1.3 遍历方式

foreachiterator迭代器 1.4 代码

public class Class001_Set {
    public static void main(String[] args) {
        Set set = new HashSet<>();
        set.add("ddd");
        set.add("aaa");
        set.add("ccc");
        set.add("bbb");
        set.add("bbb");
        set.add("bbb");
        set.add(null);
        set.add(null);
        set.add(null);
        System.out.println(set);

        System.out.println("----------foreach--------------");
        for(String str:set){
            System.out.println(str);
        }

        System.out.println("----------iterator迭代器--------------");
        Iterator it = set.iterator();
        while(it.hasNext()){
            System.out.println(it.next());
        }
    }
}

2 TreeSet 2.1 底层结构

红黑树底层是由TreeMap维护的，本质是TreeMap 2.2 特点

查询效率较高,自动把数据做升序排序 2.3 新增功能

新增了一些与比较大小相关的方法E ceiling(E e) 返回此set中大于或等于给定元素的 null元素，如果没有这样的元素，则 null 。E floor(E e) 返回此set中小于或等于给定元素的最大元素，如果没有这样的元素，则 null 。E first() 返回此集合中当前的第一个（最低）元素。E last() 返回此集合中当前的最后一个（最高）元素。E higher(E e) 返回此集合中的最小元素严格大于给定元素，如果没有这样的元素，则 null 。E lower(E e) 返回此集合中的最大元素严格小于给定元素，如果没有这样的元素，则 null 。E pollFirst() 检索并删除第一个（最低）元素，如果此组为空，则返回 null 。E pollLast() 检索并删除最后一个（最高）元素，如果此集合为空，则返回 null 2.4 遍历方式

foreachiterator迭代器 2.5 注意

TreeSet需要存储相同类型的数据,因为会默认存在比较排序 2.6 代码

public class Class002_TreeSet {
    public static void main(String[] args) {
        TreeSet tree = new TreeSet();
        tree.add(3.2);
        tree.add(2.2);
        tree.add(5.2);
        tree.add(1.2);
        tree.add(.2);
        System.out.println(tree);

        TreeSet tree2 = new TreeSet();
        tree2.add("bc");
        tree2.add("ab");
        tree2.add("a");
        tree2.add("abc");
        System.out.println(tree2);

        //E ceiling(E e) 返回此set中大于或等于给定元素的 null元素，如果没有这样的元素，则 null 。
        System.out.println(tree.ceiling(2.3));

        //E floor(E e) 返回此set中小于或等于给定元素的最大元素，如果没有这样的元素，则 null 。
        System.out.println(tree.floor(2.3));

        //E first() 返回此集合中当前的第一个（最低）元素。
        System.out.println(tree.first());

        //E last() 返回此集合中当前的最后一个（最高）元素。
        System.out.println(tree.last());
        //E higher(E e) 返回此集合中的最小元素严格大于给定元素，如果没有这样的元素，则 null 。
        System.out.println(tree.higher(2.2));
        //E lower(E e) 返回此集合中的最大元素严格小于给定元素，如果没有这样的元素，则 null 。
        System.out.println(tree.lower(2.3));
        //E pollFirst() 检索并删除第一个（最低）元素，如果此组为空，则返回 null 。
        //E pollLast() 检索并删除最后一个（最高）元素，如果此集合为空，则返回 null 。
        System.out.println(tree.pollFirst());
        System.out.println(tree);
        System.out.println(tree.pollLast());
        System.out.println(tree);

    }
}

3 比较器

TreeSet存储javabean类型的数据
去重与排序: 都是根据比较规则实现的,与equals没有关系比较规则:

内部比较器|内部比较规则|自然排序 : 比较规则定义在javabean类型的内部
javabean类型实现Comparable接口,重写compareTo(T o)方法,在方法中定义比较规则外部比较器|外部比较规则|定制排序 : 比较规则定义在javabean类型的外部
定义一个实现类,实现Comparator接口,重写int compare(T o1, T o2),在方法中定义比较规则 Arrays.sort(数组) 默认升序排序
static void sort(T[] a, Comparator c) 根据指定比较器引发的顺序对指定的对象数组进行排序。
练习: 定义一个存储javabean数据的数组,通过 Arrays.sort对数据做升序排序 3.1 员工类

定义自然排序方式
两个对象 e1,e2
e1.compareTo(e2)
大小由返回值决定 :
0 ---------> e1==e2
<0 --------> e1 >0 --------> e1>e2TreeSet在做排序的时候: 把两个数据e1,e2调用compareTo看返回值决定大小,默认升序排序,小的放在前面,大的放在后面注意: TreeSet就是根据指定的比较规则,对数据做默认的升序排序
但是可以根据自定义的比较方式的实现,真实的实现根据指定内容升序|降序

//员工类
public class Employee implements Comparable{
    private int id;
    private String name;
    private double salary;

    public Employee() {
    }

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

    public int getId() {
        return id;
    }

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

    public String getName() {
        return name;
    }

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

    public double getSalary() {
        return salary;
    }

    public void setSalary(double salary) {
        this.salary = salary;
    }

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

    
    @Override
    public int compareTo(Employee o) {
        //e1-->this   e2-->o
        //return this.name.compareTo(o.name);
         return this.id-o.id;
    }
}

3.2 内部比较器

 public static void main(String[] args) {
 		TreeSet tree = new TreeSet<>();
 	 	tree.add(new Employee(02,"zhangsan",10000));
        tree.add(new Employee(01,"lisi",12000));
        tree.add(new Employee(03,"wangwu",8000));

        System.out.println(tree);
        }

3.3 外部比较器

调用compare方法做两个数据的比较
compare(t1,t2)
返回值:
=0 t1==t2
<0 t1 >0 t1>t2匿名内部类 : 简化没有类自己作用的实现类Lambda : 简化匿名内部类对象,要求必须为函数式接口才能简化

public class Class003_Comparable {
    public static void main(String[] args) {
        //TreeSet tree = new TreeSet<>();  //根据Employee默认比较规则,自然排序方式做比较排序
        //TreeSet(Comparator comparator) 构造一个新的空树集，根据指定的比较器进行排序。
        //TreeSet tree = new TreeSet<>(new Test());

        //匿名内部类 : 简化没有类自己作用的实现类
        Comparator com = new Comparator() {//实现类的类体
            @Override
            public int compare(Employee o1, Employee o2) {
                return Double.compare(o1.getSalary(),o2.getSalary());
            }

        };

        //Lambda : 简化匿名内部类对象,要求必须为函数式接口才能简化
        //com = (o1,o2)->o1.getId()-o2.getId();

        //TreeSet tree = new TreeSet<>(com);
        //lambda表达式作为实参传递 -> 可以把行为作为参数传递
        TreeSet tree = new TreeSet<>((o1,o2)->o1.getId()-o2.getId());
        tree.add(new Employee(02,"zhangsan",10000));
        tree.add(new Employee(01,"lisi",12000));
        tree.add(new Employee(03,"wangwu",8000));

        System.out.println(tree);

    }
}

//外部比较器
class Test implements Comparator{
    
    @Override
    public int compare(Employee o1, Employee o2) {
        return Double.compare(o2.getSalary(),o1.getSalary());
    }
}

3.4 练习

public static void main(String[] args) {
        ArrayList emp = new ArrayList<>();
        emp.add(new Employee(02,"zhangsan",10000));
        emp.add(new Employee(01,"lisi",12000));
        emp.add(new Employee(03,"wangwu",8000));

        Collections.sort(emp);
        
        System.out.println(emp);
    }

4 HashSet 4.1 List与Set

List 有序可重复Set 无序不可重复

TreeSet : 默认升序排序 4.2 底层结构

哈希表(数组+链表+红黑树)

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IxtCldrU-1647995516255)(E:program安装资料笔记工具MarkdownPictures容器集合哈希表.png)]

4.3 特点

查询,增删效率高 ,去重,无序底层是由HashMap维护的 4.4 遍历

foreachiterator迭代器 4.5 新增方法

无 4.6 注意

此类允许null元素。请注意，此实现不同步。 4.7 练习

定义HashSet存储javabean类型得到数据,实现去重,测试使用去重 : 数据的类型要求重写hashCode与equals方法，返回地址值需要重写toString 4.8 代码

public class Class004_HashSet {
    public static void main(String[] args) {
        System.out.println("abc".hashCode());
        System.out.println(new Person("zhangsan",18).hashCode());
        System.out.println(new Person("zhangsan",18).hashCode());
        System.out.println(new Integer(105).hashCode());

        HashSet set = new HashSet();
        set.add("");
    }
}
class Person{
    private String name;
    private int age;

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

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

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

4.9 练习代码

public class Class004_HashSet {
    public static void main(String[] args) {
        System.out.println("abc".hashCode());
        System.out.println(new Person("zhangsan",18).hashCode());
        System.out.println(new Person("zhangsan",18).hashCode());
        System.out.println(new Integer(105).hashCode());

        Set set = new HashSet();
        set.add("张三");
        set.add("张三");
        Person p1 = new Person("张三",18);
        Person p2 = new Person("张三",18);
        Person p3 = new Person("李四",18);


        HashSet set1 = new HashSet<>();
        set1.add(p1);
        set1.add(p2);
        set1.add(p3);
        System.out.println(set1);
        for(Person p :set1){
            System.out.println(p);
        }

        System.out.println(set);

    }
}
class Person{
    private String name;
    private int age;

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

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

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

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

第二章 Map 1 Map 1.1 理解

Map : 无序的,去重的键值对数据的集合键值对->映射关系键值对: K-VK键 : 无序的,去重的|唯一的 —> SetV值 : 无序的,可重复 —> CollectionK-V可以为任意引用数据类型 1.2 特点

一个key只能对应一个Valuekey相同value覆盖 1.3 遍历方式

values 获取所有键值对的值
Collection values() 返回此映射中包含的值的Collection视图。keySet 获取所有键值对的key,根据key获取value
Set keySet() 返回此映射中包含的键的Set视图。entrySet 获取所有的键值对,每一个键值对都是一个Entry类型->表示一个键值对
Set> entrySet() 返回此映射中包含的映射的Set视图。 1.4 代码

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

        //V put(K key, V value) 将指定的值与此映射中的指定键相关联（可选操作）。
        map.put(101,"胡歌");
        map.put(103,"彭于晏");
        map.put(102,"吴彦祖");
        map.put(null,null);
        map.put(105,null);
        System.out.println(map.put(104,"王渊"));

        System.out.println(map);
        System.out.println( map.put(102,"金城武"));
        System.out.println(map);

        //V get(Object key) 返回指定键映射到的值，如果此映射不包含键的映射，则返回 null 。
        System.out.println(map.get(103));
        //void clear() 从此映射中删除所有映射（可选操作）。
        //boolean isEmpty() 如果此映射不包含键 - 值映射，则返回 true 。

        //boolean containsKey(Object key) 如果此映射包含指定键的映射，则返回 true 。
        System.out.println(map.containsKey(null));

        //boolean containsValue(Object value) 如果此映射将一个或多个键映射到指定值，则返回 true 。
        System.out.println(map.containsValue(null));

        //static  Map of(K k1, V v1) 返回包含单个映射的不可修改的映射。
        Map map2 = Map.of("xixi",true,"haha",false);
        //map2.put("heihei",false); //java.lang.UnsupportedOperationException
        System.out.println(map2);

        //V remove(Object key) 如果存在，则从该映射中移除键的映射（可选操作）。
        System.out.println(map.remove(101));

        //default V replace(K key, V value) 仅当指定键当前映射到某个值时，才替换该条目的条目。
        System.out.println(map.replace(105,"宋承宪"));
        System.out.println(map);

        //int size() 返回此映射中键 - 值映射的数量。
        System.out.println(map.size());

        //遍历
        System.out.println("-----------------values-----------------");
        Collection values = map.values();
        for(String value:values){
            System.out.println(value);
        }
        
        Iterator it1 = v.iterator();
        while (it1.hasNext()) {
            System.out.println(it1.next());
        }

        System.out.println("-----------------keySet-----------------");
        Set set = map.keySet();
        Iterator it = set.iterator();
        while(it.hasNext()){
            Integer key = it.next();
            System.out.println(key+"--->"+map.get(key));
        }

        System.out.println("---------------entrySet-----------------");
        Set> entrys = map.entrySet();
        for(Map.Entry entry:entrys){
            System.out.println(entry.getKey()+"--->"+entry.getValue());
        }
    }
}

2 TreeMap 2.1 理解

底层: 红黑树存储键值对类型的数据,自动升序排序,去重的去重,排序: 根据键值对的key实现,与value本身无关TreeSet底层是由TreeMap请注意，此实现不同步。 2.2 练习

测试: 使用TreeMap存储键值对数据,key要求为javabean类型教师数据,value存储教授学科,测试存储练习
是否可以根据key实现去重
测试是否为升序排序,要求根据教师编号做升序排序 2.3 去重|排序

根据key的类型的比较规则
key的数据类型实现内部比较器
传递外部比较规则 2.4 代码

public class Class002_TreeMap {
    public static void main(String[] args) {
        //TreeMap map = new TreeMap<>(); 根据key的数据类型Teacher默认比较规则
        TreeMap map = new TreeMap<>((o1,o2) ->o2.getNo()-o1.getNo()); //根据参数的比较规则对Key的Teacher做比较
        map.put(new Teacher(101,"老薛","JAVA"),"JAVA");
        map.put(new Teacher(103,"宝玉","JAVA"),"JAVA");
        map.put(new Teacher(104,"李老师","JAVA"),"JAVA");
        map.put(new Teacher(102,"李毅大帝","DB"),"DB");

        System.out.println(map);
    }
}

class Teacher implements Comparable{
    private int no;
    private String name;
    private String subject;

    public Teacher() {
    }

    public Teacher(int no, String name, String subject) {
        this.no = no;
        this.name = name;
        this.subject = subject;
    }

    public int getNo() {
        return no;
    }

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

    public String getName() {
        return name;
    }

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

    public String getSubject() {
        return subject;
    }

    public void setSubject(String subject) {
        this.subject = subject;
    }

    @Override
    public String toString() {
        return "Teacher{" +
                "no=" + no +
                ", name='" + name + ''' +
                ", subject='" + subject + ''' +
                '}';
    }

    @Override
    public int compareTo(Teacher o) {
        return this.no-o.no;
    }
}

3 HashMap 3.1 HashMap

基于哈希表的Map接口的实现。此实现提供了所有可选的映射操作，并允许null值和null键。HashSet 底层是由HashMap底层结构 : 哈希表(数组+链表+红黑树) 3.2 哈希表 3.2.1 理解

数组 : 节点数组Node[] --> 要求数组的长度为2的整数次幂
Node : int hash,Object key,Object value,Node next每个索引位置存储的为一个单向链表的首节点(尾插法)当链表的长度>8,数组的长度>64,会把链表优化成为红黑树当链表的长度>8,但是数组的长度不大于64,这时候会实现扩容(数组的扩容) 3.2.2 初始容量

哈希表中的数组默认的初始长度 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16数组的容量最大容量 : static final int MAXIMUM_CAPACITY = 1 << 30; 3.2.3 加载因子

0.75 一般不建议改变默认加载因子 : static final float DEFAULT_LOAD_FACTOR = 0.75f; 3.2.4 扩容阀值 threshold

扩容的临界值数据的个数size>数组的长度*加载因子就会扩容 3.2.5 扩容机制

原容量的2倍 int newCap = oldCap << 1 3.2.6 新增功能:

无 3.2.7 HashMap的哈希表存储数据的过程

根据key计算哈希值
通过key的hashCode方法的返回值进一步进行hash算法的运算,得到的整数
int hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

调用putVal方法实现添加数据(hash,key,value)
1)判断是否是第一次调用put方法做添加 if ((tab = table) == null || (n = tab.length) == 0)
如果是第一次添加,直接调用resize()实现扩容
2)计算位桶的索引 int index = (n - 1) & hash
3)判断哈希表结构的数组table[index]是否存在数据,
如果不存在数据,证明没有头节点,创建新节点,放入当前数组的对应索引位置作为头节点
table[index] = new Node<>(hash, key, value, next);
size数据的个数+1,判断是否>扩容的阀值,如果大于需要调用resize方法进行扩容,如果不大于,不需要扩容直接返回null
if (++size > threshold) resize();
return null;
如果存在数据,作为链表的头结点,遍历这个链表,拿到每一个节点的key与hash值判断是否与要添加的key和hash相同,如果相同,value覆盖
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
value覆盖之后,返回被覆盖的value
V oldValue = e.value;
e.value = value;
return oldValue;

3.2.8 去重

去重 : 根据key做去重,要求key的数据类型重写hashCode与equals方法 3.2.9 练习

测试: 定义HashMap存储数据,要求key为javabean,实现去重与测试 3.2.10 练习代码

public class Class003_HashMap {
    public static void main(String[] args) {
        HashMap map = new HashMap<>();

        map.put(101,"张三");
        map.put(101,"张三");
        map.put(102,"李四");
        System.out.println(map);
    }
}

class Student{
    private int no;
    private String name;

    public Student() {
    }

    public Student(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

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

    public String getName() {
        return name;
    }

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

    @Override
    public String toString() {
        return "Student{" +
                "no=" + no +
                ", name='" + name + ''' +
                '}';
    }

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

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

3.3 Hashtable 与 HashMap 3.3.1 区别

共同点 : 都是Map接口的实现类,底层结构都是哈希表

异同点 :
1.继承体系不同
2.线程是否安全不同
HashMap 线程不安全|不同步
Hashtable 线程安全的|同步的
3.扩容机制不同
HashMap扩容机制 : 每次扩容原容量的2倍
int newCap = oldCap << 1
Hashtable扩容机制 : 原容量的2倍+1
int newCapacity = (oldCapacity << 1) + 1;
4.键值对数据null值的要求不同
HashMap 可以存储null值的key与value
Hashtable key与value都不为null

5.计算hash值与位桶索引index的算法不同
HashMap :
int hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
int index = (n - 1) & hash
Hashtable :
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

3.3.2 解决线程不安全

如何处理HashMap线程不安全问题:
1.使用Hashtable
2.使用Collections工具类中static Map synchronizedMap(Map m) 返回由指定映射支持的同步（线程安全）映射。
3.juc高级并发编程包 ConcurrentHashMap-> 线程安全的哈希表第五章 Collections工具类 1 理解 Collections

操作集合的工具类静态工厂 2 方法

void sort(List) //对List容器内的元素排序,排序的规则是按照升序进行排序。void shuffle(List) //对List容器内的元素进行随机排列void reverse(List) //对List容器内的元素进行逆续排列void fill(List, Object) //用一个特定的对象重写整个List容器int binarySearch(List, Object)//对于顺序的List容器，采用折半查找的方法查找特定对象 3 代码

public class Class001_Collections {
    public static void main(String[] args) {
        List list= new ArrayList<>();
        list.add(5);
        list.add(3);
        list.add(1);
        list.add(2);
        list.add(4);

        System.out.println(list);

        // void shuffle(List) //对List容器内的元素进行随机排列
        Collections.shuffle(list);
        System.out.println(list);

        //void reverse(List) //对List容器内的元素进行逆续排列
        Collections.reverse(list);
        System.out.println(list);

        //void sort(List) //对List容器内的元素排序,排序的规则是按照升序进行排序。
        Collections.sort(list);
        System.out.println(list);

        //list集合存储javabean类型数据 : 1)内部比较器  2)static  void sort(List list, Comparator c) 根据指定比较器引发的顺序对指定列表进行排序。
        
        System.out.println("内部比较器");
        System.out.println(list);
        list.forEach(System.out::println);

        System.out.println("collections方法");
        Collections.sort(list, new Comparator() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });
        System.out.println(list);
        System.out.println("-----------------------");

        //void fill(List, Object) //用一个特定的对象重写整个List容器
        //Collections.fill(list,100);
        System.out.println(list);
        //int binarySearch(List, Object)//对于顺序的List容器，采用折半查找的方法查找特定对象
        System.out.println( Collections.binarySearch(list,5));;
    }
}

Set与Map

Java相关栏目本月热门文章