【数据结构】map&set详解

简介: 本文详细介绍了Java集合框架中的Set系列和Map系列集合。Set系列包括HashSet(哈希表实现,无序且元素唯一)、LinkedHashSet(保持插入顺序的HashSet)、TreeSet(红黑树实现,自动排序)。Map系列为双列集合,键值一一对应,键不可重复,值可重复。文章还介绍了HashMap、LinkedHashMap、TreeMap的具体实现与应用场景,并提供了面试题示例,如随机链表复制、宝石与石头、前K个高频单词等问题的解决方案。

🍁1. Set系列集合

Set接口是一种不包含重复元素的集合。它继承自Collection接口,所以可以使用Collection所拥有的方法,Set接口的实现类主要有HashSetLinkedHashSetTreeSet等,它们各自以不同的方式存储元素,但都遵循Set接口的规定。


  • 当你需要确保集合中的元素唯一时。


  • 当你不需要保持元素的插入顺序时(除非使用LinkedHashSet)。


  • 当你需要元素自然排序或根据自定义排序规则排序时(使用TreeSet)。

🍁1.1 HashSet

当用HashSet实例化对象时,由于底层结构是哈希表,所以元素是无序的,而TreeSet底层是红黑树,是有序的

由于Set系列集合里面不能有重复的元素,在之前我们也了解到,add方法的返回值是boolean类型的,当遇到重复元素,第二次添加就会添加失败

并且Set集合没有索引的概念,不能通过下标的方式进行遍历打印

和之前一样,没有索引的集合可以通过迭代器,增强for,lambda表达式进行遍历

Iterator<String> it = s1.iterator();
        while (it.hasNext()){
            System.out.print(it.next() + " ");
        }
        System.out.println();
        for(String s : s1){
            System.out.print(s + " ");
        }
        System.out.println();
        
        s1.forEach(new Consumer<String>() {
            @Override
            public void accept(String s) {
                System.out.print(s + " ");
            }
        });

🍁1.2 LinkedHashSet

LinkedHashSet底层也是哈希表,但是存取元素的顺序是一致的,因为使用了双向链表记录添加顺序

🍁1.3 TreeSet

TreeSet是基于红黑树实现的,TreeSet中的元素处于排序状态,因此查找、添加、删除和遍历等操作都能以对数时间复杂度进行。但是,TreeSet中添加的元素必须实现Comparable接口,或者在创建TreeSet时提供一个Comparator对象,以确保元素可以被正确地排序。

排序规则:Integer,Double等数值类型默认按照从小到大的顺序排序,对于字符,字符串类型,按照ASCII码表中的数字进行升排序

接下来演示一下,创建自定义类型的TreeSet

例如:给出一个Student类,要求按照学生的年龄排序

首先创建好Student类之后,需要实现Comparable接口,然后重写compareTo和toString方法

public class Student implements Comparable<Student>{
    public String name;
    public int age;
    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }
    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
    @Override
    public int compareTo(Student o) {
        return this.age - o.age;//this.age表示要添加的元素
    }
}

this.age表示要添加的元素,所以如果返回值是负数,表示要添加的元素是小的,存左边,如果是0,表示元素已经存在,直接舍弃

public class Text2 {
    public static void main(String[] args) {
        Student s1 = new Student("zhang",18);
        Student s2 = new Student("wang",20);
        Student s3 = new Student("li",19);
        TreeSet<Student> treeSet = new TreeSet<>();
        treeSet.add(s1);
        treeSet.add(s2);
        treeSet.add(s3);
        System.out.println(treeSet);
    }
}

最终,虽然插入时没有按顺序,由于TreeSet底层是红黑树,所以最终也实现了排序的效果

比较器排序

问题:根据字符串长度比较,长度相同再按字典序比较

//o1:当前要添加的元素
        //o2:红黑树中已经存在的元素
        TreeSet<String> ts = new TreeSet<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o1.length() - o2.length()) == 0 ? o1.compareTo(o2) : o1.length() - o2.length();
            }
        });
        ts.add("bbcd");
        ts.add("abcde");
        ts.add("abcd");
        System.out.println(ts);

也就是在创建对象的时候传入比较器进行比较

🍁2. 单列集合的使用场景分析

