数据结构之Map/Set讲解+硬核源码剖析（一）+https://developer.aliyun.com/article/1413569
get和getOrDefault的源码
// get也可以用来判断是否包含相应的key public V get(Object key) { TreeMap.Entry<K,V> p = getEntry(key); return (p==null ? null : p.value); } default V getOrDefault(Object key, V defaultValue) { V v; // 三目运算符 为真返回v 为假返回默认值 return (((v = get(key)) != null) || containsKey(key)) ? v : defaultValue; }
3.remove
删除key对应的映射关系
源码：注意remove存在返回值
// remove存在返回值！！！ 返回你要删除的key对应的value public V remove(Object key) { TreeMap.Entry<K,V> p = getEntry(key); if (p == null) return null; V oldValue = p.value; deleteEntry(p); return oldValue; }
验证
System.out.println(map.remove("cat"));// 输出17 System.out.println(map.remove("Dog"));// 输出null
4.contains
包含两个contains方法，一个是判断是否存在key，一个判断是否存在value
System.out.println(map.containsKey("cat"));// 输出true System.out.println(map.containsKey("Dog"));// 输出false System.out.println(map.containsValue(15));// 输出true System.out.println(map.containsValue(100));// 输出false
源码
public boolean containsKey(Object key) { return getEntry(key) != null; } public boolean containsValue(Object value) { for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) if (valEquals(value, e.value)) return true; return false; }
5.keySet方法
返回不重复的key的集合 就是将Map中所有的key值存放到Set内部（存的时候会进行排序）
// 此处Set里面存放的类型要和key一致！！！ Set<String> set = map.keySet(); for (String s:set) { System.out.print(s + " ");// 输出apple bank cat }
源码
public Set<K> keySet() { return navigableKeySet(); } /** * @since 1.6 */ public NavigableSet<K> navigableKeySet() { KeySet<K> nks = navigableKeySet; return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this)); }
6.values
返回所有的value的可重复集合 和上一个方法类似 此方法是拿到所有的value将其存放到Collection里面
Collection<Integer> collection = map.values(); for (int val:collection) { System.out.print(val + " ");// 输出14 15 17 }
源码
public Collection<V> values() { Collection<V> vs = values; if (vs == null) { vs = new Values(); values = vs; } return vs; }
7.entrySet方法
返回所有的key--value的映射关系 可以理解为keySet和values的集合版本
Set<Map.Entry<String,Integer>> set = map.entrySet(); for (Map.Entry<String,Integer> entry:set) { System.out.println("key = " + entry.getKey() + " " +"value = " + entry.getValue()); } // 也可以直接打印 System.out.println(set); // 输出[apple=14, bank=15, cat=17]
注意：getKey和getValue是Map的内部类Entry中的方法 用于返回映射中的key和value，所以entrySet方法就相当于创建的Set集合中存储是一个一个Entry
注意：
1.Map是一个接口，只能实例化实现他的类，如TreeMap和HashMap，区别在于前者的底层是二叉搜索树，后者的底层是哈希表
2.Map中存放的key是唯一的（二叉搜索树中不能存放相同的值，哈希表中也不能存放相同的值）
3.在TreeMap中插入键值对时，key不能为空，否则就会抛NullPointerException异常，因为每次put一个元素都需要进行一次比较，而null不能直接比较，value可以为空。但 是HashMap的key和value都可以为空
4.利用keySet方法可以将所有的key分离出来(存放到set里)，利用values方法可以将所有的value分离出来(存放到Collection内部)
5.Map中的key不能直接修改，value可以修改(会直接被替换为新值，在二叉搜索树的put代码中就有)
四.set的使用
1.概念
Set是一种纯key模型的数据集合容器 Set是继承自Collection的接口类，也就是Set中不存在values
2.常用方法
3.注意事项：
1.TreeSet的底层其实是TreeMap，所以TreeSet无法存放相同的key值
2.Set实现了toString方法，可以直接打印
Set<String> set = new TreeSet<>(); set.add("lvzi"); set.add("biandu"); set.add("zhizi"); System.out.println(set);// 输出[biandu, lvzi, zhizi]
3.Set最大的功能就是对集合中的元素进行去重
4.实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础 上维护了一个双向链表来记录元素的插入次序。
5.TreeSet中不能插入null的key，HashSet可以
五.哈希表
1.概念
1.什么是哈希表
在顺序结构和平衡二叉树的存储结构中，如果想要搜索某个元素，必须要进行关键码(key)的多次比较，顺序结构的搜索效率是O(N),平衡二叉树的搜索效率是O(logN)，搜索的效率取决于比较的次数，，其实之所以需要比较是因为关键码(key)和值（val）之间没有一一对应的关系，如果建立一种关键码与存储位置一一对应的映射，那么我们就能不进行比较就拿到我们需要的数据。比如，，对于一个正比例函数，x与y之间是一一对应的，可以说y与x建立了一一对应的映射关系。
在计算机中，也有这样的一种数据结构，叫做哈希表，实现了关键码和存储位置的一一映射
这种映射关系通过哈希函数(hashFunc)建立（就像正比例函数建立x与y的映射关系一样）
比如：哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。
2.哈希冲突
如上图，如果我们再存储一个14，14%10 = 4,他的索引应该是4，但是4下标对应关键字key，不能再对应14了，此时就发生了哈希冲突
3.负载因子
α = 填入表中的元素 / 哈希表的长度
负载因子α用于定性描述冲突率，研究表明，负载因子越大，发生哈希冲突的概率就越大；负载因子越小，发生哈希冲突的概率就越小
2.常见的哈希函数
1.直接定制法
利用关键字的特性建立线性函数，实现关键字和存储位置的一一对应！
适用于数据简单，连续的情况
相关面试题：
387. 字符串中的第一个唯一字符 - 力扣（LeetCode）
思路分析
代码实现
// 1.使用计数数组 class Solution { public int firstUniqChar(String s) { int[] cnt = new int[26]; for (int i = 0; i < s.length(); i++) { cnt[s.charAt(i) - 'a']++; } for (int i = 0; i < s.length(); i++) { if(cnt[s.charAt(i) - 'a'] == 1) { return i; } } return -1; } } 2.// 使用哈希表 Map<Character,Integer> map = new HashMap<>(); for (int i = 0; i < s.length(); i++) { char ch = s.charAt(i); // 先获取ch的val 无论是否存在 是要val+1 不存在 设置默认值为0 更新后变为1 map.put(ch,map.getOrDefault(ch,0)+1); } for (int i = 0; i < s.length(); i++) { if(map.get(s.charAt(i)) == 1) { return i; } } return -1;
数据结构之Map/Set讲解+硬核源码剖析（三）+https://developer.aliyun.com/article/1413573
