一搜索树1.1 概念二叉搜索树又称为二叉排序树它或者是⼀棵空树或者是具有以下性质的二叉树1每棵子树中根的左边都比根小根的右边都比根大2它的左右子树也分别为二叉搜索树把二叉搜索树进行中序遍历之后是有序的1.2 查找public boolean search(int val){ if(root null){ return false; } TreeNode cur root; while(cur ! null){ if(cur.val val){ cur cur.left; }else if(cur.val val){ cur cur.right; }else{ return true; } } return false; }1.3 插入二叉搜索树在插入数据的时候一定是往叶子节点来插入的如果要插入的值和搜索二叉树中某个节点的值一样则不进行存储//插入 public void insert(int val){ if(root null){ root new TreeNode(val); } TreeNode cur root; TreeNode parent null; while(cur ! null){ if(cur.val val){ parent cur; cur cur.left; }else if(cur.val val){ parent cur; cur cur.right; }else{ return; } } TreeNode newNode new TreeNode(val); if(parent.val val){ parent.left newNode; }else{ parent.right newNode; } }1.4 删除操作private void removeNode(TreeNode cur,TreeNode parent){ if(cur.left null){ if(cur root){ root cur.right; }else if(cur parent.left){ parent.left cur.right; }else{ parent.right cur.right; } }else if(cur.right null){ if(cur root){ root cur.left; }else if(cur parent.left){ parent.left cur.left; }else{ parent.right cur.left; } }else{ //替换删除在右树当中找到最小值这个最小值在右树的最左边并且没有左子树 // 在左子树中找最大值则最大值在左树的最右边 //将这个最小值/最大值和要删除的元素互换位置之后删除这个元素就变成了 //以上几种情况中的其一 TreeNode target cur.right; TreeNode targetParent cur; while(target.left ! null){ targetParent target; target target.left; } cur.val target.val; if(target targetParent.right){ targetParent.right target.right; } targetParent.left target.right; } }插入和删除都必须先查找查找效率代表了二叉搜索树中各个操作的性能对有n个节点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是节点在二叉搜索树的深度的函数即节点越深则比较次数越多。但是对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树1最优的情况下二叉搜索树为完全二叉树平均比较次数为Ologn2最差情况下二叉搜索树退化为单支树平均比较次数为N二搜索2.1 概念和场景Map和set是一种专门用来搜索的容器或者 数据结构其搜索的效率与其具体的实例化子类有关。以前常见的搜索方式有1. 直接遍历时间复杂度为O(N)元素如果比较多效率会非常慢2. 二分查找时间复杂度为,但搜索前必须要求序列是有序的 上述排序比较适合静态类型的查找即⼀般不会对区间进行插入和删除操作了而现实中的查找比如1. 根据姓名查询考试成绩2. 通讯录即根据姓名查询联系方式3. 不重复集合即需要先搜索关键字是否已经在集合中可能在查找时进行⼀些插入和删除的操作即动态查找那上述两种方式就不太适合了而Map和Set是⼀种适合动态查找的集合容器2.2 模型⼀般把搜索的数据称为关键字Key和关键字对应的称为值Value将其称之为Key-value的键值对所以模型会有两种1.纯key模型比如有⼀个英文词典快速查找⼀个单词是否在词典中快速查找某个名字在不在通讯录中2.Key-Value模型比如统计文件中每个单词出现的次数统计结果是每个单词都有与其对应的次数梁山好汉的江湖绰号每个好汉都有自己的江湖绰号3. 而Map中存储的就是key-value的键值对Set中只存储了Key3Map的相关使用和说明1Map是一个接口不能直接实例化对象如果要实例化对象只能实例化其实现类TreeMap或者HashMap2Map当中存放的键值对的Key是唯一的value是可以重复的如果存放了一样的Key的值则编译器会更新value的值只存放最后一个重复的键值对3在TreeMap中插入键值对时Key不可以为空否则会抛出NullPointExcetion异常value可以为空但是HashMap的Key和value都可以为空4Map中的Key可以全部分离出来存储到Set中来进行访问因为Key不能重复5Map中的value可以全部分离出来存储在Collection的任何一个子集合中value可能有重复6Map中的value是可以进行修改的但是Key不可以直接修改如果要修改Key只能将该Key删除掉然后再来重新插入。HashMap和TreeMap的区别一句话区别HashMap无序基于哈希表追求 O(1) 极速查询。TreeMap按键排序基于红黑树用于 O(log n) 有序遍历和范围查找。关键对比顺序HashMap 无序TreeMap 按键自然顺序或自定义比较器排序。null 键HashMap 允许一个 null 键TreeMap 完全不允许 null 键。判重标准HashMap 靠 hashCode 和 equalsTreeMap 靠 compareTo 或 Comparator。性能HashMap 增删查平均 O(1)TreeMap 稳定 O(log n)。简单选择只关心存取速度不管顺序用 HashMap。需要按键遍历、范围查找如找比某值大/小的键用 TreeMap。4Set相关的使用和说明1Set是继承Collection的一个接口类2Set只存储了key并且要求key一定要唯一3TreeSet的底层是用Map来实现的其使用 Key与Object的一个默认对象作为键值插入到Map中4Set最大的功能就是对集合中的元素去重5实现Set接口的常用类有TreeSet和HashSet还有⼀个LinkedHashSetLinkedHashSet是在 HashSet的基础上维护了⼀个双向链表来记录元素的插入次序6Set中的Key不能修改如果要修改先将原来的删除掉然后再重新插入7TreeSet中不能插入null的keyHashSet可以。TreeSet和HashSet的区别HashSet无序为了快。TreeSet有序为了排序和范围查找。核心对比底层HashSet用哈希表TreeSet用红黑树。判重HashSet靠hashCode/equalsTreeSet靠compareTo/Comparator。nullHashSet允许一个nullTreeSet完全不允许。性能HashSet平均O(1)TreeSet稳定O(log n)。怎么选只关心唯一性追求极致速度 → 选HashSet。需要排序、范围查找、取首尾最大最小值 → 选TreeSet。五哈希表概念哈希表核心思想 用空间换时间通过键直接算出存储地址实现快速增删查。四个关键概念哈希函数把键算成数组索引的工具。哈希冲突不同键算出相同索引不可避免。解决冲突链地址法Java标准做法拉链表/红黑树或开放地址法向后找空位。扩容重哈希元素太多冲突变多时扩大数组并重新排布所有元素。Java默认在装到75%时触发。实现根据Key的值找到桶的位置index位置是一个链表1遍历链表中是否存在相同的Key存在那就需要更新Key2如果不存在则进行尾插或者头插public class HashBuck { static class Node{ public int key; public int val; public Node next; public Node(int key, int val) { this.key key; this.val val; } } public Node[] array; public int usedSize; public double load_factor 0.75; public HashBuck(){ array new Node[10]; } public void put(int key,int val){ int index key % array.length; Node cur array[index]; while(cur ! null){ if(cur.key key){ cur.val val; return; } cur cur.next; } //头插法头插法和尾插法都可以 Node newNode new Node(key,val); newNode.next array[index]; array[index] newNode; this.usedSize; //检查负载因子 if(doFactor() 0.75){ //扩容 grow(); } } private void grow(){ Node[] newArray new Node[2* array.length]; for(int i 0;iarray.length;i){ Node cur array[i]; while(cur ! null){ int newIndex cur.key % newArray.length; Node curNext cur.next; cur.next newArray[newIndex]; newArray[newIndex] cur; cur curNext; } } this.array newArray; } private double doFactor(){ return usedSize*1.0/array.length; } public int get(int key){ int index key % array.length; Node cur array[index]; while(cur ! null){ if(cur.key key){ return cur.val; } cur cur.next; } return -1; } }链表在一定程度上会变成红黑树条件为1数组长度大于等于642链表的长度超过了8两个条件均需满足泛型哈希表的实现public class HashBuckK,V { static class NodeK,V{ public K key; public V val; public NodeK,V next; public Node(K key,V val){ this.key key; this.val val; } } //需要进行强转 public NodeK,V[] array (NodeK,V[])new Node[10]; public int usedSize; public double load_factor 0.75; public void put(K key,V val){ int hash key.hashCode(); int index hash % array.length; NodeK,V cur array[index]; while(cur ! null){ //引用类型不用要用equals // if(cur.key key){ // cur.val val; // return; // } if(cur.key.equals(key)){ cur.val val; return; } cur cur.next; } NodeK,V newNode new Node(key,val); newNode.next array[index]; array[index] newNode; this.usedSize; //检查负载因子 } public V get(K key){ int hash key.hashCode(); int index hash % array.length; NodeK,V cur array[index]; while(cur ! null){ if(cur.key.equals(key)){ return cur.val; } cur cur.next; } return null; } }HashSet的底层也是HashMaphashCode一样说明位置一样但是在这个位置上可以有很多不同的值equals不一定一样equals一样hashCode一定是一样的