mapset
一，搜索树
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，最优的情况下，二叉搜索树为完全二叉树，平均比较次数为O（logn）
2，最差情况下，二叉搜索树退化为单支树，平均比较次数为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中只存储了Key
3，Map的相关使用和说明
1，Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap
2，Map当中存放的键值对的Key是唯一的，value是可以重复的
（如果存放了一样的Key的值，则编译器会更新value的值，只存放最后一个重复的键值对）
3，在TreeMap中插入键值对时，Key不可以为空，否则会抛出NullPointExcetion异常，value可以为空，但是HashMap的Key和value都可以为空
4，Map中的Key可以全部分离出来，存储到Set中来进行访问（因为Key不能重复）
5，Map中的value可以全部分离出来，存储在Collection的任何一个子集合中（value可能有重复）
6，Map中的value是可以进行修改的，但是Key不可以直接修改，如果要修改Key只能将该Key删除掉，然后再来重新插入。
HashMap和TreeMap的区别
一句话区别：
HashMap：无序，基于哈希表，追求 O(1) 极速查询。
TreeMap：按键排序，基于红黑树，用于 O(log n) 有序遍历和范围查找。
关键对比：
顺序：HashMap 无序；TreeMap 按键自然顺序或自定义比较器排序。
null 键：HashMap 允许一个 null 键；TreeMap 完全不允许 null 键。
判重标准：HashMap 靠 hashCode 和 equals；TreeMap 靠 compareTo 或 Comparator。
性能：HashMap 增删查平均 O(1)；TreeMap 稳定 O(log n)。
简单选择：
只关心存取速度，不管顺序，用 HashMap。
需要按键遍历、范围查找（如找比某值大/小的键），用 TreeMap。
4，Set相关的使用和说明
1，Set是继承Collection的一个接口类
2，Set只存储了key，并且要求key一定要唯一
3，TreeSet的底层是用Map来实现的，其使用 Key与Object的一个默认对象作为键值插入到Map中
4，Set最大的功能就是对集合中的元素去重
5，实现Set接口的常用类有TreeSet和HashSet，还有⼀个LinkedHashSet，LinkedHashSet是在 HashSet的基础上维护了⼀个双向链表来记录元素的插入次序
6，Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入
7，TreeSet中不能插入null的key，HashSet可以。
TreeSet和HashSet的区别
HashSet：无序，为了快。
TreeSet：有序，为了排序和范围查找。
核心对比
底层：HashSet用哈希表，TreeSet用红黑树。
判重：HashSet靠hashCode/equals；TreeSet靠compareTo/Comparator。
null：HashSet允许一个null；TreeSet完全不允许。
性能：HashSet平均O(1)；TreeSet稳定O(log n)。
怎么选？
只关心唯一性，追求极致速度 → 选HashSet。
需要排序、范围查找、取首尾最大最小值 → 选TreeSet。
五，哈希表
概念
哈希表核心思想： 用空间换时间，通过键直接算出存储地址，实现快速增删查。
四个关键概念：
哈希函数：把键算成数组索引的工具。
哈希冲突：不同键算出相同索引，不可避免。
解决冲突：链地址法（Java标准做法，拉链表/红黑树）或开放地址法（向后找空位）。
扩容（重哈希）：元素太多冲突变多时，扩大数组并重新排布所有元素。Java默认在装到75%时触发。
实现
根据Key的值找到桶的位置
index位置是一个链表
1，遍历链表中是否存在相同的Key，存在那就需要更新Key
2，如果不存在，则进行尾插或者头插
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;i<array.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，数组长度大于等于64
2，链表的长度超过了8
两个条件均需满足
泛型哈希表的实现
public class HashBuck<K,V> { static class Node<K,V>{ public K key; public V val; public Node<K,V> next; public Node(K key,V val){ this.key = key; this.val = val; } } //需要进行强转 public Node<K,V>[] array = (Node<K,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; Node<K,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; } Node<K,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; Node<K,V> cur = array[index]; while(cur != null){ if(cur.key.equals(key)){ return cur.val; } cur = cur.next; } return null; } }HashSet的底层也是HashMap
hashCode一样（说明位置一样，但是在这个位置上可以有很多不同的值），equals不一定一样
equals一样，hashCode一定是一样的