HashSet 集合类

HashSet介绍

HashSet集合底层采取哈希表存储数据

哈希表是一种对于增删改查数据性能都较好的结构

HashSet的基本使用

结论：集合中存储的对象，需要同时重写hashCode和equals方法，才能够去重

hashCode方法和equals方法的配合流程

hashCode方法和equals方法的配合流程总结

当添加对象的时候，会先调用对象的hashCode方法，计算出一个应该存入的索引位置，查看该位置上是否存在元素

不存在：直接存

存在：调用equals方法比较内容

false：存

true: 不存

hashCode方法介绍

哈希值

• 是JDK根据某种规则算出来的int类型的整数

Object类的API

@IntrinsicCandidate

public native int hashCode( );

• public int hashCode( )：调用底层C++代码计算出的一个随机数（常被人称作地址值）

hashCode方法改造

1. 重写hashCode方法
2. 根据对象的属性值计算出的哈希值

HashSet1.7 版本原理解析：数组+链表

1. 创建一个默认长度16的数组，数组名table
2. 根据元素的哈希值跟数组的长度求余计算出应存入的位置
3. 判断当前位置是否为null,如果是null直接存入
4. 如果位置不为null,表示有元素，则调用equals方法比较
5. 如果一样，则不存，如果不一样，则存入数组

JDK7新元素占老元素位置，指向老元素（头插法

JDK8中新元素挂在老元素下面（尾插法）

HashSet的添加过程(JDK8版本以后)

底层结构：哈希表（数组、链表、红黑树的结合体）

1. 创建HashSet集合，内部会存在一个长度为16个大小的数组
2. 调用集合的添加方法，会拿着对象的hashCode方法计算出应存入的束引位置（哈希值 % 数组长度）
3. 判断束引位置元素是否是null

是：存入

不是：说明有元素，调用equals方法比较内容

问题：描述一下HashSet集合数据的添加过程

回答：当我们添加元素的时候，添加方法内部会自动调用对象的hashCode方法，计算出应存入的索引位置

计算方式：

调用hashCode方法得到原始哈希值

对原始哈希值进行哈希扰动，扰动的方式是向右移动16位

使用扰动后的哈希，和原始哈希进行操作，这是二次哈希操作

然后使用运算后的哈希值，和数组的长度进行取余操作，计算应存入索引位置

• 但是源码中，计算方式（数组长度-1）& 哈希值;
• 这样做的原因是&操作，比%操作的效率更高

当计算出索引位置之后，会判断对应索引上是否是null

是null：说明没有元素，直接存

不是null：说明有元素，调用equals方法比较内容

内容相同：不存

内容不同：存

问题：如果某一个索引上的链表，结点个数超过了阈值，会怎么办？

回答：

-判断数组长度是否<64

是：扩容数组

-数组长度>=64

将这一条链表，转换为红黑树

问题：还有什么情况，会扩容数组？

回答：

当数组中元素的个数，也就是size( )，到达了（数组长度 * 加载因子）的时候，就会扩容数组，大小是原来的两倍

• 初始数组长度为：16
• 默认加载因子：0.75
• 第一次的扩容：12的时候

LinkedHashSet 集合类

LinkedHashSet集合概述和特点

有序、不重复、无索引

这里的有序指的是保证存储和取出的元素顺序一致

原理：底层数据结构是依然哈希表，只是每个元素又额外的多了一个双链表的机制记录存储的顺序

集合使用场景总结

1. 如果想要集合中的元素可重复

用ArrayList集合，基于数组的（用的最多）

2. 如果想要集合中的元素可重复，而且当前的增删操作明显多于查询

用LinkedList集合，基于链表的。

3. 如果想对集合中的元素去重

用HashSet集合，基于哈希表的（用的最多）

4. 如果想对集合中的元素去重，而且保证存取顺序

用LinkedHashSet集合，基于哈希表和双链表，效率低于HashSet

5. 如果想对集合中的元素进行排序

用TreeSet集合，基于红黑树，后续也可以用List集合实现排序

可变参数

可变参数：本质来讲就是一个数组

使用细节：调用方法，参数是可变参数，实际参数可以给，也可以不给，还可以给多个

注意事项：如果自己设计的方法，带有可变参数，需要将可变参数放在最后

Collections 集合工具类

java.utils.Collections:是集合工具类

作用：Collections并不属于集合，是用来操作集合的工具类

Map 接口

Map集合是一种双列集合，每个元素包含两个数据

Map集合的每个元素的格式：key = value(键值对元素)

key(键)：不允许重复

value(值)：允许重复

键和值是一一对应的，每个键只能找到自己对应的值

key + value这个整体我们称之为 “键值对” 或者 “键值对对象”在Java中使用Entry对象表示

Map的常见API

Map是双列集合的顶层接口，它的功能是全部双列集合都可以继承使用的

Map集合的三种遍历方式

1. 通过键找值
2. 通过键值对对象获取键和值
3. 通过foreach方法遍历

Map集合的第一种遍历方式: 根据键找值

方法的铺垫:
    1. public V get(Object key) : 根据传入的键, 获取对应的值
    2. public Set<K> keySet() : 返回Map集合中所有的键
    
    步骤:
    1. 获取Map集合中所有的键 (Set集合)
    2. 遍历Set集合, 获取每一个键
    3. 根据键找值

