【Java数据结构】Map&Set的理解与应用(附面试题加深理解)

简介: 搜索、Map的使用、Set的说明、面试题练习

搜索

概念及场景

Map和set是一种专门用来进行搜索的容器或者数据结构,其搜索的效率与其具体的实例化子类有关。


以前常见的搜索方式有:

直接遍历,时间复杂度为O(N),元素如果比较多效率会非常慢

二分查找,时间复杂度为O(log2 N) ,但搜索前必须要求序列是有序的

上述排序比较适合静态类型的查找,即一般不会对区间进行插入和删除操作了,而现实中的查找比如:

根据姓名查询考试成绩

通讯录,即根据姓名查询联系方式

不重复集合,即需要先搜索关键字是否已经在集合中

可能在查找时进行一些插入和删除的操作,即动态查找,那上述两种方式就不太适合了,本文介绍的Map和Set是一种适合动态查找的集合容器。


模型

一般把搜索的数据称为关键字(Key),和关键字对应的称为值(Value),将其称之为Key-value的键值对,所以模型会有两种:


纯 key 模型,比如:

有一个英文词典,快速查找一个单词是否在词典中

快速查找某个名字在不在通讯录中

Key-Value 模型,比如:

统计文件中每个单词出现的次数,统计结果是每个单词都有与其对应的次数:<单词,单词出现的次数>

梁山好汉的江湖绰号:每个好汉都有自己的江湖绰号

而Map中存储的就是key-value的键值对,Set中只存储了Key。

Map的使用

b1.png


关于Map的说明

Map是一个接口类,该类没有继承自Collection,该类中存储的是<K,V>结构的键值对,并且K一定是唯一的,不能重复。


Map 的常用方法说明

b2.png


注意:


Map是一个接口,不能直接实例化对象,如果要实例化对象只能实例化其实现类TreeMap或者HashMap

Map中存放键值对的Key是唯一的,value是可以重复的

在Map中插入键值对时,key可以为空,value可以为空

Map中的Key可以全部分离出来,存储到Set中来进行访问(因为Key不能重复)。

Map中的value可以全部分离出来,存储在Collection的任何一个子集合中(value可能有重复)。

Map中键值对的Key不能直接修改,value可以修改,如果要修改key,只能先将该key删除掉,然后再来进行重新插入。

TreeMap和HashMap的区别


b3.png


关于Map.Entry<K, V>的说明

Map.Entry<K, V> 是Map内部实现的用来存放<key, value>键值对映射关系的内部类,该内部类中主要提供了<key, value>的获取,value的设置以及Key的比较方式。

b4.png


注意:Map.Entry<K,V>并没有提供设置Key的方法


Set的说明

Set与Map主要的不同有两点:

  • Set是继承自Collection的接口类
  • Set中只存储了Key。


Set常见方法说明

image.png


注意:


1.Map是一个接口,不能直接实例化对象,如果要实例化对象只能实例化其实现类TreeMap或者HashMap

2.Map中存放键值对的Key是唯一的,value是可以重复的

3.在Map中插入键值对时,key可以为空,value可以为空

4.Map中的Key可以全部分离出来,存储到Set中来进行访问(因为Key不能重复)。

5.Map中的value可以全部分离出来,存储在Collection的任何一个子集合中(value可能有重复)。

6.Map中键值对的Key不能直接修改,value可以修改,如果要修改key,只能先将该key删除掉,然后再来进行重新插入。

7.TreeMap和HashMap的区别

b6.png

关于Map.Entry<K, V>的说明

Map.Entry<K, V> 是Map内部实现的用来存放<key, value>键值对映射关系的内部类,该内部类中主要提供了<key, value>的获取,value的设置以及Key的比较方式。


image.png


注意:Map.Entry<K,V>并没有提供设置Key的方法


Set的说明

Set与Map主要的不同有两点:

  • Set是继承自Collection的接口类
  • Set中只存储了Key。


Set常见方法说明

image.png


注意:


1.Set是继承自Collection的一个接口类

2.Set中只存储了key,并且要求key一定要唯一

3.Set的底层是使用Map来实现的,其使用key与Object的一个默认对象作为键值对插入到Map中的

4.Set最大的功能就是对集合中的元素进行去重

5.实现Set接口的常用类有TreeSet和HashSet,还有一个LinkedHashSet,LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。

6.Set中的Key不能修改,如果要修改,先将原来的删除掉,然后再重新插入

7.TreeSet和HashSet的区别

b7.png


面试题练习

只出现一次的数字

b8.png


思路:

我们知道Set的特点就是key不会重复,所以这题第一时间想到的就是用HashSet,每读取一个数据,就将其存入我们的set里,如果set已经有这个数据了,说明这是第二次出现了,就把原来存在set里的这个数据给删除掉,遍历完全部数据后,还存在于set里的就是只出现一次的数据了


