有关Java中的集合(2):Map＜T＞(底层源码分析)

学习目标 核心掌握Map集合 1.Map<K,V>

● 实现了Map接口的集合对象的集合元素： 成对的值 key-value 键值对 ● key对象是不能重复的. value可以重复。 ● 核心: 根据key获得value。

1.1 层级 public interface Map<K, V> {} 1.2 常用方法

1.3 使用方法 private static void demo1() { //测试Map集合方法 //在正常开发中 map的key的类型: Integer/Long/String map的value随意给类型(开发功能)。 //一定要使用自定义的类型作为map的key。UserInfo Product HashMap<Integer,String> map = new HashMap<>(); //1.新增 map.put(1,"abc"); map.put(2,"hello"); //map.put(3,null); map.putIfAbsent(3,"aaa");//等价于put map.put(3,"bbb"); map的key重复了 新值覆盖旧值 Map<Integer, String> map1 = Map.of(3, "a",4,"b"); map.putAll(map1);//将一个map的集合所有数据 存储到指定的map集合中 //2.删除 String removeValue = map.remove(3); System.out.println(removeValue); System.out.println(map.remove(3, "bbb")); //3.修改 String oldValue = map.replace(3, "张三"); System.out.println(oldValue); //System.out.println(map.replace(3, "bbb", "张三")); //修改满足条件的value值 map.replaceAll(new BiFunction<Integer, String, String>() { @Override public String apply(Integer key, String value) { //System.out.println("key:"+key+"---value:"+value); if(key<=2){ value = "张三"; } return value; } }); map.replaceAll((key,value)->"张三");//等同于将所有的value都改为 张三 //4.查询 String value = map.get(20); System.out.println(value); System.out.println(value.equals("hello")); //5.其它方法 System.out.println(map.size()); System.out.println(map.isEmpty()); System.out.println(map.containsKey(1)); System.out.println(map.containsValue("hello")); map.clear(); System.out.println(map);//{1=abc, 2=hello, 3=bbb} Collection/数组 [] } 1.4 遍历集合 private static void demo2() { //没有UserInfo这样类的前提下 //使用map集合存储一个完整用户信息 id name pass age.... Map<String, Object> map = new HashMap<>(); map.put("id", 1001); map.put("name", "张三"); map.put("pass", "12435832"); map.put("age", 20); //遍历map集合数据 //Collection、List、Set //forEach 增强for 迭代器 普通for //在jdk1.8之前 建议使用: 1. Set<Entry<K,V>> entrySet();(推荐使用 性能高) //1.1 获得Set集合对象----> 维护的就是一个个的Entry对象---->等价于是Map集合每组数据 Set<Map.Entry<String, Object>> entrySet = map.entrySet(); //1.2 遍历Set集合 for (Map.Entry<String, Object> entry : entrySet) { String key = entry.getKey(); Object value = entry.getValue(); System.out.println("key:"+key+"---value:"+value); } // 2. Set<K> keySet(); //2.1 获得map集合所有的key Set<String> keySet = map.keySet(); //2.2 遍历set集合 Iterator<String> it = keySet.iterator(); while (it.hasNext()) { String key = it.next(); Object value = map.get(key); System.out.println("key:"+key+"---value:"+value); } //3.forEach(); 1.8之后 推荐使用 map.forEach(new BiConsumer<String, Object>() { @Override public void accept(String key, Object value) { System.out.println("key:"+key+"---value:"+value); } }); //map.forEach((k,v)-> System.out.println("key:"+k+"---value:"+v)); //4.Collection values(); 使用蛮多 Collection<Object> values = map.values(); System.out.println("所有的values:"+values); System.out.println(map); } 1.5 merge private static void demo3() { //使用Map集合: 随意给定一个字符串的数据 统计字符串中每个字符出现的次数。 String str = "dhshdsgy5324244ffffhsahgs"; Map<String, Integer> map = new HashMap<>(); //1.获得每个字符 循环遍历String----> String方法 int length = str.length(); for (int index = 0; index < length; index++) { String s = String.valueOf(str.charAt(index));// char转String //map集合有这个key count++ //2. map集合中是否存在s? Integer count = map.get(s); if (count == null) { count = 1; } else { count++; } map.put(s, count); // map.merge(s, 1, new BiFunction<Integer, Integer, Integer>() { // @Override // public Integer apply(Integer oldValue, Integer value) { // return Integer.sum(oldValue,value); // } // }); map.merge(s, 1, Integer::sum); } map.forEach((k, v) -> { System.out.println(k + ":" + v); }); } 1.5 集合嵌套 private static void demo4() { //目的: 集合嵌套 //List<Map<Key,Value>> //Map<Key,List<T>> //Map<Key,Map<K,V>> //使用map集合维护: 城市级联的数据 //根据指定的省份获得对应的所有的城市数据。 value get(key); Map<Integer,List<String>> provinceMap = new HashMap<>(); List<String> cityList = new ArrayList<>(10); Collections.addAll(cityList,"郑州市","开封市","洛阳市"); provinceMap.put(1001,cityList); //provinceMap.put(1001,List.of()); cityList = new ArrayList<>(10); Collections.addAll(cityList,"石家庄市","保定市","唐山市"); provinceMap.put(2001,cityList); //获得展示河南省份下的所有的城市信息 1001 List<String> list = provinceMap.get(2001); System.out.println(list); } public static void method1() { HashMap<String, Integer[]> hashMap = new HashMap<>(); Integer[] integers = new Integer[10]; hashMap.put("abc", integers); HashMap<Integer, Stu> stuHashMap = new HashMap<>(); stuHashMap.put(1, new Stu()); HashMap<Integer, List<Stu>> stuHashMap2 = new HashMap<>(); LinkedList<Stu> linkedList = new LinkedList<>(); ArrayList<Stu> arrayList = new ArrayList<>(); arrayList.add(new Stu()); stuHashMap2.put(1, arrayList); stuHashMap2.put(2, linkedList); HashMap<Integer, HashMap<Integer, Stu>> stuHashMap3 = new HashMap<>(); stuHashMap3.put(1, new HashMap<>()); // 容器 放所有班级的所有学生 3 1-12 2-32 3-50(以前用的是二维数组) HashMap<Integer, List<Stu>> hashMap4 = new HashMap<>(); ArrayList<Stu> stus1 = new ArrayList<>(); stus1.add(new Stu("tom1", 1001)); stus1.add(new Stu("tom2", 1002)); stus1.add(new Stu("tom3", 1003)); hashMap4.put(101, stus1); // System.out.println("size:" + hashMap4.size()); System.out.println(hashMap4); } 2.常用实现类 实现类底层数据结构K/V是否可以为null线程安全HashMap<K,V>哈希，位桶+单向链表+红黑树维护都可以为null不安全LinkedHashMap<K,V>哈希，位桶+双向链表都可以为null不安全TreeMap<K,V>红黑树k不能为null v可以为null不安全HashTable<K,V>哈希k/v都不能为null安全->synchornizedConcurrentHashMap<K,V>哈希k/v都不能为null安全->CAS+synchornized 2.1 HashMap<K,V>

● 底层是hash表（数组+链表+红黑树JDK8之后引入的 ）；hash表中和了数组和链表的优势； ● hash表 哈希表 （字典表，映射表），其内部用到了一种算法 hash算法； ● hash算法： 把一个无限范围的输入映射到一个有限的范围内 也成为数据压缩技术； ● 抽屉原理：100个苹果 9个抽屉（0-8） 尽量分散 减少hash冲突（两个不同的输入映射到同一个输出上 起始就是索引）； ● 数组的查询的时间复杂度是O(1)，链表查询的时间复杂度是O(n)，二叉搜索树（二叉排序树）的查询的时间复杂度是O(log2n)；因此JDK8 引入红黑树的目的是 提升链表的查询性能

1.层级 public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable{} 2.常用构造 1.HashMap();//创建HashMap对象 并初始化容量为16 负载因子: 0.75 2.HashMap(int initialCapacity);//建议 initialCapacity=存储最大元素个数/负载因子+1; 3.源码分析 3.1 常量 final float loadFactor;//负载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f;//默认的负载因子 transient Node<K,V>[] table;//就是HashMap底层的数组/位桶 null int threshold;//阈值 何时再次执行扩容的条件 0 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;//16 初始化容量数据 static final int TREEIFY_THRESHOLD = 8;//维护链表转红黑树的阈值 static final int MIN_TREEIFY_CAPACITY = 64;//使用数组空间: 维护链表转红黑树 static final int MAXIMUM_CAPACITY = 1 << 30;//2的30次幂 static final int UNTREEIFY_THRESHOLD = 6;//维护树转链表 //在resize() 进行旧数组元素转到新的数组中 要对树节点固定位置 高位/低位存储 //无乱是高位还是低位 树节点的数据量<6 这个时候 会在split方法中 将树节点转换成链表维护。 3.2 Node<K,V>

维护底层单向链表。每新增一组数据，其实底层就是一个Node类对象维护。

static class Node<K,V> implements Map.Entry<K,V> { // 成员变量 存放的是hash值 final int hash; // key 对象 final K key; // value对象 V value; // 指向下一个节点 单向链表 Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } } 3.3 put

//计算指定的key的hash数据 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); //高位运算: hash更加随机 减少hash碰撞。 } put方法底层代码简单分析 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { //定义了2个局部变量 一个数Node数组 一个是Node类型p Node<K, V>[] tab; Node<K, V> p; int n, i; // 第一次添加 的时候 数组是null tab = table; // 数组尚未初始化 if (tab == null || (n = tab.length) == 0) { // resize() 内部就是扩容第一次对数组初始化之后 新数组长度是16 tab = resize(); // n代表数组长度 16 hashMap内部数组的长度是2的指数 n = tab.length; } // hash 34116543 % 16 = (0-15) 进行数据压缩（把hash映射为一个索引） i = hash & (n - 1); // 3 // tab是Node[] p = tab[i]; // 当前索引位置 没有元素 if (p == null) { // 直接创建节点对象给数组元素赋值 tab[i] = newNode(hash, key, value, null); } else { //hash碰撞-----> 3种解决方案 Node<K, V> e; K k; //先判断hash值是否一样 再看key对象是否是同一个对象或者 使用equals比较相等也可 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) { // 给局部变量 Node类型的e进行赋值 e = p; } else if (p instanceof TreeNode) { // 如果是树节点 向红黑树中插入节点 e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value); } else { // 添加到链表中 for (int binCount = 0; ; ++binCount) { e = p.next; // 下一个节点 是null if (e == null) { //给p的下一个节点 就是新的节点了 p.next = newNode(hash, key, value, null); // if (binCount >= TREEIFY_THRESHOLD - 1) { // 把链表升级为红黑树 1，链表个数达到8了 2，数组容量达到64了 可以进行树化否则只是扩容 treeifyBin(tab, hash); } break; } //判断链表节点中这个节点的key对象是否和传入进来的key对象一样，如果一样只是重新赋值而已 if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) { // 替换value的值 e.value = value; } afterNodeAccess(e); return oldValue; } } ++modCount; // size> 12 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } 3.4 get get方法底层代码简单分析 final Node<K, V> getNode(int hash, Object key) { // 局部变量 Node<K, V>[] tab; Node<K, V> first, e; int n; K k; // 数组非空并且数组长度大于0 才有元素 tab = table; if (tab != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { // 第一个节点是否是目标节点 ,比较hash相同并且key对象相同 if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))) { return first; } // "java" 3 "3" 3 // first是否有下一个节点 e = first.next; if (e != null) { // 判断是否是树节点 if (first instanceof TreeNode) { return ((TreeNode<K, V>) first).getTreeNode(hash, key); } // 遍历链表 do { //当条件满足 表示在链表中找到节点了 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { return e; } } while ((e = e.next) != null); // 整个链表遍历完了都没找到 } } return null; } 3.5 resize resize方法底层代码简单分析 final Node<K,V>[] resize() { Node<K,V>[] oldTab = table;//获得旧数组 int oldCap = (oldTab == null) ? 0 : oldTab.length;//获得旧数组的old length int oldThr = threshold;//获得旧 阈值 int newCap, newThr = 0;//初始化新容量 新阈值 if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } //不是第一次扩容的时候 会执行下面这个操作 2倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&// 32 oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold 24 } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY;//16 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//12 //第一次执行put操作 第一次扩容 执行else } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//创建一个新的Node数组。 table = newTab; if (oldTab != null) {//不是第一次扩容 需要将旧数组的每个数据都存储到新数组中 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { //要求指定的index下的数据不为null 才会将旧数组的index下数据 存储到新的数组中 //规定数据存储在新数组的位置。 //位置: 1. oldIndex 2.oldIndex+OldCap oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); //split方法中: 也会将树节点进行拆分存储----> 依旧采取高低位 //而且也可能会出现树节点转换成链表节点数据进行维护。 else { // preserve order //对链表数据进行拆分 进行高位/低位存储 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; } 2.2 LinkedHashMap<K,V>

● 是HashMap的子类 ● 底层相当于是在 hash表（数组+单向链表+红黑树）的基础上 添加了一个双向链表 ● 为了保证元素的插入顺序，底层加了个双向链表去维持顺序

1.层级 public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>{} //哈希表和链表实现的Map接口，具有可预测的迭代次序 2.双向链表 static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } } 3.基本使用 private static void testLinkedHashMap() { LinkedHashMap<String, Integer> linkedHashMap = new LinkedHashMap<>(); linkedHashMap.put("a", 100); linkedHashMap.put("a", 200); linkedHashMap.put("c", 100); linkedHashMap.put("1", 100); linkedHashMap.put(null, null); System.out.println(linkedHashMap); //新增顺序与遍历顺序一致。 } 2.3 TreeMap<K,V>

● 底层是红黑树 ● TreeMap的key类型一定要实现 Comparable接口 或者在TreeMap的构造器中提供比较器

1.层级 public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, Serializable{} 2.常用构造 //可以实现对TreeMap的key的数据进行自然排序。 1. TreeMap();//要求TreeMap的key的数据类型必须实现java.lang.Comparable 2. TreeMap(Comparator<? super K> comparator);//使用自定义的外部比较器对集合key进行 排序 3.基本使用 private static void testTreeMap1() { //Collections.synchronizedSortedMap(new TreeMap<>()); 只服务于TreeMap TreeMap<Integer, String> map = new TreeMap<>(Comparator.reverseOrder()); map.put(1, "a"); map.put(10, "a"); map.put(2, "a"); map.put(100, "a"); map.put(12, "a"); map.put(11, null); //key不能为null value可以为null System.out.println(map); //Integer已经实现了Comparable 底层已经提供了排序规则了。 一般底层 都是升序排列。 //需求: 集合类型底层已经实现过Comparable，实现进行降序排列。 自定义外部比较器。java.util.Comparator 使用TreeMap的有参构造 //建议不要使用自定义的类对象作为Map的key。 //TreeMap<UserInfo,Integer> userInfoTreeMap = new TreeMap<>(); //真的想对多个UserInfo的对象进行 排序 直接选择使用List集合 list.sort(Comparator); } 2.4 Hashtable<K,V>

● Hashtable的底层也是哈希表； ● HashMap 是线程不安全的，多线程环境中 会有数据安全问题 ● Hashtable是线程安全的，多线程环境中可以保证数据安全 ● Hashtable性能较低，在多线程高并发情况下 使用ConcurrentHashMap取代 ● Hashtable() 构造一个新的，空的散列表，默认初始容量（11）和负载因子（0.75）。

private static void testHashTable() { Hashtable<Integer,Integer> hashtable = new Hashtable<>(); hashtable.put(1,1); hashtable.put(100,1); hashtable.put(11,1); // hashtable.put(null,null);//不能为null System.out.println(hashtable); //线程安全 //底层的扩容: 初始化容量11 rehash()----> 2倍+1 //旧数组的数据在新数组的索引位置： (e.hash & 0x7FFFFFFF) % newCapacity; } 2.5 ConcurrentHashMap<K,V> public class ConcurrentHashMap<K,V> extends AbstractMap<K,V> implements ConcurrentMap<K,V>, Serializable{} //常用构造 ConcurrentHashMap() 创建一个新的，空的地图与默认的初始表大小(16)