当前位置： 首页 > article >正文

Map和Set(下)

article 2025/3/4 17:19:00

        我们先对上一小节部分进行一些复习和补充

        1. 补充和强调

                补充

                1. HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 Set

                2. java 中使用的是哈希桶方式解决冲突的

                3. java 会在冲突链表长度大于一定阈值后，将链表转变为搜索树（红黑树）条件:链表长度>=8,数组长度>=64

                4. java 中计算哈希值实际上是调用的类的 hashCode 方法，进行 key 的相等性比较是调用 key 的 equals 方法。所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值，必须覆写 hashCode 和 equals 方法，而且要做到 equals 相等的对象，hashCode 一定是一致的。

                强调

                1. Map没有实现Iterable接口,因此不支持迭代器遍历,如果想进行迭代器遍历,我们就必须转化为Set才可以.

                2. TreeMap的下标是要进行比较的,因此这个对象是要可比较的

                

                3. Set里面不能存储相同的Key值 天然可以去重 HashSet底层是一个HashMap,TreeSet底层是一个TreeMap,每次Set存储对象的时候,默认的val是一个Object对象.     

       代码实现

class Student {

}
public static void main(String[] args) {
        HashMap<String,Integer> map = new HashMap<>();
        //放入键值对元素
        map.put("hello",2);
        map.put("xiaobai",3);
        map.put("yes",6);
        //根据key获取val
        Integer val = map.get("hello");
        System.out.println(val);
        System.out.println(map);
        //通过for-each来打印每个元素
        for (Map.Entry<String,Integer> entry:map.entrySet()) {
            System.out.println("key: " + entry.getKey() + "val: " + entry.getValue());
        }
        //TODO 没有实现Iterlable,因此不支持迭代器遍历,要转化为Set才可以

        HashMap<Student,Integer> map1 = new HashMap<>();
        map1.put(new Student(),2);
        map1.put(new Student(),2);
        map1.put(null,23);//可以放null
        //TODO TreeMap的下标是要进行比较的,因此这个对象是要可比较的
        TreeMap<Student,Integer> treeMap = new TreeMap<>();
//        treeMap(new Student(),2);
//        treeMap(new Student(),3);
        //TODO Set里面不能存储相同的key 天然可以去重 HashSet底层是一个HashMap,TreeSet底层是一个TreeMap;每次Set存储元素的时候,默认的val是一个Object对象
        HashSet<String> set = new HashSet<>();
        set.add("hello");
        set.add("hello");
        set.add("hello");
        set.add("xioabai");
        System.out.println(set);
        TreeSet<String> set1 = new TreeSet<>();
        set1.add("hello");
        set1.add("hello");
        set1.add("hello");
        set1.add("小白");
        System.out.println(set1);
        //TODO 如果是int类型我们可以通过整形的数/数组长度来获取哈希地址,那么如果是字符串型?自定义类型,该如何呢?
        //把对象转化为整数hashcode
    }

         

//TODO 2. 2的Student
//一般自定义类型要重写equals,hashcode
class Student {
    public String id;

    public Student(String id) {
        this.id = id;
    }
//根据id来比较
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return Objects.equals(id, student.id);
    }
//根据id来生成hashcode
    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}

 public static void main2(String[] args) {
        //TODO 如果是int类型我们可以通过整形的数/数组长度来获取哈希地址,那么如果是字符串型?自定义类型,该如何呢?
        //把对象转化为整数hashcode
        Student student1 = new Student("1233");
        Student student2 = new Student("1233");
        //得到俩个对象的hashCode
        System.out.println(student1.hashCode());//明明是一样的id,但是因为我们使用的是Object使用的默认的hashCode,需要重写
        System.out.println(student2.hashCode());//x%len,重写了hashCode后就一样了
        HashMap<Student,Integer> map = new HashMap<>();
        //用s1放进去
        map.put(student1,2);
       //用s2取出来
        System.out.println(map.get(student2));//如果不重写就找不到,为null
    }