代码:

class Solution {

   public int singleNumber(int[] nums) {

       HashSet<Integer> set = new HashSet<Integer>();


       for(int i = 0 ; i < nums.length ; i++){

           if(set.contains(nums[i])){

               set.remove(nums[i]);

           }else{

               set.add(nums[i]);

           }

       }


       for(int key:set){

           return key;

       }

       return -1;

   }

}


复制带随机指针的链表

b9.png


思路:

题目要求进行深拷贝,所以就是说,我们要返回一个新的链表,新链表和原链表里的东西是一模一样的,但是互不相干,由于存在一 一对应的关系,首先想到的就是用Map,原链表的节点就是key–value里的key,而新链表的节点就是value,两者形成了一 一对应的关系,然后再利用map将原节点对应的next和random依次复制给新节点,具体看代码注释


代码:

/*

// Definition for a Node.

class Node {

   int val;

   Node next;

   Node random;


   public Node(int val) {

       this.val = val;

       this.next = null;

       this.random = null;

   }

}

*/


class Solution {

   public Node copyRandomList(Node head) {

           if(head==null) return null;

           Node cur = head;//创建一个cur节点遍历原链表

           HashMap<Node,Node> map = new HashMap<>();//建一个HashMap

           while(cur!=null){//依次遍历原链表

               Node copyNode = new Node(cur.val);//创建新节点,值和原链表中节点值一样

               map.put(cur,copyNode);//将原链表的节点和新创建的值一样的节点放入Map中

               cur = cur.next;

           }

           //已经将复制好的新节点和原节点按对应方式存入了map中

           //最后需要利用map处理新节点的next和random

           cur = head;

           while(cur!=null){

               //关键代码如下

               map.get(cur).next = map.get(cur.next);

               map.get(cur).random = map.get(cur.random);

               cur = cur.next;

           }

           return map.get(head);

     

   }

}


宝石与石头

b10.png


思路:

遍历字符串 jewels,使用HashSet存储其中的字符,然后遍历字符串 stones,对于其中的每个字符,如果其在哈希集合(HashSet)中,则是宝石。

代码:

class Solution {

   public int numJewelsInStones(String jewels, String stones) {

       HashSet<Character> set = new HashSet<>();

       for(int i = 0; i < jewels.length() ; i++){

           set.add(jewels.charAt(i));

       }


       int count = 0;

       for(int i = 0; i < stones.length() ; i++){

           if(set.contains(stones.charAt(i)))

           count++;

       }

       return count;

   }

}


坏键盘打字

b11.png


思路:


将实际输入的字符存入一个Set里,Set里的值不会重复,也就是说这个Set(setActul)里代表的就是好的键

遍历期望输入的字符串,如果setActual里边没有期望字符串里的字符,说明这个键是坏的,因为题目要求只输出一次坏的键,所以还需要用一个setBroken来记录坏的键,这样就不会重复输出坏的键了

代码:

import java.util.*;

public class 坏键盘 {

   public static void main(String[] args) {

       Scanner scan = new Scanner(System.in);

       String str1 = scan.nextLine();//期望的

       String str2 = scan.nextLine();//实际的


       HashSet<Character> setActual = new HashSet<>();

       for(char ch : str2.toUpperCase().toCharArray()) {

           setActual.add(ch);//把实际的字符串放到一个set里

       }


       HashSet<Character> setBroken = new HashSet<>();

       //再把坏了的键放到一个set里

       for(char ch : str1.toUpperCase().toCharArray()) {//遍历期望的字符串

           if(!setActual.contains(ch) && !setBroken.contains(ch)) {//在对比已经存在setActul里实际输入的字符串

               setBroken.add(ch);

               //这个ch就是坏了的

               //setBroken里只存一次这个坏了的键,存的时候同时打印一次

               System.out.print(ch);

           }

       }

   }

}



10w个数据去除重复数据

思路:

  • 原理就是利用Set的性质,set里的值不会重复,只要去重就想到用Set
  • 遍历生成的10w个随机数,这里假设随机数是1~100之间的,每遍历一个数据就判断一下set里是否已经存有,若没有则存入set,若有则进行下一个数据的检查

代码:

import java.util.ArrayList;

import java.util.HashSet;

import java.util.Random;


public class 去除10w个数据中的重复数据 {

   public static void main(String[] args) {

       Random random = new Random();

       ArrayList<Integer> list = new ArrayList<Integer>();//将随机生成的10w个数据存到顺序表中

       for (int i = 0; i < 100000; i++) {

           list.add(random.nextInt(100));//生成0~100之间的随机数

       }


       HashSet<Integer> set = new HashSet();//创建一个HashSet容器,存放数据

       //由于Set的性质,里面的元素不会重复,将顺序表里的数据存进这个容器就可以达到去除重复数据的目的了

       for (int i = 0 ; i< list.size(); i++){

           set.add(list.get(i));

       }

       System.out.println("不重复的数据有:"+set.size()+"个");

       System.out.println(set);

   }

}



