心得技巧
html5HTML/XhtmlCSSXML/XSLTDreamweaver教程Frontpage教程心得技巧

Map 和 Set 【数据结构】

发布时间：2022-07-01 发布网站：脚本宝典
脚本宝典收集整理的这篇文章主要介绍了Map 和 Set 【数据结构】，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

Map 和 Set 1.标准库：TreeSet，TreeMap，HashSet，HashMap 2.二叉搜索树：对应TreeSet TreeMap 底层实现 3.哈希表：对应 HashMap，HashTree 底层实现

搜索

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

模型

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

  1. 纯 key 模型 ：即，我们 Set 要解决的事情，只需要判断关键字在不在集合中即可，没有关联的 Value —— 例：有一个英文词典，快速查找一个单词是否在词典中
  2. Key-Value 模型 ：即，我们 Map 要解决的事情，需要根据指定 Key 找到关联的 Value 例：梁山好汉的江湖绰号：每个好汉都有自己的江湖绰号

Map 中存储的就是 Key - Value 的键值对，Set 中只存储了 Key

Map 的使用

Map 和 Set 【数据结构】

Map.Entry<K, V>

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

方法说明
K getKey( )返回 Entry 中的 key
V getValue( )返回 Entry 中的 value
V setValue(V value)将键值对中的 value 替换为指定 value

常用方法

方法说明
V get (Object key)返回 key 对应的 value
V getOrDefault (Object key，V defaultValue)返回 key 对应的 value，key 不存在，返回默认值
V put (K key，V value)设置 key 对应的 value
V remove (Object key)删除 key 对应的映射关系
Set keySet ( )返回所有 key 的不重复集合
Collection values ( )返回所有 value 的可重复集合
Set<;map.Entry <K, V> > entrySet( )返回所有的 key-value 映射关系
boolean containsKey (Object key) (高效)判断是否包含 key
boolean containsValue (Object value) (低效)判断是否包含 value

HashMap 使用示例：

public static void main(String[] args) {
    Map<Integer,String> map = new HashMap<>();
    // put(key, value):插入key-value的键值对
    map.put(1,"hello~");
    // key  value 重复
    map.put(1,"hello");

    map.put(6,"Java");
    map.put(3,"Cpp");

    // put(key,value): key 为null
    map.put(null,"Python");

    // put(key,value): value 为null
    map.put(2,null);
    System.out.PRintln(map.get(null));

    System.out.println(map);
    // 返回 key 对应的 value
    System.out.println(map.get(6));
    // 找不到 返回会null
    System.out.println(map.get(10));

    // 打印所有的 key
    for (Integer key : map.keySet()) {
        System.out.print(key + " ");
    }
    System.out.println();

    // 打印所有的 value
    for (String value : map.values()) {
        System.out.print(value + " ");
    }
    System.out.println();

    // 按照映射关系打印
    for (Map.Entry<Integer,String> entry : map.entrySet()) {
        System.out.println(entry);
    }

    // 是否包含 key
    System.out.println(map.containsKey(6));
    //是否包含 value
    System.out.println(map.containsValue("Java"));
}
@H_360_589@ 

输出结果：
 

Map 和 Set 【数据结构】
 TreeMap 使用示例：
 

1.插入键值对
 

public static void main(String[] args) {
    Map<String,String> map = new TreeMap<>();
    //插入键值对
    map.put("西游记","吴承恩");
    map.put("红楼梦","曹雪芹");
    map.put("狂人日记","鲁迅");
    
    // value 重复
    map.put("阿Q正传","鲁迅");
    // key 重复
    map.put("阿Q正传","key不能重复");
    
    System.out.println(map.get("阿Q正传"));
}

 

输出结果：
 

Map 和 Set 【数据结构】
 

如果key存在，会使用 value 替换原来 key 所对应的 value，返回旧 value
 

key 不能为null
 

key 为null，会抛出 NullPointerException 异常
 