代码演示

public static void main(String[] args) {
    HashMap<String, String> hm = new HashMap<>();

    hm.put("张三", "北京");
    hm.put("李四", "上海");
    hm.put("王五", "广州");

    // 1.获取集合上所有的键
    Set<String> KeySet = hm.keySet();

    // 2.遍历set集合，获取每一个键
    Iterator<String> it = KeySet.iterator();
    while (it.hasNext()) {
        String key = it.next();
        // 3.根据键查找对应的值
        String value = hm.get(key);
        System.out.println(key + "---" + value);
    }

    System.out.println("------------------------");

    for (String key : hm.keySet()) {
        System.out.println(key + "---" + hm.get(key));
    }
}

Map集合的第一种遍历方式：通过键值对对象获取键和值

键值对对象 : Entry (内部接口)
Map.Entry

public Set<Map.Entry<K,V>> entrySet() : 获取Map集合中, 所有的键值对对象

1. 调用entrySet方法, 获取所有键值对对象
2. 遍历Set集合, 获取每一个键值对对象
3. 根据键值对对象, 获取键和值

代码演示

public static void main(String[] args) {

    HashMap<String, String> hm = new HashMap<>();

    hm.put("张三", "北京");
    hm.put("李四", "广州");
    hm.put("王五", "上海");

    // 1.调用Map集合的entrySet方法，获取到所有对象的键值对对象
    Set<Map.Entry<String, String>> entries = hm.entrySet();
    // 2.遍历set集合，获取每一个键值对对象
    for (Map.Entry<String, String> entry : entries) {
        // 3.根据键值对对象，获取键和值
        System.out.println(entry.getKey() + "---" + entry.getValue());
    }
}

优化代码

public static void main(String[] args) {

    HashMap<String, String> hm = new HashMap<>();

    hm.put("张三", "北京");
    hm.put("李四", "广州");
    hm.put("王五", "上海");

    // 1.调用Map集合的entrySet方法，获取到所有对象的键值对对象
    // 2.遍历set集合，获取每一个键值对对象
    for (Map.Entry<String, String> entry : hm.entrySet()) {
        // 3.根据键值对对象，获取键和值
        System.out.println(entry.getKey() + "---" + entry.getValue());
    }
}

Map集合的第三种遍历方式 : foreach方法

代码演示

public static void main(String[] args) {

    HashMap<String, String> hm = new HashMap<>();

    hm.put("张三", "北京");
    hm.put("李四", "广州");
    hm.put("王五", "上海");

    hm.forEach(new BiConsumer<String, String>() {
        @Override
        public void accept(String key, String value) {
            System.out.println(key + "---" + value);
        }
    });

    System.out.println("-----------------------");

    // 改成Lamda表达式
    hm.forEach((key, value) -> System.out.println(key + "---" + value));
}

Map集合练习题

练习题一：

代码演示

import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

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

        System.out.print("请输入需要统计的字符串: ");
        String msg = new Scanner(System.in).nextLine();

        // 1. 准备Map集合用于统计操作（key：字符）（value：次数）
        TreeMap<Character, Integer> tm = new TreeMap<>();
        // 2. 拆分字符串
        char[] charArray = msg.toCharArray();
        // 3. 获取每一个字符
        for (char c : charArray) {
            // 4. 判断当前字符在集合中是否存在
            if (!tm.containsKey(c)) {
                // 不包含：说明是第一次出现
                tm.put(c, 1);
            } else {
                // 包含：值的位置应该是获取原值 + 1存回去
                tm.put(c, tm.get(c) + 1);
            }
        }

        // 5. 按照题目的格式拼接
        StringBuffer sb = new StringBuffer();
        for (Map.Entry<Character, Integer> entry : tm.entrySet()) {
            sb.append(entry.getKey()).append("(").append(entry.getValue()).append(")");
        }

        System.out.println(sb);
    }
}

练习题二：

代码演示

import java.util.ArrayList;
import java.util.Collections;
import java.util.Map;
import java.util.TreeMap;

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

        ArrayList<String> list1 = new ArrayList<>();
        Collections.addAll(list1, "南京市", "扬州市", "苏州市", "无锡市", "常州市");

        ArrayList<String> list2 = new ArrayList<>();
        Collections.addAll(list2, "武汉市", "孝感市", "十堰市", "宜昌市", "鄂州市");

        ArrayList<String> list3 = new ArrayList<>();
        Collections.addAll(list3, "石家庄市", "唐山市", "邢台市", "保定市", "张家口市");

        TreeMap<String, ArrayList<String>> tm = new TreeMap<>();
        tm.put("江苏省", list1);
        tm.put("湖北省", list2);
        tm.put("河北省", list3);

        for (Map.Entry<String, ArrayList<String>> en : tm.entrySet()) {
            // 1. 获取键(省份)
            System.out.print(en.getKey() + " = ");
            // 2. 获取值(市)
            ArrayList<String> values = en.getValue();
            for (int i = 0; i < values.size() - 1; i++) {
                System.out.print(values.get(i) + ", ");
            }
            System.out.println(values.get(values.size() - 1));
        }
    }
}