【Java】数据结构Map和Set的使用

章节目标

掌握Map/Set及实际实现类 HashMap/TreeMap/HashSet/TreeSet的使用。

掌握 TreeMap 和 TreeSet 背后的数据结构搜索树的原理和简单实现。

掌握 HashMap 和 HashSet 背后的数据结构哈希表的原理和简单实现。

概念

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

关于Map的说明

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

Map 的常用方法说明 以及 代码的实现

public static void main1(String[] args) {
    Map<String, Integer> map = new HashMap<>();//Map<k,v>
    //k元素，v值
    map.put("abc",3);//放元素,设置K对应的value
    map.put("bit",2);
    map.put("hello",4);//存放元素顺序和打印顺序不一样
    //为什么呢？ hashmap存储元素的时候，不是按照你的存储顺序进行打印的
    //存储的时候，是根据一个函数来进行存储的，具体存储到哪里？由函数来确定
    //这个函数是哈希函数
    System.out.println(map);
    int ret = map.get("bit");//返回K对应的value
    System.out.println(ret);
    System.out.println(map.get("bit2"));
    Integer ret2= map.remove("bit");//删除bit，返回值是v，v是整数
    System.out.println(ret2);
    System.out.println(map);
}

public static void main2(String[] args) {
    Map<String, Integer> map = new HashMap<>();
    map.put("abc",3);//放元素
    map.put("bit",2);//put存储元素的时候，要注意key如果相同 val值会被覆盖
    map.put("hello",4);
    map.put("hello",5);
    System.out.println(map);
    Set<String> set = map.keySet();//返回所有K的不重复集合
    //set这个集合当中存储的元素 都是不重复的
    System.out.println(set);
}

public static void main3(String[] args) {
    Map<String, Integer> map = new HashMap<>();
    map.put("abc",3);
    map.put("bit",2);
    map.put("hello",4);
    map.put(null,null);
    System.out.println(map);
    //返回所有key-value映射关系 就是将 key，val看做一个整体 放在set当中
    Set<Map.Entry<String,Integer>> entrySet =map.entrySet();//返回值是Set<Map.Entry<Sting,Integer>>
    for (Map.Entry<String,Integer> entry:entrySet) {
        System.out.println(entry.getKey()+"->" + entry.getValue());
    }
}

// Set 的使用说明
public static void main(String[] args) {
    Set<Integer> set = new HashSet<>();
    set.add(1);
    set.add(2);
    set.add(3);
    //如果在添加一个1 它只会存储一个1(自动去重)
    set.add(1);
    System.out.println(set);
    //返回迭代器 返回值 Iterator<Integer> iterator
    Iterator<Integer> iterator = set.iterator();
    //迭代器打印方式
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
}

注意：

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

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

1. 在Map中插入键值对时，key不能为空，否则就会抛NullPointerException异常，但是value可以为空

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

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

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

2. TreeMap和HashMap的区别

面试题练习

1.**给定1w个数据，统计每个数据出现的次数**

public static void main(String[] args) {
    int[] array = new int[1_0000];
    Random random = new Random();
    for (int i = 0; i < array.length; i++) {
        array[i] = random.nextInt(1000);
    }
    Map<Integer,Integer> ret = func1(array);
    System.out.println(ret);
}

//key是关键字 value 出现的次数
public static Map<Integer,Integer> func1(int[] array) {
    HashMap<Integer,Integer> map = new HashMap<>();
    //出现次数做题的关键在于 判断array中的元素是否在map当中，如果不在就是1
    //在就是在原来的基础上＋1
    for (int x :array) {
        if(map.get(x) == null) {//如果关键字x一次都没有出现
            map.put(x,1);//不在就是1
        }else {
            //关键字X在array中
            int val = map.get(x);//找到原来的x所对应的次数
            map.put(x,val+1);
        }
    }
    return map;
}

这里关于set和map的使用：

//1.**当题中说到搜索的时候我们 采用set和map**
//2.**当 求 次数的时候 我们使用 map**
//3.**当 求 去重 重复 的时候 我们使用 set**

**2.将10W个数据中的数据去重**

//方法直接把数据放在set当中
public static Set<Integer> func2(int[] array) {
    HashSet<Integer> set = new HashSet<>();
    for (int x : array) {
        set.add(x);
    }
    return set;
}

3.

**从10w个数据中，找出第一个重复的元素**

public static int func3(int[] array) {
    HashSet<Integer> set = new HashSet<>();
    for (int x : array) {
        if(set.contains(x)) {
            return x;
        }else {
            set.add(x);
        }
    }
    return -1;
}

**只出现一次的函数**

public int singleNumber1(int[] nums) {
    HashSet<Integer> set = new HashSet<>();
    for (int x : nums) {
        if(set.contains(x)) {
            set.remove(x);
        }else {
            set.add(x);
        }
    }
    for (int i = 0; i < nums.length; i++) {
        if(set.contains(nums[i])) {
            return nums[i];
        }
    }
    return -1;
}

**复制带随机指针的链表**

public Node1 copyRandomList(Node1 head) {
    Map<Node1,Node1> map = new HashMap<>();
    Node1 cur = head;
    while (cur != null) {
        Node1 node1 = new Node1(cur.val);
        map.put(cur,node1);
        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;
    }
    return map.get(head);
}

**宝石和石头**

public int numJewelsInStones(String jewels, String stones) {
    HashSet<Character> set = new HashSet<>();
    for (Character ch : jewels.toCharArray()) {
        set.add(ch);
    }
    int count = 0;
    for (Character ch : stones.toCharArray()) {
        if(set.contains(ch)) {
            count++;
        }
    }
    return count;
}

**旧键盘** (20)旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字，请你列出
//肯定坏掉的那些键。
    //输入 7_This_is_a_test 预期输出
    // _hs_s_a_es  实际输出
    //输出7TI

public static void func(String strExce,String strActual) {
    HashSet<Character> set = new HashSet<>();
    for (Character ch :strExce.toUpperCase().toCharArray()) {
        set.add(ch);
    }
    HashSet<Character> broken = new HashSet<>();
    for (Character ch :strActual.toUpperCase().toCharArray()) {
        if(!set.contains(ch) && !broken.contains(ch)) {
            System.out.println(ch);
            broken.add(ch);
        }
    }
}

public static void main8(String[] args) {
    func("7_This_is_a_test","_hs_s_a_es");

}