public static void main(String[] args) {
    Map<String,String> map = new TreeMap<>();
    // key 不能为 null，否则抛出异常
    map.put(null,"异常~");
}

 

输出结果：
 

Map 和 Set 【数据结构】
 value 可以为null
 

public static void main(String[] args) {
    Map<String,String> map = new TreeMap<>();
    // value 可以为null
    map.put("value为null",null);
    System.out.println(map.get("value为null"));
}

 

输出结果：
 

Map 和 Set 【数据结构】
 

注意事项：
 

  • Map 是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类 TreeMap 或者HashMap
  • TreeMap 中存放键值对的 key 是唯一的，value 是可以重复的
  • 在 TreeMap 中插入键值对时，key 不能为空，否则就会抛 NullPointerException 异常，但是 value 可以为空
  • Map 中的 key 可以全部分离出来，存储到 Set 中来进行访问 (因为 key 不能重复)
  • Map 中的 value 可以全部分离出来，存储在 Collection 的任何一个子集合中 (value可能有重复)
  • Map 中键值对的 key 不能直接修改，value 可以修改，如果要修改 key，只能先将该 key 删除掉，然后再进行重新插入
  • HashMap 和 TreeMap 的区别
 

Map底层结构TreeMapHashMap
底层结构红黑树哈希桶
插入 / 删除 / 查找@R_626_1304@O(LOGN)O(1)
是否有序关于 key 有序无序
线程是否安全不安全不安全
插入 / 删除 / 查找区别需要进行元素比较通过哈希函数计算哈希地址
比较与重写key 必须能够比较，否则会抛出 ClassCastException 异常自定义类型需要重写 equals 和 hashCode 方法
应用场景需要 key 有序场景下key 是否有序不关心，需要更高的时间性能


Set 的使用
 

Set与Map主要的不同：
 

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

常见方法：
 

方法说明
boolean add(E e)添加元素，但重复元素不会被添加成功
void clear( )清空集合
boolean contains(Object o)判断 o 是否在集合中
ITerator iterator( )返回迭代器
boolean remove(Object o)删除集合中的 o
int size( )返回set中元素的个数
boolean iSEMpty( )检测 set 是否为空，空返回 true，否则返回 false
Object[] toArray( )将 set 中的元素转换为数组返回
boolean containsAll(Collection<?> c)集合 c 中的元素是否在 set 中全部存在，是返回 true，否则返回 false
boolean addAll(Collection<? extends E> c)将集合 c 中的元素添加到 set 中，可以达到去重的效果


HashSet 代码示例：
 

public static void main(String[] args) {
    //1.实例化 Set
    Set<String> set = new HashSet<>();

    //2.插入元素 : add
    set.add("hello");
    set.add("Java");
    set.add("Cpp");
    // 插入null
    set.add(null);

    //3.判断某个值是否存在
    System.out.println("Java: " + set.contains("Java"));
    System.out.println("Python: " + set.contains("Python"));
    System.out.println("Cpp: " + set.contains("Cpp"));
    System.out.println("null: " + set.contains("null"));

    //4.删除某个值
    System.out.println("删除Cpp....");
    set.remove("Cpp");
    System.out.println("Cpp: " + set.contains("Cpp"));
    //删除null
    System.out.println("删除null....");
    System.out.println("null: " + set.contains(null));

    //5.打印Set
    // a) 直接打印
    System.out.println(set);
    // b) 循环遍历,使用迭代器
    // 迭代器的泛型参数 要和 集合类中保存的元素参数类型一致
    // 集合类内部自己实现自己版本的迭代器,不同的集合类 内部的迭代器类型不同，迭代方式也不同
    System.out.print("使用迭代器打印：");
    Iterator<String> iterator = set.iterator();
    while (iterator.hasNext()){
        String next = iterator.next();
        System.out.print(next + " ");
    }
}

 

输出结果：
 

Map 和 Set 【数据结构】
 TreeSet 代码示例：
 