2. 自定义类实现哈希桶                    

        在上一节,我们实现了int类型的哈希桶,如果是int类型我们可以通过整形的数/数组长度来获取哈希地址,那么如果是自定义类型该如何呢?我们int类型就直接%数组长度即可,但是如果是自定义类型,我们就要使用key的hashcode值来%数组长度.这个就是总体思路

        2.1 变量介绍

                我们既然要来计算自定义类型的hashcode,那么我们就要使用泛型,(K,V就是泛型),我们可以把自定义类型,或者包装类放在里面当作参数,我们创建了一个内部类(作为哈希桶的链表节点),里面任然也是泛型类型的.

        

                仿照之前int类型的哈希桶,我们也要创建数组,有效值大小,负载因子,并且提供一个可以创建大小为10的数组的构造方法.

     

        2.2 放入元素put()

                        我们放入元素,首先先计算这个泛型对象的K的哈希值,然后让这个哈希值和数组长度进行取余计算,计算出我们应该方在的数组的位置,我们遍历整个位置上的链表,比较放入的元素和链表节点的val值是否一致(注意,此时我们是泛型,我们就不能用==来比较val,因此我们要使用equals来比较val值),一致我们只更新val值即可.不一致,我们就把元素通过头插法放入链表中.我们是通过key的hash值来确定所放的数组的位置的.(现在的java是尾插)

                

        2.3 获取元素getValue()

                        我们获取元素的值,首先我们同样需要知道key值的hashcode值,然后通过%操作获得链表所在的数组的位置,然后我们遍历链表去寻找和当前key值一样的节点.

                      

                注意的点:

                总体代码:

哈希桶

package Map_Set.HashConfict;
//自己是实现一个泛型类型的hashMap
public class HashBuck2<K,V> {//直接定义泛型
    //创建内部类
    static class Node<K,V> {
        public K key;
        public V val;
        //键值对类型
        public Node<K,V> next;
        public Node(K key,V val) {
            this.key = key;
            this.val = val;
        }
    }
    public Node<K,V>[] array;
    public int usedSize;
    public static final float DEFAULT_LOAD_FACTOR = 0.75f;
    public HashBuck2(){
        array = (Node<K, V>[]) new Node[10];
    }
    //放入元素
    public void put(K key,V val) {
        //通过key来获取hashcode
        int hash = key.hashCode();
        int index = hash % array.length;
        Node<K,V> cur = array[index];
        while (cur != null) {
            if(cur.val.equals(val)) {//引用类型不能使用等号!
                //更新val值
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        Node<K,V> node = new Node<>(key,val);
        node.next = array[index];
        array[index] = node;
        usedSize++;
    }
    //获取元素值
    public V getValue(K key) {
        int hash = key.hashCode();
        int index = hash % array.length;
        //找到数组里面所指的链表的第一个元素
        Node<K,V> cur = array[index];
        while (cur != null) {
//            if(cur.key == key) {//引用类型不能使用等号!
            if(cur.key.equals(key)) {//引用类型不能使用等号!

                //更新val值
               return cur.val;
            }
            cur = cur.next;
        }
        return null;//没找到

    }
}

测试类

package Map_Set.HashConfict;


import java.util.Objects;

class Student1 {
    public String id;

    public Student1(String id) {
        this.id = id;
    }
    //根据id来比较
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student1 student = (Student1) o;
        return Objects.equals(id, student.id);
    }
    //根据id来生成hashcode
    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}
public class Test {
    public static void main(String[] args) {
        HashBuck2<Student1,Integer> hashBuck2 = new HashBuck2<>();
        Student1 student1 = new Student1("123");
        Student1 student2 = new Student1("123");
        hashBuck2.put(student1,2);
        System.out.println(hashBuck2.getValue(student2));
    }
}

3. 哈希桶的底层源码

4. 几个OJ题目

        4.1 只出现一次的元素

                题目: 136. 只出现一次的数字 - 力扣（LeetCode）

                解析:

                1. 遍历数组把元素放进set里面

                2. 判断每个数组元素是否在set里面,在就去除

                3. 遍历数组求出只出现一次的元素

                完整代码:

    public int singleNumber(int[] nums) {
        //TreeSet更慢
        //我们使用Set来解决,set天生可以去重
        HashSet<Integer> set = new HashSet<>();
        //把元素放进set
        for (int x : nums) {
            //如果不包含x,就放到set里面
            if(!set.contains(x)){
                set.add(x);
            }else {
                //如果包含就删除
                set.remove(x);
            }
        }
        //此时set只剩下只出现一次的元素了
        for (int x : nums) {
            if (set.contains(x)) {
                return x;
            }
        }
        //走到这里,说明没有
        return -1;
    }

        4.2 宝石和石头

                题目:771. 宝石与石头 - 力扣（LeetCode）

                解析:

        1. 把宝石放进set

         2. 遍历stones数组,判断数组元素是不是宝石

这里注意: 字符串名字.toCharArray()这个就是把字符串转化为字符数组,这样我们就不必把字符串的每个元素charAt出来了.

