【目标】掌握 Map/Set 及实际实现类 HashMap/TreeMap/HashSet/TreeSet 的使用掌握 HashMap 和 HashSet 背后的数据结构哈希表的原理和简单实现1.二叉搜索树大家只需要直到二叉搜索树是如何即可至于Map和Set的底层实现——红黑树大家现在不需要了解只需要知道红黑树是基于二叉搜索树演变而来的1.1 二叉搜索树的概念1.2 二叉搜索树的实现1.2.1 查找二叉搜索树的查找很简单其思想与二分查找一致。1.2.2 插入二叉搜索树的插入其实和查找差不多都是要先找到指定位置然后再进行插入。提醒在插入时遇到已有的相同数据操作不唯一直接返回、覆盖......这里的演示过程则默认为不会插入相同的数据毕竟具体要怎样做还要看业务需求这里了解底层原理即可1.2.3 删除删除这个节点时其实同上述思维一样并没有那么复杂在这里进行演示。1.2.4 代码实现public class BinarySearchTree { static class TreeNode{ public int val; public TreeNode left; public TreeNode right; public TreeNode(int val) { this.val val; } } TreeNode root; public void insert(int key) { TreeNode node new TreeNode(key); if(root null) { root node; return; } TreeNode cur root; TreeNode parent null; while(cur ! null) { parent cur; if(cur.val key) { cur cur.left; }else if(cur.val key) { cur cur.right; }else { return; } } if(parent.val key) { parent.right node; }else { parent.left node; } } public TreeNode search(int key) { if(root null) { return null; } TreeNode cur root; while(cur ! null) { if(cur.val key) { cur cur.right; }else if(cur.val key){ cur cur.left; }else { return cur; } } return null; } public void remove(int vall) { TreeNode cur root; TreeNode parent null;//表示的是待删除结点的双亲结点 while(cur ! null) { if(cur.val vall) { //去右边找 cur cur.right; } else if (cur.val vall) { //去左边找 cur cur.left; } else { //表示的cur就是要删除的节点 removeNode(parent,cur); } } } public void removeNode(TreeNode parent, TreeNode cur) { if(cur.left null) { if(cur root) { root cur.right; } else { if(parent.right cur) { parent.right cur.right; } else if(parent.left cur) { parent.left cur.right; } } } else if (cur.right null) { if(cur root) { root cur.left; } else { if(parent.left cur) { parent.left cur.left; } else if (parent.right cur) { parent.right cur.left; } } } else { TreeNode tp cur; TreeNode t cur.right; while(t.left ! null) { tp t; t t.left; } cur.val t.val; if(tp.right t) { tp.right t.right; } else { tp.left t.right; } } } }1.3 二叉搜索树的性能分析2.哈希表2.1 哈希表的简述顺序结构以及平衡树中元素关键码与其存储位置之间没有对应的关系因此在查找一个元素时必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)平衡树中为树的高度即O(log₂N)搜索的效率取决于搜索过程中元素的比较次数。理想的搜索方法可以不经过任何比较一次直接从表中得到要搜索的元素。如果构造一种存储结构通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系那么在查找时通过该函数可以很快找到该元素。当向该结构中插入元素根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放搜索元素对元素的关键码进行同样的计算把求得的函数值当做元素的存储位置在结构中按此位置取元素比较若关键码相等则搜索成功该方式就是哈希方法散列方法其中用于计算关键码的元素为哈希函数散列函数构造出来的结构称为哈希表散列表2.2 哈希表的结构哈希表的底层是用数组实现的接下来通过演示来讲解哈希表的结构2.3 冲突2.3.1 概念对于两个数据元素 m 和 n 如果这两者的关键码通过哈希运算得到的 index 相同那么这时候就会发生哈希冲突哈希碰撞把关键码不同但是计算出的 index 值相同的两个数据称为同义词2.3.2 设计、避免冲突1.哈希函数的设计原则哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址时其值域必须在0到m-1之间哈希函数计算出来的地址能均匀分布在整个空间中哈希函数应该比较简单2.由于哈希函数的设计原则太过理论它仅仅是在认为这些通过关键码算出来的index不同 的情况下设计的然而这种理论化的设计原则在遇到冲突时恰恰就出现了问题而我们能做的就是降低冲突率3.降低冲突率的方法1. 直接定制法--(常用)取关键字的某个线性函数为散列地址hash(key) a * key b;2. 除留余数法--(常用)设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数按照哈希函数hash(key) key % p将关键码转换成哈希地址。4.需要注意的是哈希函数无论怎样设计设计的再巧妙也只是能够降低冲突率并不能避免冲突的出现2.3.3 负载因子的调节重点散列表的负载因子定义为α 填入表中的元素个数 / 散列表的长度也就是数组的长度α是散列表装满程度的标志因子。由于表长是定值α与“填入表中的元素个数”成正比所以α越大表明填入表中的元素越多产生冲突的可能性就越大α越小标明填入表中的元素越少产生冲突的可能性就越小。实际上散列表的平均查找长度是载荷因子α的函数只是不同处理冲突的方法有不同的函数。对于开放定址法荷载因子是特别重要因素应严格限制在0.7-0.8以下。超过0.8查表时的CPU缓存不命中cache missing按照指数曲线上升。因此一些采用开放定址法的hash库如Java的系统库限制了荷载因子为0.75超过此值将扩容散列表。这里说的并不是HashMap和HashSet它俩的底层实现使用的开散列的方式2.3.4 冲突的解决重点冲突的解决有两种方式闭散列 和 开散列2.3.4.1 闭散列闭散列开放定址法当发生哈希冲突时如果哈希表未被装满说明哈希表中仍然有空位置那么可以把key存放到冲突位置的“下一个位置”去那么“下一个位置”应该如何定义呢1.线性探测线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。所谓向右探测如果在探测到哈希表的最后一个元素仍然没有找到空位置那么就会从头开始相当于是一个环。从公式上可以体会2.二次探测线性探测的局限是产生冲突的数据都堆到一起。为了避免该问题找到下一个位置的方法就可以改进为二次探测同样的如果二次探测也遇到了单方向探测不到的情况那么也会进行从头开始就相当于是一个环2.3.4.2 开散列重点开散列又叫做链地址法首先根据关键码计算出index而在遇到冲突时具有相同index的不同数据算作一个集合每一个集合就相当于一个桶因此也叫做哈希桶。每一个哈希桶中的元素都是通过单链表连接起来的各链表的头节点存储在哈希表中注意哈希表中存储的是哈希桶中第一个元素的地址而不是第一个元素哈希桶的代码实现import java.util.Arrays; public class HashBuck { private static class Node { //这个Node是每一个节点 public int key; public int val; public Node next;//下一个节点的地址 public Node(int key, int val) { this.key key; this.val val; } } private int usedSize 0; private int capacity 10; private Node[] array new Node[capacity]; //最初哈希桶的数组,里面的类型是Node类型 //注意这里已经创建完了最初的数组但是这个数组是容器并不是对象 private static final double DEFAULT_LOADFACTOR 0.75f;//负载因子一旦超过这个数就要进行扩容 public void push(int key,int val) { int index key % array.length;//key节点要放入数组的数组下标 Node node new Node(key,val);//创建新节点 Node cur array[index]; while(cur ! null) { if(cur.key key) { cur.val val; return;//如果替换的话不需要进行usedSize } cur cur.next; } node.next array[index]; array[index] node; this.usedSize; //但是创建完成之后要看负载因子了,如果大于了负载因子那么就进行扩容 if(1.0 * this.usedSize / this.capacity DEFAULT_LOADFACTOR) { resize(); } } private void resize() { //表示要进行扩容 //但是扩容并不能简单的扩容还要对原数组的每一个节点进行遍历 Node[] newArray new Node[array.length * 2]; for (int i 0; i array.length; i) { Node cur array[i]; while(cur ! null) { Node next cur.next;//要先存旧节点 int newIndex cur.key % newArray.length;//某个节点放入新数组的下标 //但是这个节点cur已经创建好了,所以不需要再进行创建 cur.next newArray[newIndex]; newArray[newIndex] cur; cur next; } } this.array newArray; this.capacity this.array.length; } public int getVal(int key) { //根据k来抽取val先要判断有没有这个元素 int index key % array.length; Node cur array[index]; while(cur ! null) { if(cur.key key) return cur.val; cur cur.next; } return -1;//表示没有这一个元素 } }2.4 哈希表的性能分析虽然哈希表的使用过程中存在冲突但是在实际的使用过程中哈希表的冲突率是不高的冲突的个数是可控的。也就是说每个桶中的链表的长度是一个常数所以在通常情况下我们认为哈希表的查询/插入/删除的时间复杂度都是O(1)3.Set集合Set是Java中的接口之一而Set的具体实现有两种。一种是TreeSet其底层是红黑树另一种是HashSet其底层是哈希表并且该哈希表为避免冲突采取的方式是开散列链地址法。3.1 常用的方法方法作用返回值add(E e)添加元素已存在则失败booleanremove(Object o)删除指定元素booleancontains(Object o)判断是否包含booleansize()元素个数intisEmpty()是否为空booleanclear()清空void另外多说一句由于TreeSet的底层是红黑树也就是说TreeSet的存储是有序的那么根据这一特征TreeSet就有独属于自己的方法如下方法作用first()最小元素last()最大元素这里不给出更多的方法等到后续做项目时可能会用到那么再进行查阅。在实际工作中并不要求我们对每个方法都进行掌握甚至倒背如流。对于常用的方法多用几遍就记住了在日常的练习中、比如LeetCode等平台上也可以锻炼自己而对于不常用的方法等要用到的时候再去查询也不迟3.2 HashSet和TreeSet的取用由于HashSet的底层是哈希表也就是说操作数据的时候时间复杂度为O(1)那么就很快了。如果在一般操作中不要求数据有序那么我们大概率会选择使用HashSet但是如果我们要求了数据有序那么就会使用TreeSet。具体的见下对比维度HashSetTreeSet底层结构数组 链表/红黑树哈希表底层是 HashMap红黑树自平衡二叉查找树底层是 TreeMap元素的顺序❌无序遍历顺序不可预测✅自动排序自然顺序或 Comparator性能增删查平均O(1)极快O(log n)相对慢能否存 null✅ 可以一个null 元素❌ 不行null 无法比较会抛 NPE对参数key是自定义类的要求重写hashCodeequals必须实现Comparable或传Comparator范围查询能力❌ 无只能全表遍历或 contains 判断✅有headSet/tailSet/subSet等另外对于去重一事在Set中无论是TreeSet还是HashSet对于插入新的已有的数据时Java底层进行的操作是“什么都不做原数据不变”那么就一定会做到去重的效果。而如果只是进行去重操作的话更推荐使用HashSet因为其时间复杂度为O(1)相较于TreeSet它更快一点4.Map映射所谓映射即是一一对应的关系那么也就是说在操作数据到Map中时数据是以key—value的键值对形式操作的。Map是Java中的接口之一而Map的具体实现有两种。一种是TreeMap其底层是红黑树另一种是HashMap其底层是哈希表并且该哈希表为避免冲突采取的方式是开散列链地址法。4.1 常用的方法TreeMap特有的方法不再给出有兴趣的自己去学习使用。方法作用返回值put(K k, V v)存入键值对key 已存在则覆盖 value旧 value无则 nullget(Object k)按 key 取 value 的值value无则 nullremove(Object k)按 key 删除 key—value 键值对被删的 value无则 nullcontainsKey(Object k)判断是否含某 keybooleansize()键值对数量int这里的key、value都是实际存入的数据而在使用的过程中我们通常是根据key来对value进行操作的。有的讲解会说这里key是标识作用这种说法其实没有太大意义就算知道了他是标识value的作用又如何在实际的使用过程中我们只会根据具体的效果选择使用的方法等不会执着于“标识”这种说法。key 映射到 value是人类对 Map 接口行为的建模语言。计算机内部没有映射这个实体具体实现依赖各实现类的物理结构和算法HashMap数组 链表/红黑树靠 hash 定位 equals 比较TreeMap红黑树靠 compareTo/Comparator 比较大小走树查找无论哪种实现方法能返回 value都是因为在各自的物理结构上定位到了 key 相等的节点。映射关系不是机器的内在属性而是人类对这套机制的命名。另外Set的构造其实是调用的Map的构造方法。而Set的key其实就是Map的key至于Set的value其实是占位符 PRESENT没有实际作用。在这里希望大家还是忘记key的标识作用这种说法这只是一种说法具体的效果是我们根据不同的方法进行实现的。4.2 HashMap和TreeMap的取用对比维度HashMapTreeMap底层结构数组 链表/红黑树哈希表红黑树自平衡二叉查找树key 的顺序❌ 无序遍历顺序不可预测✅ 自动按 key 排序自然顺序或 Comparator性能增删查平均 O(1)极快O(log n)相对慢key 能否为 null✅ 可以一个 null key❌ 不行null 无法比较会抛 NPE对参数是自定义类的要求重写hashCodeequals必须实现Comparable或传Comparator范围查询能力❌ 无只能全表遍历✅ 有headMap/tailMap/subMap等具体的选取方法和Set一样有序用TreeMap无序用HashMap......5.常用数据结构图