public static void main(String[] args) {
    //1.实例化 Set
    Set<String> set = new TreeSet<>();

    //2.插入元素
    set.add("Hello");
    set.add("Java");
    set.add("Cpp");
    // 不能插入null，会抛出 空指针异常
//        set.add(null);

    //3.判断某个值是否存在
    System.out.println("Java: " + set.contains("Java"));
    System.out.println("Python: " + set.contains("Python"));
    System.out.println("Cpp: " + set.contains("Cpp"));
    // contains(key): key为null，抛出空指针异常
//        System.out.println("null: " + set.contains(null));

    //4.删除某个值
    System.out.println("删除Cpp....");
    set.remove("Cpp");
    System.out.println("Cpp: " + set.contains("Cpp"));
    //删除null
    System.out.println("删除null....");
    // remove(key): key为null，抛出空指针异常
//        set.remove(null);
//        System.out.println("null: " + set.contains(null));

    //5.打印 set
    // a) 直接打印
    System.out.println(set);
    // b) 迭代器打印
    System.out.print("使用迭代器打印：");
    Iterator<String> iterator = set.iterator();
    while (iterator.hasNext()){
        String next = iterator.next();
        System.out.print(next + " ");
    }
}

 

输出结果：
 

Map 和 Set 【数据结构】
 

注意事项：
 

  • Set 是继承自 Collection 的一个接口类
  • Set 中只存储了 key，key 是唯一的，不能重复
  • Set 最大的功能就是对集合中的元素进行去重
  • Set 中的 Key 不能修改，如果要修改，先将原来的删除掉，然后再重新插入
  • TreeSet 和 HashSet 的区别
 

SetTreeSetHashSet
底层结构红黑树哈希桶
插入 / 删除 / 查找时间复杂度O(logN)O(1)
是否有序关于 key 有序不一定有序
线程是否安全不安全不安全
插入 / 删除 / 查找区别按照红黑树的特性来进行插入和删除1. 先计算 key 哈希地址；2. 然后进行插入和删除
比较与重写key 必须能够比较，否则会抛出 ClassCastException 异常自定义类型需要重写 equals 和 hashCode 方法
应用场景需要 key 有序场景下key是否有序不关心，需要更高的时间性能


题目练习
 

只出现 1 次的数字
 

题目： 在线OJ
 

Map 和 Set 【数据结构】
 思考：
 

方法一： 通过 Map 统计每个数字出现的次数，再遍历 Map 找到那个只出现一次的数字
 

  • 创建 Map<Integer，Integer>，key：当前出现的数字；value：该数字出现次数
  • 遍历统计次数即可~
 

方法二： 按位异或 A ^ B ^ A = B；A ^ 0 = A，异或规则，相同为0，相异为1
 

代码实现：
 

  • 方法1
 

public int singleNumber(int[] nums) {
    // key : 当前数字
    // value : 数字出现次数
    Map<Integer,Integer> map = new HashMap<>();
    for (int x : nums) {
        Integer value = map.get(x);
        // 当前数字在 map 中不存在，新增一个键值对
        if(value == null){
            map.put(x,1);
        }
        //这个数字已经存在了
        else{
            map.put(x,value + 1);
        }
    }
    // 遍历 map ，找到出现次数为1的数
    for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
        // getValue 得到的是一个 Integer 包装类
        // 使用 equals，相当于对 1 自动装箱
        // 使用 == ，相当于对 Integer 自动拆箱
        if(entry.getValue().equals(1)){
            return entry.getKey();
        }
    }
    //没找到
    return 0;
}

 

  • 方法2
 

public int singleNumber(int[] nums) {
    int result = 0;
    for (int x : nums) {
        result ^= x;
    }
    return result;
}

 

复制带随机指针的链表
 

题目： 在线OJ
 

Map 和 Set 【数据结构】
 思考：
 

  • 创建一个 Map <Node，Node>，key：旧链表的节点；value：新链表的节点(旧链表对应节点的拷贝)
  • Map 结构创建好了之后，遍历旧链表，取出节点在 Map 中找到对应的 value 例：新node1.next = map.get (旧node1.next)； 新node1.random = map.get (旧node1.random)；
 