                完整代码:


        //创建计数器和set
        int count = 0;
        HashSet<Character> set = new HashSet<>();
        //把jewels的元素放到set
        for (char x : jewels.toCharArray()) {//字符串转化为字符数组
            set.add(x);
        }
        //遍历stones,判断数组元素是不是宝石
        for (char x : stones.toCharArray()) {
            if(set.contains(x)) {
                count++;
            }
        }
        return  count;

自己写的:

    //先创建一个set,把宝石放进去
        HashSet<Character> set = new HashSet<>();
        //计数器
        int count = 0;
        for (int i = 0; i < jewels.length();i++) {
            set.add(jewels.charAt(i));
        }
        //然后遍历stones,在stons里面找宝石
        for (char x : set) {
            for (int i = 0; i < stones.length();i++) {
                if(x == stones.charAt(i)){
                    count++;
                }
            }
        }
        return count;
    }

        4.3 坏键盘打字

                题目:旧键盘 (20)__牛客网

                解析:

注意: 我们要统一转换为大写

                完整代码:

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        //输入俩个字符串
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String str1 = in.nextLine();
            String str2 = in.nextLine();
            func(str1, str2);
        }
    }
    private static void func(String str1, String str2) {
             //把str2放进set
        HashSet<Character> set = new HashSet<>();
        for (char ch : str2.toUpperCase().toCharArray()) {
            set.add(ch);//先大写再转化为字符数组
        }
        HashSet<Character> set1 = new HashSet<>();
        for (char ch : str1.toUpperCase().toCharArray()) {
            if(!set.contains(ch) && !set1.contains(ch)) {
                //不包含就输出
                //但是会出现重复的坏件,解决方法: 放到另一个set里面
                System.out.print(ch);
                set1.add(ch);
            }
        }
    }
}

        4.4 复制带有随机指针的链表

                题目:138. 随机链表的复制 - 力扣（LeetCode）

                解析:

                        步骤:

                        1. 第一次遍历链表 产生节点 并且用map存储新老节点的对应关系

                        2. 第二次遍历链表,开始修改每个新节点的指向

                        3. 返回head对应的地址

注意:set不管是HashSet还是TreeSet都是有序的

                完整代码:

//TODO 复制带有随机指针的链表
    public Node copyRandomList(Node head) {
        //创建一个Map,key原先链表的的每个节点的地址,val是根据原先节点的val生成的新的节点地址
        HashMap<Node,Node> map = new HashMap<>();
        Node cur = head;
        //TODO 1.第一次遍历链表 存储对应关系
        while (cur != null) {
            //创建新的节点
            Node node = new Node(cur.val);
            //存放到map,形成老-新地址的键值对
            map.put(cur,node);
            cur = cur.next;
        }
        //TODO 2.第二次遍历链表 开始修改每个新节点的指向
            cur = head;
            while (cur != null) {
                //得到next
                map.get(cur).next = map.get(cur.next);
                //得到radom
                map.get(cur).random = map.get(cur.random);
                cur = cur.next;
            }
            //TODO 3.返回head对应的地址
            return map.get(head);
    }

        4.5 前K个高频单词

                做这个题前我们先写俩个小题目:

                1> 10W个数据如何去除重复的数据,且重复的数据只保留一份

                        我们直接用set,把所有数组都放进set即可

                        代码:

    public static void main(String[] args) {
        int[] array = {1,2,3,3,2};
        HashSet<Integer> set = new HashSet<>();
        for (int x : array) {
            set.add(x);
        }
        System.out.println(set);
    }

                2> 10W个数据统计每个数据出现的次数

                       我们使用Map,数据为Key,次数为value,每次遇到重复的单词就在val上+1

                        代码:

   public static void main(String[] args) {
        int[] array = {1,2,3,3,2};
        Map<Integer,Integer> map = new HashMap<>();
        for (Integer x : array) {
            if(map.get(x) == null) {
                //第一次存放
                map.put(x,1);
            }else {
                //>1次,直接修改val值即可
                int val = map.get(x);
                map.put(x,val+1);
            }
        }
        for (Map.Entry<Integer,Integer> entry : map.entrySet()){
            System.out.println("key: " +entry.getKey() + " Val: " +entry.getValue());
        }
    }

                 题目:692. 前K个高频单词 - 力扣（LeetCode）

                解析:

          根据上面俩个题目,我们就有思路了

                1> 统计每个单词出现的次数,存储到map里面去

                2> 遍历统计好的map,把每组数据存到小根堆去

                3> 通过Topk来获得前k个频率最大的单词数,如果频次一样,我们就要根据字典序进行排序(转换为大根堆)

                4> 把k个数从大到小进行排序,并且输出.

