文章目录一、Key 与 Key-Value数据模型二、Set1.Set 常用 API2.Set 的特点3.HashSet 与 TreeSet二、Map1.Map 常用 API2.Map的特点3.HashMap1实现原理2put(K key, V value) 和 get(key)3HashMap的扩容机制5.HashMap 与 TreeMap一、Key 与 Key-Value数据模型Set 对应纯 Key 模型Map 对应 Key-Value 模型。在 Java 集合框架中两者都是接口需要通过具体实现类 来使用Set纯 Key 模型只存储 Key且 Key 不可重复。MapKey-Value 模型存储一对映射关系Key 不可重复Value 可重复。二、SetSet 是继承自 Collection 的一个接口类这意味着它拥有 Collection 的所有方法同时有自己的特性约束。Set 的核心特征是元素不可重复向 Set 中添加已存在的元素会被直接忽略1.Set 常用 API方法解释boolean add(E e)添加元素但重复元素不会被添加成功返回 falsevoid clear()清空集合中的所有元素boolean contains(Object o)判断元素 o 是否在集合中IteratorE iterator()返回迭代器用于遍历集合boolean remove(Object o)删除集合中的元素 o删除成功返回 trueint size()返回 Set 中元素的个数boolean isEmpty()检测 Set 是否为空空返回 true否则返回 falseObject[] toArray()将 Set 中的元素转换为数组返回boolean containsAll(Collection? c)判断集合 c 中的元素是否在 Set 中全部存在boolean addAll(Collection? extends E c)将集合 c 中的元素添加到 Set 中可以达到去重的效果SetStringsetnewHashSet();set.add(Java);set.add(Python);set.add(Java);// 重复元素添加失败返回 falseSystem.out.println(set);// [Java, Python]System.out.println(set.size());// 2System.out.println(set.contains(C));// false// 遍历方式一增强 forfor(Strings:set){System.out.println(s);}// 遍历方式二迭代器IteratorStringitset.iterator();while(it.hasNext()){System.out.println(it.next());}2.Set 的特点Set 中只存储了 Key并且要求 Key 一定要唯一不能重复Set 最大的功能就是对集合中的元素进行去重Set 中的 Key 不能修改如果要修改只能先将原来的删除掉然后再重新插入所有常用 Set 实现类均非线程安全可用 Collections.synchronizedSet() 包装或使用 ConcurrentSkipListSet。3.HashSet 与 TreeSet特性HashSetTreeSet底层结构HashMap只用 keyvalue 为固定常量TreeMap只用 key增删查时间复杂度O(1)O(log n)元素顺序无序有序自然顺序或比较器null 支持允许一个 null 元素不允许 null会抛 NullPointerException比较要求需重写 hashCode() 和 equals()元素必须实现 Comparable 或传入 Comparator二、MapMap 是一个接口类它没有继承自 Collection 接口这与 List、Set 不同。Map 中存储的是 K, V 结构的键值对并且 Key 一定是唯一的不能重复。当使用 put 方法放入相同的 key 时新的 value 会覆盖旧的 value1.Map 常用 API以下是 Map 接口中最核心的方法无论使用 HashMap 还是 TreeMap这些 API 都是通用的方法解释V get(Object key)返回 key 对应的 value若 key 不存在则返回 nullV getOrDefault(Object key, V defaultValue)返回 key 对应的 value若 key 不存在则返回默认值 defaultValueV put(K key, V value)设置 key 对应的 value若 key 已存在则覆盖并返回旧值V remove(Object key)删除 key 对应的映射关系返回被删除的 valueSetK keySet()返回所有 key 的不重复集合因为 key 唯一CollectionV values()返回所有 value 的可重复集合value 可能重复SetMap.EntryK, V entrySet()返回所有的 key-value 映射关系boolean containsKey(Object key)判断是否包含指定的 keyboolean containsValue(Object value)判断是否包含指定的 valueMapString,IntegermapnewHashMap();map.put(Java,1);map.put(Python,2);map.put(C,3);System.out.println(map.get(Java));// 1System.out.println(map.getOrDefault(Go,0));// 0System.out.println(map.containsKey(Python));// true// 遍历方式一keySetfor(Stringkey:map.keySet()){System.out.println(key - map.get(key));}// 遍历方式二entrySet推荐效率最高for(Map.EntryString,Integerentry:map.entrySet()){System.out.println(entry.getKey() - entry.getValue());}// 遍历方式三forEachJDK 8map.forEach((k,v)-System.out.println(k - v));2.Map的特点Map是一个接口不能直接实例化对象如果要实例化对象只能实例化其实现类 TreeMap 或者 HashMapMap中存放键值对的 Key 是唯一的value 是可以重复的在 TreeMap 中插入键值对时key 不能为空否则就会抛NullPointerException 异常value 可以为空。但是 HashMap 的 key和 value 都可以为空。Map 中的 Key 可以全部分离出来存储到 Set 中来进行访问因为 Key 不能重复。Map中的 value 可以全部分离出来存储在Collection的任何一个子集合中value可能有重复。Map 中键值对的 Key 不能直接修改value 可以修改如果要修改key只能先将该 key 删除掉然后再来进行重新插入。3.HashMap1实现原理HashMap 是 Java 中最常用的键值对集合它基于哈希表实现通过“数组 链表 红黑树”的组合结构在大多数情况下提供 O(1) 的增删查性能。JDK 8 的 HashMap 采用 数组 链表 红黑树 的复合结构核心是一个 NodeK,V[] table 数组// HashMap 核心字段transientNodeK,V[]table;// 哈希表数组transientintsize;// 键值对数量intthreshold;// 扩容阈值 capacity * loadFactorfinalfloatloadFactor;// 负载因子默认 0.75// 链表节点结构staticclassNodeK,V{finalinthash;finalKkey;Vvalue;NodeK,Vnext;// 指向下一个节点形成链表}// 红黑树节点结构继承自 LinkedHashMap.Entry后者继承自 NodestaticfinalclassTreeNodeK,VextendsLinkedHashMap.EntryK,V{TreeNodeK,Vparent;TreeNodeK,Vleft;TreeNodeK,Vright;TreeNodeK,Vprev;booleanred;}2put(K key, V value) 和 get(key)put(K key, V value) 用于插入键值对get(key)用于获取键值对① 计算哈希值HashMap 通过 key.hashCode() 计算哈希值并进行扰动处理来降低哈希冲突。// JDK 8 的 hash 方法staticfinalinthash(Objectkey){inth;return(keynull)?0:(hkey.hashCode())^(h16);}为什么要 h ^ (h 16)将哈希值的高 16 位与低 16 位进行异或让高位特征也参与到低位中使得哈希值更均匀地分布到数组的各个桶位。② 定位数组索引// n 是数组长度2 的幂等价于 h % n但位运算效率更高intindex(n-1)hash;//示例 key.hashCode() 10101010 11110000 00001111 01010101 (二进制) h 16 00000000 00000000 10101010 11110000 h ^ (h 16) 10101010 11110000 10100101 10100101 → 最终的 hash 值 n 16 (数组长度) n - 1 15 00000000 00000000 00000000 00001111 index hash 15 00000000 00000000 00000000 00000101 → 5③ 对于put(K key, V value)来说有以下流程计算 key 的 hash 值判断 table 是否已初始化如果未初始化则调用 resize() 扩容初始化若已经初始化则通过 (n - 1) hash 计算索引 i判断 table[i] 是否为空若为空则直接创建 Node 放入数组不为空则发生哈希冲突。对于哈希冲突有下面的两种是红黑树则调用 putTreeVal() 插入是链表如果链表长度 ≥ 8则转换红黑树检查元素数量是否超过阈值如果超过则执行扩容④ 对于get(key)来说有以下流程计算 key 的 hash 值判断 table 是否已初始化如果未初始化则调用 resize() 扩容初始化若已经初始化则通过 (n - 1) hash 计算索引 i判断当前桶是链表还是红黑树如果是红黑树就调用 getTreeNode() 在红黑树中查找如果是链表就遍历链表逐个比较 key。3HashMap的扩容机制当元素数量超过 容量 × 负载因子默认 16 × 0.75 12时HashMap 会进行扩容有以下步骤容量翻倍newCap oldCap 12 倍。阈值翻倍newThr oldThr 1。创建新数组NodeK,V[] newTable new Node[newCap]。数据迁移遍历旧数组的每个桶将其中的元素重新哈希到新数组中。JDK 8 利用“数组长度为 2 的幂”这一特性对迁移过程进行了极大优化对于旧数组索引 j 处的元素在新数组中只有两种落点判断方法(e.hash oldCap) 0 ? j : j oldCap原位置 j高位为 0j oldCap高位为 15.HashMap 与 TreeMap特性HashMapTreeMap底层结构哈希表数组链表红黑树红黑树增删查时间复杂度O(1)O(log n)元素顺序无序按键的自然顺序或比较器排序null 支持key 和 value 均可为 nullkey 不能为 nullvalue 可以为 null比较要求自定义对象需重写 hashCode() 和 equals()key 必须实现 Comparable 或传入 Comparator