Map

1 搜索: 在大量的数据元素中找到某个特定的数据元素.

2 搜索的数据称为关键字(Key)，和关键字对应的称为值(Value)，所以模型会有两种： (1) 纯 key 模型, 即我们使用 Set 要解决的事情，只需要判断关键字在不在集合中即可,没有关联的 value. (2) Key-Value 模型, 即我们 Map 要解决的事情, 需要根据指定 Key找到关联的 Value. 主要实现类 HashMap, TreeMap.

3 Map 的使用:

map.keySet() 返回所有的 key的集合. map.entrySet() 返回所有的 key-value的集合. map.values() 返回所有的 values的集合.

public static void main(String[] args) { //1.创建Map实例，泛型参数有两个，第一个参数是key的类型，第二个参数是value的类型 Map<String, String> map = new HashMap<>(); //2.使用size获取到元素个数（键值对个数） System.out.println(map.size()); //3.使用isEmpty查看是否为空 System.out.println(map.isEmpty()); //4.使用put方法把一些键值对存放进去 map.put("及时雨", "宋江"); map.put("玉麒麟", "卢俊义"); map.put("智多星", "吴用"); map.put("入云龙", "公孙胜"); map.put("及时雨","songjiang"); //如果两个key值重复，后者value就会覆盖前者 //5.使用get方法跟据key来查找对应的value,如果key不存在，返回null // getOrDefault如果key不存在，返回默认值 System.out.println(map.get("及时雨")); System.out.println(map.get("玉麒麟")); System.out.println(map.get("大刀")); System.out.println(map.getOrDefault("行者", "武松")); //6.通过containsKey和containsValue判断某个值是否存在 //containsKey执行效率高，containsValue执行效率低，不推荐 System.out.println(map.containsKey("智多星")); System.out.println(map.containsValue("公孙胜")); //Map中的元素和插入顺序无关，取决于具体的实现方式 for (Map.Entry<String, String> x : map.entrySet()) { System.out.println(x.getKey() + ": " + x.getValue()); } map.remove("入云龙"); System.out.println("删除元素后："); for (Map.Entry<String, String> x: map.entrySet()) { System.out.println(x.getKey() + ": " + x.getValue()); } System.out.println(map); // 也可以直接输出map }

4 Set 的使用: Set中无重复元素, 如果后面添加相同的元素, 就会后者覆盖前者.

public static void main(String[] args) { Set<String> set = new HashSet<>(); set.add("hello"); set.add("world"); set.add("java"); System.out.println(set.contains("world")); set.remove("world"); System.out.println(set.contains("world")); // 5. 遍历打印 set System.out.println(set); // 如果要想循环遍历 set 中的元素, 就需要使用迭代器了 // 迭代器的泛型参数, 要和集合类中保存的元素参数保持一致. Iterator<String> iterator = set.iterator(); while (iterator.hasNext()) { String next = iterator.next(); System.out.println(next); } }

5 map 和 set 练习.

1 一个数字只有一个数字只出现了一次,其他数字都出现了两次,找到只出现一次的数字. (扩展: 有两个数字...,找到这两个数字...,也使用异或.) (1) 使用异或(简单方便) 0与一个数字异或得到这个数字, 与两个相同的数字异或得到0本身. public int singleNumber(int[] array) { int ret = 0; for (int x : array) { ret ^= x; } return ret; } (2) 使用map. public int singleNumber(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); for (int x : nums) { Integer value = map.get(x); if (value == null) { // 当前这个数字在 map 中不存在. 就新增一个键值对 map.put(x, 1); } else { // 当前这个数字前面已经存在过了~, 把 value 再加 1 即可 map.put(x, value + 1); } } // for (Map.Entry<Integer, Integer> entry : map.entrySet()) { // if (entry.getValue().equals(1)) { // return entry.getKey(); // } // } Iterator<HashMap.Entry<Integer, Integer>> iterator = map.entrySet().iterator(); while (iterator.hasNext()) { HashMap.Entry<Integer, Integer> entry = iterator.next(); if (entry.getValue().equals(1)) { return entry.getKey(); } } // 理论上讲, 只要输入数组给的是正确的内容, 这里的 return 0 是不会触发的. return 0; } 2 坏键盘打字: 给出应该输入的一段文字, 以及实际被输入的文字, 请你列出肯定坏掉的那些键 public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { String expected = scanner.next(); String actual = scanner.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<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)) { // 此处的 brokenKeySet 用于辅助去重. 防止同一个坏键被打印多次 continue; } System.out.print(c); brokenKeySet.add(c); } } } 3 复制带随机指针的链表 4 前k个高频单词

6 哈希表. (1) 顺序结构以及平衡树(任意节点的子树的高度差<=1), 元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较. 顺序查找时间复杂度为O(N), 平衡树中为树的高度, 即O(logN). (2) 理想的搜索方法:可以不经过任何比较，一次直接从表中得到要搜索的元素. 如果构造一种存储结构，通过 某种函数使 元素的存储位置与它的关键码之间能够建立一一映射的关系, 那么在查找时通过该函数可以很快找到该元素. (3) 向该结构中插入或者搜索元素时, 都是通过 对元素的关键码进行计算得到hashcode, 然后对应具体位置的. (4) 该方式即为哈希(散列)方法, 哈希方法中使用的转换函数称为哈希(散列)函数, 构造出来的结构称为哈希表(散列表). (5) 哈希表的本质 依赖了 数组 的随机访问能力, 在哈希表中插入 查找 删除的时间复杂度都近似为O(1). 7 哈希冲突. (1) key不同元素通过相同哈希函数计算出相同的哈希地址, 该种现象称为哈希冲突(哈希碰撞). (2) 冲突的发生是必然的，但我们能通过设计更巧妙的哈希函数来降低冲突率.

8 哈希冲突的解决. (1) 闭散列 (开放定址法): 在冲突位置开始往后找, 直到寻找到下一个空位置为止.我们用的是闭散列的 线性探测法. 闭散列的最大缺陷就是 空间利用率比较低, 这也是哈希的缺陷.

(如果数组元素的个数选的比较大, 确实冲突降低了, 但是浪费的空间也变多了. 另外如果把数组长度选为一个 素数, 那么冲突概率也会低一点). (2) 开散列/哈希桶 (链地址法): Java 中使用的是开散列方式解决冲突的. 开散列中每个桶中放的都是发生哈希冲突的元素. 标准库中的 HashMap 就是通过 开散列的方式处理hash冲突. 如果发现链表过长, 就会把链表的结构调整成 红黑树 的结构. 9 负载因子: 哈希表中元素的填满程度. (负载因子越小, 产生冲突的可能越小). (1) 当前hash表中 实际元素个数 / 数组capacity(容量) ----->负载因子. (2) 对于闭散列负载因子十分重要, 要严格控制在0.7~0.8. 标准库中的负载因子为0.75, 超过它就会进行扩容操作. 闭散列的负载因子一定小于1. (3) 闭散列可以根据负载因子的值 来决定是否要对hash表进行扩容. 扩容就是申请一个更大的数组作为新的hash表,把原来的元素都拷贝过去(非常耗时). (4) 开散列的 负载因子 可以大于1, 标准库中的负载因子为0.75. 开散列冲突更严重时的解决办法, 每个桶的背后是另一个哈希表 或者 每个桶的背后是一棵搜索树(红黑树).

10 总结. (1) hash冲突 理论上是客观存在的, 而它的各种插入 查找删除的时间复杂度 近似O(1). 最终取决于hash冲突的严重程度. 解决方法: 可以让数组更长一些. 可以选择更 合理的哈希函数 (例如 数组长度设为素数, 然后% 素数). (2) hash函数的目标就是为了把key映射成下标 (希望映射过程中能尽量避免冲突). (3) key为整数时, 算hash比较好算. 如果key为String时,hash就比较复杂( md5,sha1 两种常见的 字符串 hash算法) (4) 虽然哈希表一直在和冲突做斗争, 但实际工作中我们认为哈希表的冲突率是不高的, 冲突个数是可控的. 也就是每个桶中的链表的长度是一个常数, 所以通常我们认为哈希表的插入/删除/查找时间复杂度是O(1)

11 哈希思想 (这种思想很重要)的应用在实际工作中很常见. 分布式的核心思想就是 hash. 海量数据处理问题, 核心就是哈希切分. 在磁盘中的查找效率太低, 内存中的查找效率就很高,如果一台机器放不下就用多台. 12 实现一个自己的 HashMap. (存放的是 <k,v> 结构的元素).

public class MyHashMap { static class Node{ public int key; public int value; public Node next; public Node(int key, int value) { this.key = key; this.value = value; } } private static final double LOAD_FACTOR=0.75; 自定义一个负载因子 private int hashFunc(int key) { 实际的 hashFunc 可能会比较复杂的. return key%array.length; } 是一个Node类型的数组, 数组的每个元素又是一个链表的头结点, 数组长度为101. private Node[] array=new Node[101]; private int size=0; //表示当前hash表中元素的个数 public void put(int key,int value){ //1.先把key映射成数组下标 int index=hashFunc(key); //2.跟据下标找到对应链表 Node list=array[index]; //3.当前key是否在链表中在 for(Node cur=list;cur!=null;cur=cur.next){ if(cur.key==key){ // key 已经存在, 直接修改 value 即可 cur.value=value; return; } } //4.如果刚才循环结束，没有找到相同key的节点，直接插入到指定链表的头部 //此处实现尾插也可以，但是比较麻烦 Node newNode= new Node(key, value); newNode.next=list; array[index]=newNode; size++; if(size/array.length>LOAD_FACTOR){ resize(); } } 扩容操作 (比较 难理解) private void resize() { Node[] newArray=new Node[array.length*2]; 把原来hash表中的所有元素搬运到新的数组上. for(int i=0;i<array.length;i++){ for(Node cur=array[i];cur!=null;cur=cur.next){ int index=cur.key%newArray.length; Node newNode= new Node(cur.key, cur.value); newNode.next=newArray[index]; newArray[index]=newNode; } } //让新数组替代原数组 array=newArray; } //根据 key 查找指定元素. 如果找到返回对应 value. 如果没找到, 返回 null public Integer get(int key){ //返回类型设置成封装类, 就可以返回null. int index=hashFunc(key); Node list=array[index]; for(Node cur=list;cur!=null;cur=cur.next){ if(cur.key==key){ return cur.value; } } return null; } }

13 LinkedHashMap 是有序的. 现在需要把学生 按年龄降序排列, 就使用 LinkedHashMap.

public class DemoC { User 这里省略没写... public static HashMap<Integer, User> sortHashMap(HashMap<Integer, User> map) { //首先拿到 map 的键值对集合 Set<Map.Entry<Integer, User>> entrySet = map.entrySet(); List<Map.Entry<Integer, User>> list = new ArrayList<>(entrySet); Collections.sort(list, new Comparator<Map.Entry<Integer, User>>() { @Override public int compare(Map.Entry<Integer, User> o1, Map.Entry<Integer, User> o2) { return o2.getValue().getAge() - o1.getValue().getAge(); } }); LinkedHashMap<Integer, User> linkedHashMap = new LinkedHashMap<>(); for (Map.Entry<Integer, User> entry : list) { linkedHashMap.put(entry.getKey(), entry.getValue()); } return linkedHashMap; } public static void main(String[] args) { HashMap<Integer, User> users = new HashMap<Integer, User>(); users.put(1, new User("张三", 25)); users.put(2, new User("李四", 22)); users.put(3, new User("王五", 28)); // 输出排序后的. HashMap<Integer, User> sortHash = sortHashMap(users); for (Map.Entry<Integer, User> entry : sortHash.entrySet()) { System.out.println(entry.getKey() + ":" + entry.getValue()); } // 也可以直接输出 System.out.println(sortHash); {3=User{name='王五', age=28}, 1=User{name='张三', age=25}, 2=User{name='李四', age=22}} } }