这里需要注意几个点

        1> 关于PriorityQueue里面为什么不直接放map,而是要放Map里面的内部类Entry.

        2> 关于频次一样,要根据字典序来进行排序的问题.

        3> 我们要获取前k个最大的数->构建小根堆.获取前k个最小的数->构建大根堆.

                完整代码:

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
         //TODO 1.统计每个单词出现的次数,存储到map
        Map<String,Integer> map = new HashMap<>();
        for (String word : words) {
            if(map.get(word) == null){
                //单词第一次出现
                map.put(word,1);
            }else {
                Integer val = map.get(word);
                map.put(word,val + 1);
            }
        }
        //TODO 2. 遍历统计好的Map,把每组数据存储到小根堆里面去
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override//建立小根堆
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue())== 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });//根据单词频率进行排序
        //TopK问题
        for (Map.Entry<String,Integer> entry : map.entrySet()) {
            if(minHeap.size() < k) {
                //k个元素没放满,就继续放
                minHeap.offer(entry);
            }else {
                //去k后面找最大频率的单词
                Map.Entry<String,Integer> top = minHeap.peek();
                //如果当前的值比我堆顶元素的值小,那么就把它放到堆顶,顶替原来的元素
                if(top.getValue().compareTo(entry.getValue()) < 0) {
                    minHeap.poll();
                    minHeap.offer(entry);
                }else {
                    //频率相同,按照单词字典序来进行排列,
                    if(top.getValue().compareTo(entry.getValue()) == 0) {
                        if(top.getKey().compareTo(entry.getKey()) > 0) {
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    }
                }
            }
        }
        List<String> ret = new ArrayList<>();
        //放到了小根堆 2 3 4,TODO 3.返回的答案按照单词出现的频率由高到低排序
        for (int i = 0 ; i < k ;i++) {
            Map.Entry<String,Integer> top = minHeap.poll();
            ret.add(top.getKey());
        }
        // 2 3 4 -> 4 3 2 进行数组的逆置
        Collections.reverse(ret);
        return ret;
    }
}

5. HashCode的应用--String进阶

        5.1 字符串常量池

           我们先得知道什么是池,池这个东西就是存着我们经常用的一种容器,是为了实现随去随用的,提高运行速度节省内存的容器.

           在java中,我们有很多的池

                1> class文件常量池: 每个.Java源文件编译后生成.Class文件中会保存当前类中的字面常量以及符号信息.

                2> 运行时常量池: 在.Class文件被加载时，.Class文件中的常量池被加载到内存中称为运行时常量池，运行时常量池每个类都有一份.

                3> 字符串常量池: 字符串常量池在JVM中是StringTable类，实际是一个固定大小的HashTable,java8里面,字符串常量池在堆里面.

        5.2 String对象的创建

                这里注意,只要是""引起来的都会放到字符串常量池中.

                重点:

                1. 创建字符串的俩种方法在虚拟机和堆上是怎么创建的

                2. intern方法把字符串手动放进字符串常量池

        

                        


http://www.kler.cn/a/427802.html

相关文章：

  • Swift 扩展
  • vm ubuntu黑屏
  • 【配置查询】.NET开源 ORM 框架 SqlSugar 系列
  • 光猫开DMZ教程
  • 为什么 JavaScript 中的箭头函数不生效？
  • 基于Springboot的校园交友网站设计与实现
  • c语言的思维导图
  • Web3与人工智能的跨界融合：数据隐私与去中心化的新机遇
  • 论文笔记：Asymptotic Midpoint Mixup for Margin Balancing and Moderate Broadening
  • SQL分类：DDL、DML、DCL
  • 如果MySQL中没有MVCC，会有什么影响？
  • rockit 学习、开发笔记(六)(VENC)
  • docker批量创建cloudstack虚拟主机脚本
  • 2022-12-4----Android11（H713m）---- WiFi驱动添加写入mac号补丁
  • LabVIEW热阻炉温度控制
  • OpenResty Nginx：详细对比与部署指南
  • 【jvm】讲讲jvm中的gc
  • SQL SERVER 2016 AlwaysOn 无域集群+负载均衡搭建与简测
  • redis安装与使用
  • LeetCode题练习与总结：根据字符出现频率排序--451