介绍完Set系列集合之后,我们的单列集合就都学习完了,接下来分析一下这写集合的使用场景

如果集合中元素可重复:使用ArrayList(基于数组)

如果集合中元素可重复并且用到增删操作多余查询:使用LinkedList

如果需要对集合去重:使用HashSet

如果需要在去重的前提下还要保证存取顺序:使用LinkedHashSet

如果需要对集合中的元素进行排序:使用TreeSet

🍁3. Map系列集合

Map系列的集合称为双列集合

1. 双列集合一次存储一对数据,分别为键和值

2. 键不能重复,值可以重复

3. 键和值是一一对应的,每一个键都对应一个值

4. 键+值整体称为键值对,也叫Entry对象

和Set集合类似,Map是顶层接口,底下有这些实现类

以下就是Map集合常用的API

🍁3.1 HashMap

HashMap的底层也是哈希表,和之前的HashSet不同,HashMap中,当插入的key相同时,第二次插入会覆盖原来的value值,同时,如果存储的是自定义类型的对象还需要重写HashCode和equals方法

编辑其他方法就不演示了,下面来介绍一下map的遍历

Map的遍历

键找值:调用keySet方法,获取所有的key,把返回值放在Set集合中,再遍历Set集合,通过get方法获取每一个key的value

//获取所有的键,并放在Set集合中
        Set<String> set = map.keySet();
        //遍历set,根据所有的键获取值
        for(String key:set){
            int value = map.get(key);
            System.out.println(key + " = " + value);
        }

通过键值对对象进行遍历

调用entrySet方法,把所有键值对对象放在Set集合中,再遍历Set集合

可以看出,Entry是Map接口的一个内部接口,所以需要通过Map.Entry的形式调用,也可以直接导入

import java.util.Map.Entry;

就可以省略Map.

遍历时,可以直接打印Entry对象,也可以通过get的方式获取key和value        

Set<Map.Entry<String, Integer>> entries = map.entrySet();
        for(Map.Entry<String,Integer> entry : entries){
            //System.out.println(entry);
            String s = entry.getKey();
            Integer i = entry.getValue();
            System.out.println(s + " = " + i);
        }

最后还可以通过lambda的形式遍历

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

🍁3.2 LinkedHashMap

和LinkedHashSet一样,LinkedHashMap存储的键是有序的(存储顺序和取出顺序一样)


🍁
3.3 TreeMap

TreeMap和TreeSet底层一样,都是红黑树,根据键进行排序,排序规则也是类似的,对于非数值等类型,可以实现Comparable接口,指定比较规则,也可以传入比较器

🍁4. 面试OJ题练习

🍁4.1 随机链表的复制

138. 随机链表的复制

也就是下面这种情况

如果说直接对链表节点进行复制是不可以的,因为题目中要求的是深拷贝,所以说拷贝后的 节点可能和原来的地址不一样

思路:遍历原来的链表,每遍历一次都创建一个新的节点,把原来的节点和拷贝的新节点的映射关系使用map存储起来,再通过get方法得到节点,再连接next和random

public Node copyRandomList(Node head) {
        Map<Node, Node> map = new LinkedHashMap<>();
        Node cur = head;
        while (cur != null) {
            Node copy = new Node(cur.val);
            map.put(cur, copy);
            cur = cur.next;
        }
        /*cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }*/
        Set<Node> keySet = map.keySet();
        for (Node curNode : keySet) {
            map.get(curNode).next = map.get(curNode.next);
            map.get(curNode).random = map.get(curNode.random);
        }
        return map.get(head);
    }

🍁4.2 宝石与石头

771. 宝石与石头

这一题就可以很好的利用Set集合元素不能重复的特性了,如果不用Set集合,把全部元素异或一遍就可以找到了,而且速度更快,这里只是为了练习一下Set集合的使用,只需要把jewels存一个set,再遍历stones,判断是否有set集合里的元素即可

public class Text {
    public static void main(String[] args) {
        String jewels = "aA";
        String stones = "aAABBBBB";
        System.out.println(numJewelsInStones(jewels, stones));
    }
    public static int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < jewels.length(); i++) {
            set.add(jewels.charAt(i));
        }
        int cnt = 0;
        for (int i = 0; i < stones.length(); i++) {
            if (set.contains(stones.charAt(i))) {
                cnt++;
            }
        }
        return cnt;
    }
}