代码实现：
 

public Node copyRandoMList(Node head) {
    //1.创建 map
    Map<Node,Node> map = new HashMap<>();
    //2.遍历旧链表，把旧链表的每个节点 依次插入到map中
    // key: 旧链表节点
    // value: 新链表节点
    for (Node cur = head;cur != null;cur = cur.next){
        map.put(cur,new Node(cur.val));
    }
    // 再次遍历链表，修改新链表节点中的 next 和 random
    for (Node cur = head;cur != null;cur = cur.next){
        // 先从 map 中找到 该 cur对应的新链表对应的节点
        Node newCur = map.get(cur);
        newCur.next = map.get(cur.next);
        newCur.random = map.get(cur.random);
    }
    // 返回新链表的头节点
    return map.get(head);
}

 

宝石和石头
 

题目： 在线OJ
 

Map 和 Set 【数据结构】
 思考：
 

  • 遍历 J，把所有宝石放到一个 set 里
  • 遍历 S，和 set 中元素比较即可
 

代码实现：
 

public int numJewelsInStones(String jewels, String stones) {
    // 先遍历J，把所有宝石类型加到一个 set 里
    Set<Character> set = new HashSet<>();
    for (char c : jewels.toCharArray()) {
        set.add(c);
    }
    // 遍历 S，和set 中元素比较
    int ret = 0;
    for (char c : stones.toCharArray()) {
        if(set.contains(c)){
            ret++;
        }
    }
    return ret;
}

 

宝石和石头
 

题目： 在线OJ
 

 
 
旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字，请你列出肯定坏掉的那些键
 
 
 
 
输入描述： 输入在2行中分别给出应该输入的文字、以及实际被输入的文字。每段文字是不超过80个字符的串，由字母A-Z（包括大、小写）、数字0-9、 以及下划线“_”（代表空格）组成。题目保证2个字符串均非空
 
 
 
 
输出描述： 按照发现顺序，在一行中输出坏掉的键。其中英文字母只输出大写，每个坏键只输出一次。题目保证至少有1个坏键
 

 

思考： 坏掉的键，即：按下键，没有输出 给出一个预期输出的字符串，再给出一个实际输出的字符串 找到那些预期要输出，但实际没输出的字符，这样的字符就是坏掉的键 键盘上某个键坏了，则其大小写字母均不会输出，需要把 A 和 a当成同一种情况
 

代码实现：
 

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    //循环读取两个字符串
    // 字符串1: 预期输出内容; 字符串2: 实际输出内容
    while (scan.hasNext()){
        String expected = scan.next();
        String actual = scan.next();
        // 把输入的字符串全部转换成大写字母
        exPEcted = expected.toUpperCase();
        actual = actual.toUpperCase();
        // 创建一个set, 存储实际输出的每个字符
        Set<Character> actualSet = new HashSet<>();
        for (int i = 0; i < actual.length(); i++) {
            // set中的元素 不能重复，若add时，发现这个元素已经存在，add操作就会失败，
            // 但不会有任何影响，不会抛出异常，也不会影响元素原来的内容
            actualSet.add(actual.charAt(i));
        }
        // 存放坏的键的set
        Set<Character> brokenKeySet = new HashSet<>();
        // 遍历预期输出内容,看是否匹配即可
        for (int i = 0;i < expected.length();i++){
            char c = expected.charAt(i);
            //当前字符被输出，该键没坏
            if(actualSet.contains(c)){
                continue;
            }
            //没被输出，就是坏的键
            // [坏的键],预期字符串中可能多次出现坏的键,但最后输出结果 只输出一次
            //  需要去重操作
            if(brokenKeySet.contains(c)){
                continue;
            }
            System.out.print(c);
            brokenKeySet.add(c);
        }
    }
}

 

前 K 个高频单词
 

题目： 在线OJ
 

