Map和Set(下)

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

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获取valInteger 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来比较@Overridepublic 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@Overridepublic int hashCode() {return Objects.hash(id);}
}public static void main2(String[] args) {//TODO 如果是int类型我们可以通过整形的数/数组长度来获取哈希地址,那么如果是字符串型?自定义类型,该如何呢?//把对象转化为整数hashcodeStudent student1 = new Student("1233");Student student2 = new Student("1233");//得到俩个对象的hashCodeSystem.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来获取hashcodeint 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来比较@Overridepublic 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@Overridepublic 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<>();//把元素放进setfor (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出来了.

完整代码:

//创建计数器和setint count = 0;HashSet<Character> set = new HashSet<>();//把jewels的元素放到setfor (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放进setHashSet<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) {//得到nextmap.get(cur).next = map.get(cur.next);//得到radommap.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.统计每个单词出现的次数,存储到mapMap<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;}
}