对于不同的数据结构，他们的使用场景是不一样的，map和set这两种数据结构主要用在搜索相关的场景中。学习这些之前我们先来了解一下二叉搜索树，
一、搜索树
1.1概念
二叉搜索树 又称 二叉排序树 ，它或者是一棵空树，或者是具有以下性质的二叉树 :
<1>左子树上所有的值都小于根节点的值；
<2>右子树上所有的值都大于根结点的值；
<3>子树也是一颗二叉搜索树；
1.2 搜索树操作
1.2.1树的查找操作
代码如下：
public TreeNode search(int val) {
TreeNode cur = root;
while (cur != null) {
if (cur.val < val) {
cur = cur.right;
} else if (cur.val > val) {
cur = cur.left;
} else {
return cur;
}
}
return null;
}
1.2.2树的插入操作
与树的查找操作一样，也需要与树的节点进行大小比较，cur的移动方法与查找相同，当我们还需要定义一个parent记录cur的父亲节点，当cur为空时，要插入的值就可以通过与parent节点的值比较大小来确定插入到parent的左节点还是右节点。
public void insert(int val) {
if (root == null) {
root = new TreeNode(val);
return;
}
TreeNode cur = root;
//记录cur的父亲节点
TreeNode parent = null;
while (cur != null) {
parent=cur;
if (val > cur.val) {
cur = cur.right;
} else if(val<cur.val){
cur = cur.left;
}else{
//二叉搜索树不能有两个一样的值
return;
}
}
if(val>parent.val){
parent.right=new TreeNode(val);
}else{
parent.left=new TreeNode(val);
}
}1.2.3树的删除操作
实际上，在情况一和情况三中还分别有三种小情况：
代码如下：
private void removeNode(TreeNode parent, TreeNode cur) {
//情况1：cur的左边为空
if(cur.left==null){
if(cur==root){
//cur是根结点
root=cur.right;
}else if(parent.right==cur){
//parent的右节点是cur
parent.right=cur.right;
}else if(parent.left==cur){
//parent的左节点是cur
parent.left=cur.right;
}
}else if(cur.right==null){//情况2：cur的右边为空
if(cur==root){
//cur是根结点
root=cur.left;
}else if(parent.right==cur){
//parent的右节点是cur
parent.right=cur.left;
}else{
//parent的左节点是cur
parent.left=cur.left;
}
}else{//情况3：cur的左右都不为空
TreeNode rightMin = cur.right;
TreeNode parent2=cur;//记录rightMin的父亲节点
while(rightMin.left!=null){
parent2=rightMin;
rightMin=rightMin.left;
}
//找到右树最小值,将cur.val覆盖,相当于删除了这个节点
cur.val=rightMin.val;
//删除rightMin节点，与情况一方法相同
if(parent2.left==rightMin) {
parent2.left = rightMin.right;
}else{
parent2.right=rightMin.right;
}
}
}1.2.4复杂度分析
最优情况下，二叉搜索树为完全二叉树，其平均比较次数为： O（ logN）
最差情况下，二叉搜索树退化为单支树，其平均比较次数为： O（N）
（当插入的数据有序时，二叉搜索树退化成一颗单分支的树，时间复杂度最大）
1.2.5 和 java 类集的关系
TreeMap 和 TreeSet 即 java 中利用搜索树实现的 Map 和 Set ；实际上用的是红黑树，而红黑树是一棵近似平衡的二叉搜索树，即在二叉搜索树的基础之上 + 颜色以及红黑树性质验证，关于红黑树的内容后序再进行讲解。
二、搜索
2.1概念与场景
Map 和 set 是一种 专门用来进行搜索的容器或者数据结构 ，其搜索的效率与其具体的实例化子类有关 。以前常见的
搜索方式有：
1. 直接遍历 ，时间复杂度为 O(N) ，元素如果比较多效率会非常慢
2. 二分查找 ，时间复杂度为O(logN),但搜索前必须要求序列是 有序 的
上述排序比较适合静态类型的查找，即一般不会对区间进行插入和删除操作了，而现实中的查找比如：
1. 根据姓名查询考试成绩
2. 通讯录，即根据姓名查询联系方式
3. 不重复集合，即需要先搜索关键字是否已经在集合中
可能在查找时进行一些插入和删除的操作，即动态查找，那上述两种方式就不太适合了，本节介绍的 Map和Set是一种适合动态查找的集合容器 。
2.2模型
2.2 模型
一般把搜索的数据称为关键字（ Key ），和关键字对应的称为值（ Value ），将其称之为 Key-value 的键值对，所以模型会有两种：
1. 纯 key 模型 ，比如：
<1>有一个英文词典，快速查找一个单词是否在词典中
<2>快速查找某个名字在不在通讯录中
2. Key-Value 模型 ，比如：
<1>统计文件中每个单词出现的次数，统计结果是每个单词都有与其对应的次数： < 单词，单词出现的次数 >
<2>梁山好汉的江湖绰号：每个好汉都有自己的江湖绰号
而 Map中存储的就是key-value的键值对，Set中只存储了Key 。
三、Map的使用
Map 是一个接口类，该类没有继承自 Collection ，该类中存储的是 <K,V> 结构的键值对，并且 K 一定是唯一的，不可以重复。
3.1Map.Entry<k,v>
Map.Entry<K, V> 是 Map 内部实现的用来存放 <key, value> 键值对映射关系的内部类 ，该内部类中主要提供了<key, value>的获取， value 的设置以及 Key 的比较方式。
！！！Map.Entry<k,v>中没有设置key的方法。
3.1Map的常用方法
注意：
1. Map 是一个 接口 ，不能直接实例化对象 ，如果 要实例化对象只能 实例化其实现类TreeMap或者HashMap
2. Map 中存放键值对的 Key是唯一的，value是可以重复 的
3. 在 TreeMap中插入键值对时，key不能为空 ，否则就会抛 NullPointerException 异常 ， value 可以为空。但是 HashMap的key和value都可以为空 。
4. Map 中的 Key 可以全部分离出来，存储到 Set 中 来进行访问 ( 因为 Key 不能重复 ) 。
5. Map 中的 value 可以全部分离出来，存储在 Collection 的任何一个子集合中 (value 可能有重复 ) 。
6. Map 中键值对的 Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入 。
7. TreeMap 和 HashMap 的区别（HashMap后面会说到）
！！！ entrySet方法中返回的映射关系相当于搜索树的每一个节点 。
四、Set的使用
4.1Set的常用方法
！！！Map不能使用迭代器，只有Set才可以，原因是Map没有实现Iterable接口，但是我们可以使用entrySet方法将Map的键值对放入Set中，在通过Set使用迭代器间接遍历Map。
public static void main(String[] args) {
TreeSet<String> treeSet = new TreeSet<>();
treeSet.add("abcd");
treeSet.add("hello");
treeSet.add("def");
//判断元素是否存在于集合中，存在返回true
System.out.println(treeSet.contains("hello"));
//迭代器遍历
Iterator<String> it = treeSet.iterator();
while(it.hasNext()){
System.out.println(it.next()+" ");
}
}注意：
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可以 。
8. TreeSet 和 HashSet 的区别【 最后会讲到】
五、哈希表
在TreeSet和TreeMap中查找值时，需要通过对关键码的多次比较，而红黑树的高度为logN，因此它们查询的时间复杂度为O(logN)，
如果构造一种存储结构， 通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系 ，那么在查找时通过该函数可以很快 找到该元素。
当向该结构中：
插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功
该方式即为哈希 ( 散列 ) 方法， 哈希方法中使用的转换函数称为哈希 ( 散列 ) 函数，构造出来的结构称为哈希表 (Hash Table)( 或者称散列表 )
5.1哈希冲突
5.2冲突-避免-负载因子调节
由于填入表中的元素个数是无法改变的，因此我们只能通过增加散列表的长度来降低负载因子。
5.3冲突-解决-开散列/哈希桶
开散列法又叫链地址法 ( 开链法 ) ，首先对 关键码集合用散列函数计算散列地址 ，具有 相同地址的关键码归于同一子集合 ，每一个子集合称为一个桶， 各个桶中的元素通过一个单链表链接起来 ，各链表的 头结点存储在哈希表中 。
5.4HashMap代码实现
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 static final double DEFAULT_LOADFACTER = 0.75f;
//数组
public Node[] array = new Node[10];
public int usedSize;
//存放值
public void push(int key,int val){
int index = key % 10;//随便举例的一个哈希函数
//首先要遍历对应链表，看是否已经存在key
Node cur = array[index];
while(cur!=null){
if(cur.key==key){
cur.val=val;
}
cur=cur.next;
}
//说明没有key节点
Node node = new Node(key,val);
node.next=array[index];
array[index]=node;
usedSize++;
//计算负载因子大小
if(doloadFactor()>=DEFAULT_LOADFACTER){
//扩容
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){
int newIndex= cur.key% newArray.length;
Node curN=cur.next;
cur.next=newArray[newIndex];
newArray[newIndex]=cur;
cur=curN;
}
}
//将array指向newArray即可
array=newArray;
}
private double doloadFactor() {
return usedSize*1.0/array.length;
}
public int getVal(int key){
int index = key % 10;
Node cur = array[index];
while(cur!=null){
if(cur.key==key){
return cur.val;
}
cur=cur.next;
}
//没找到
return -1;
}
}
在对散列表进行reSize过程中，可能会遇到下面的问题：
5.5性能分析
实际使用过程中，我们认为哈希表的冲突率是不高的，冲突个数是可控的，也就是每个桶中的链表的长度是一个 常数 ，所以，通常意义下，我们认为 哈希表的插入/删除/查找时间复杂度是O(1) 。
5.6哈希表和Java类集的关系
1. HashMap 和 HashSet 即 java 中 利用哈希表实现 的 Map 和 Set
2. java 中使用的是 哈希桶 方式解决冲突的
3. java 会在冲突链表长度大于一定阈值后，将链表 转变为搜索树 （红黑树）
4. java 中计算哈希值实际上是调用的类的 hashCode 方法，进行 key 的相等性比较是调用 key 的 equals 方法。所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值 ，必须覆写 hashCode 和 equals 方法 ，而且要做到 equals 相等的对象， hashCode 一定是一致的。