🍁4.3 前k个高频单词

692. 前K个高频单词

思路:前k个高频词,就是经典的topk问题,根据之前我们学到的,就是用小根堆解决,首先统计一下每个单词出现的频率,并通过map存储它们的映射关系,接着创建小根堆,套用之前的模板解决

public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        //统计单词个数并存入map
        for (String s : words) {
            if (map.get(s) == null) {
                map.put(s, 1);
            } else {
                int val = map.get(s);
                map.put(s, ++val);
            }
        }
        //创建根据map的value创建小根堆
        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) {
                //相同时根据key创建大根堆,最后反转的时候就可以把字典序靠前的排到前面了
                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()) {
            //先把前K个元素加入大根堆
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            } else {
                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) {
                    //堆顶元素等于后面时,堆顶的key字典序大于后面的
                    if (top.getKey().compareTo(entry.getKey()) > 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        ArrayList<String> ans = new ArrayList<>();
        //把key存入ArrayList
        for (int i = 0; i < k; i++) {
            ans.add(minHeap.poll().getKey());
        }
        //题目要求出现频率由高到低,进行翻转
        Collections.reverse(ans);
        return ans;
    }
相关文章
|
13天前
|
存储 Java
告别混乱!用Java Map优雅管理你的数据结构
【10月更文挑战第17天】在软件开发中,随着项目复杂度增加,数据结构的组织和管理至关重要。Java中的Map接口提供了一种优雅的解决方案,帮助我们高效、清晰地管理数据。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,有效提升了代码质量和维护性。
53 2
|
13天前
|
存储 Java 开发者
Java Map实战:用HashMap和TreeMap轻松解决复杂数据结构问题!
【10月更文挑战第17天】本文深入探讨了Java中HashMap和TreeMap两种Map类型的特性和应用场景。HashMap基于哈希表实现,支持高效的数据操作且允许键值为null;TreeMap基于红黑树实现,支持自然排序或自定义排序,确保元素有序。文章通过具体示例展示了两者的实战应用,帮助开发者根据实际需求选择合适的数据结构,提高开发效率。
42 2
|
11天前
|
存储 Java 开发者
Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效
【10月更文挑战第19天】在软件开发中,随着项目复杂度的增加,数据结构的组织和管理变得至关重要。Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,帮助开发者告别混乱,提升代码质量。
20 1
|
23天前
|
存储 JavaScript 前端开发
Set、Map、WeakSet 和 WeakMap 的区别
在 JavaScript 中,Set 和 Map 用于存储唯一值和键值对,支持多种操作方法,如添加、删除和检查元素。WeakSet 和 WeakMap 则存储弱引用的对象,有助于防止内存泄漏,适合特定场景使用。
|
26天前
|
存储 缓存 Java
【用Java学习数据结构系列】HashMap与TreeMap的区别,以及Map与Set的关系
【用Java学习数据结构系列】HashMap与TreeMap的区别,以及Map与Set的关系
31 1
|
29天前
|
存储 安全
【数据结构】Set的使用与注意事项
【数据结构】Set的使用与注意事项
19 2
|
29天前
|
存储 自然语言处理 安全
【数据结构】Map的使用与注意事项
【数据结构】Map的使用与注意事项
24 1
|
2月前
|
算法
你对Collection中Set、List、Map理解?
你对Collection中Set、List、Map理解?
32 5
|
2月前
|
存储 JavaScript 前端开发
js的map和set |21
js的map和set |21
|
2月前
|
存储 JSON NoSQL
redis基本数据结构(String,Hash,Set,List,SortedSet)【学习笔记】
这篇文章是关于Redis基本数据结构的学习笔记,包括了String、Hash、Set、List和SortedSet的介绍和常用命令。文章解释了每种数据结构的特点和使用场景,并通过命令示例演示了如何在Redis中操作这些数据结构。此外,还提供了一些练习示例,帮助读者更好地理解和应用这些数据结构。
redis基本数据结构(String,Hash,Set,List,SortedSet)【学习笔记】