运行结果:

b12.png


在10w个数据中找到第一个重复的数据

思路:

  • 和去重方法一样,用set,每遍历一个数据就检查set里是否已经存在这个数据,若不存在,则存入set,若已经存在,则说明已经找到第一次出现重复的数据了

代码:import java.util.ArrayList;

import java.util.HashSet;

import java.util.Random;


public class 在10w个数据中找到第一个重复的数据 {

   public static void main(String[] args) {

       Random random = new Random();

       ArrayList<Integer> list = new ArrayList<Integer>();//将随机生成的10w个数据存到顺序表中

       for (int i = 0; i < 100000; i++) {

           list.add(random.nextInt(100));//生成0~100之间的随机数

       }


       HashSet<Integer> set = new HashSet<Integer>();//还是用set


       for (int i = 0; i < list.size(); i++) {

           if (set.contains(list.get(i))) {//如果set里已经有此数据

               System.out.println(list.get(i));//输出,这就是第一个重复的数据

               break;//找到第一个从重复数据就可以退出了

           }else {

               set.add(list.get(i));//否则把新数据加入到set里

           }

       }

   }

}


运行结果:

b13.png


统计10w个数据重复出现的次数

思路:


统计重复次数的题,首先想到就是map,利用map的性质,键值对,一 一对应的关系

遍历数据,若map里没有这个数据,则加入到map里,并给 key–value里 的value初始化为1,代表出现了1次

后续再次遍历到这个数据的时候,value值+1,表示重复次数+1

代码:

import java.util.ArrayList;

import java.util.HashMap;

import java.util.Map;

import java.util.Random;


public class 统计10w个数据重复出现的次数 {

   public static void main(String[] args) {

       Random random = new Random();

       ArrayList<Integer> list = new ArrayList<Integer>();//将随机生成的10w个数据存到顺序表中

       for (int i = 0; i < 10; i++) {

           list.add(random.nextInt(10));//生成0~100之间的随机数

       }


       //        数据    出现次数

       HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

       for (Integer key : list) {//循环遍历list

           if (map.get(key)==null){//如果map里找不到key(数据)对应的值(次数)

               map.put(key, 1);

           }else{//说明之前存过一次了

               int count = map.get(key);//count记录原来出现的次数

               map.put(key, count+1);//更新key出现的次数

           }

       }


       //输出每个数据的重复次数

       System.out.println(map.entrySet());//entrySet()返回的是一个set,里面存放的是键值对(key和value的映射关系)


       //  Map.Entry<Integer, Integer>是一个内部类    map.entrySet()返回的是一个set集合

       for (Map.Entry<Integer, Integer> entry : map.entrySet()){

           System.out.println("数据:"+entry.getKey()+"   "+"出现次数:"+entry.getValue());

       }


   }

}


运行结果:

数据已经简化,方便观看

b14.png



相关文章
|
21天前
|
存储 Java C++
Java中的数据结构选择指南
Java中的数据结构选择指南
|
12天前
|
存储 安全 Java
Java基础之集合Map
【7月更文挑战第8天】Java中的Map集合以键值对方式存储数据,如`Map&lt;&quot;name&quot;, &quot;张三&quot;&gt;`。Map接口定义了存取、判断、移除等操作,包括`put`、`get`、`containsKey`等方法。HashMap是最常用的实现,基于哈希表,允许null键值,但不保证顺序。其他实现包括同步的Hashtable、处理属性文件的Properties、保持插入顺序的LinkedHashMap、基于红黑树的TreeMap、弱引用的WeakHashMap、并发安全的ConcurrentHashMap和针对枚举优化的EnumMap。
17 4
|
20天前
|
存储 安全 Java
如何在Java中实现自定义数据结构:从头开始
如何在Java中实现自定义数据结构:从头开始
|
28天前
|
存储 Java API
探讨Java中交换Map的Key和Value值的技术
探讨Java中交换Map的Key和Value值的技术
14 2
|
28天前
|
缓存 Java 测试技术
探讨Java中遍历Map集合的最快方式
探讨Java中遍历Map集合的最快方式
18 1
|
13天前
|
存储 安全 Java
Java Map集合:选择正确的实现方式
Java Map集合:选择正确的实现方式
|
21天前
|
存储 Java 开发者
如何在Java中实现自定义数据结构
如何在Java中实现自定义数据结构
|
21天前
|
Java
Java Map.Entry接口详解
Java Map.Entry接口详解
|
24天前
|
存储 算法 Java
解密Java中的运行时数据结构
解密Java中的运行时数据结构
|
25天前
|
存储 算法 Java
老程序员分享:java之数据结构【入门篇】
老程序员分享:java之数据结构【入门篇】
15 0

热门文章

最新文章