Map 和 Set 【数据结构】
 

思考：
 

  • 先统计数组中每个单词出现的次数，使用 Map
  • 把键值对组织到一个 ArrayList 中
  • 按照题目要求降序排序(出现次数 + 字典序)
  • 取前 K 个元素即可
 

代码实现：
 

//比较器
static class MyComparator implements Comparator<String>{
    private Map<String,Integer> map;

    public MyComparator(Map<String, Integer> map) {
        this.map = map;
    }

    @override
    public int compare(String o1, String o2) {
        int count1 = map.get(o1);
        int count2 = map.get(o2);
        if(count1 == count2) {
            // String 自身的 compareTo
            return o1.compareTo(o2);
        }
        return count2 - count1;
    }
}
public List<String> topKFrequent(String[] words, int k) {
    //1.统计每个单词出现的次数
    Map<String,Integer> map = new HashMap<>();
    for (String s : words) {
        Integer count = map.getOrDefault(s,0);
        map.put(s,count + 1);
    }
    //2.把刚才统计的字符串内容放到ArrayList 中
    ArrayList<String> arrayList = new ArrayList<>(map.keySet());
    //3.排序
    // sort 默认按照元素的自身大小升序排序(字典序)
    // 自己写一个比较器
//        Collections.sort(arrayList,new MyComparator(map));
    //匿名内部类 这个类只需要用一次，用完就丢了~~
//        Collections.sort(arrayList, new Comparator<String>() {
//            @Override
//            public int compare(String o1, String o2) {
//                int count1 = map.get(o1);
//                int count2 = map.get(o2);
//                if(count1 == count2) {
//                    // String 自身的 compareTo
//                    return o1.COMpareTo(o2);
//                }
//                return count2 - count1;
//            }
//        });
    // lambda 表达式  本质上就是一个匿名方法,也可以认为是一个对象
    Collections.sort(arrayList, (o1, o2) -> {
        int count1 = map.get(o1);
        int count2 = map.get(o2);
        if(count1 == count2) {
            // String 自身的 compareTo
            return o1.compareTo(o2);
        }
        return count2 - count1;
    });
    //取前 K 个元素
    return arrayList.subList(0,k);
}

 

Map 和 Set 【数据结构】

脚本宝典总结

以上是脚本宝典为你收集整理的Map 和 Set 【数据结构】全部内容，希望文章能够帮你解决Map 和 Set 【数据结构】所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。
标签：capHashMapjavajavascriptlistphppythonsortStringwhilewhile参数参数应用场景应用场景排序排序查找查找程序员程序员遍历遍历
猜你在找的心得技巧相关文章
其他相关热搜词更多
phpjavapython程序员loadpost-format-gallerydivString参数开发ListcapMapClass工具安装SQL数据库资源this
全站导航更多
html5HTML/XhtmlCSSXML/XSLTDreamweaver教程Frontpage教程心得技巧JavaScriptASP.NETPHP编程正则表达式AJAX相关ASP编程JSP编程编程10000问CSS/HTMLFlexvbsDOS/BAThtahtcpythonperl游戏相关VBA远程脚本ColdFusionMsSqlMysqlmariadboracleDB2mssql2008mssql2005SQLitePostgreSQLMongoDB星外虚拟主机华众虚拟主机Linuxwin服务器FTP服务器DNS服务器Tomcatnginxzabbix云和虚拟化bios系统安装系统系统进程Windows系列LINUXRedHat/CentosUbuntu/DebianFedoraSolaris红旗Linux建站经验微信营销网站优化网站策划网络赚钱网络创业站长故事alexa域名photoshop教程摄影教程Fireworks教程CorelDraw教程Illustrator教程Painter教程Freehand教程IndesignSketch笔记本主板内存CPU存储显卡显示器光存储鼠标键盘平板电脑安全教程杀毒防毒安全设置病毒查杀脚本攻防入侵防御工具使用业界动态Exploit漏洞分析
最新心得技巧教程
热门心得技巧教程