目录
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值若它的右子树不为空，则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树
例如这棵树便是一颗二叉搜索树
二叉排序树的查找操作利用了二叉排序树的特性来进行查找：左子树 < 根节点 < 右子树
通过判断当前结点与查找结点之间数值的关系来对二叉排序树进行查找操作
插入操作分成空树与非空两种情况：
2. 如果树不是空树，按照查找逻辑确定插入位置，插入新结点
<2.1>被删除结点z只有一棵左子树，删除关键字为45的结点。
<2.2>被删除结点z只有一棵右子树，如删除关键字为78的结点。
<3>被删除结点z有左、右两棵子树，如删除结点78。
最优情况下，二叉搜索树为完全二叉树，其平均比较次数为： logN
最差情况下，二叉搜索树退化为单支树，其平均比较次数为： N / 2
1. 直接遍历，时间复杂度为 O(N) ，元素如果比较多效率会非常慢2. 二分查找，时间复杂度为O（log N）,但搜索前必须要求序列是有序的
上述排序比较适合静态类型的查找，即一般不会对区间进行插入和删除操作了，而现实中的查找比如：
有一个英文词典，快速查找一个单词是否在词典中快速查找某个名字在不在通讯录中
2. Key-Value 模型，比如：
统计文件中每个单词出现的次数，统计结果是每个单词都有与其对应的次数： < 单词，单词出现的次数 >梁山好汉的江湖绰号：每个好汉都有自己的江湖绰号
而Map中存储的就是key-value的键值对，Set中只存储了Key。
注意：Map.Entry<K,V>并没有提供设置Key的方法
注意：
1. Map是一个接口，不能直接实例化对象 ，如果 要实例化对象只能实例化其实现类TreeMap或者HashMap2. 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 的区别
import java.util.TreeMap;
import java.util.Map;
public static void TestMap(){
Map<String, String> m = new TreeMap<>();
// put(key, value):插入key-value的键值对
// 如果key不存在，会将key-value的键值对插入到map中,返回null
m.put("林冲", "豹子头");
m.put("鲁智深", "花和尚");
m.put("武松", "行者");
m.put("宋江", "及时雨");
String str = m.put("李逵", "黑旋风");
System.out.println(m.size());
System.out.println(m);
// put(key,value): 注意key不能为空，但是value可以为空
// key如果为空，会抛出空指针异常
//m.put(null, "花名");
str = m.put("无名", null);
System.out.println(m.size());
// put(key, value):
// 如果key存在，会使用value替换原来key所对应的value，返回旧value
str = m.put("李逵", "铁牛");
// get(key): 返回key所对应的value
// 如果key存在，返回key所对应的value
// 如果key不存在，返回null
System.out.println(m.get("鲁智深"));
System.out.println(m.get("史进"));
//GetOrDefault(): 如果key存在，返回与key所对应的value，如果key不存在，返回一个默认值
System.out.println(m.getOrDefault("李逵", "铁牛"));
System.out.println(m.getOrDefault("史进", "九纹龙"));
System.out.println(m.size());
//containKey(key)：检测key是否包含在Map中，时间复杂度：O(logN)
// 按照红黑树的性质来进行查找
// 找到返回true，否则返回false
System.out.println(m.containsKey("林冲"));
System.out.println(m.containsKey("史进"));
// containValue(value): 检测value是否包含在Map中，时间复杂度: O(N)
// 找到返回true，否则返回false
System.out.println(m.containsValue("豹子头"));
System.out.println(m.containsValue("九纹龙"));
// 打印所有的key
// keySet是将map中的key防止在Set中返回的
for(String s : m.keySet()){
System.out.print(s + " ");
}
System.out.println();
// 打印所有的value
// values()是将map中的value放在collect的一个集合中返回的
for(String s : m.values()){
System.out.print(s + " ");
}
System.out.println();
// 打印所有的键值对
// entrySet(): 将Map中的键值对放在Set中返回了
for(Map.Entry<String, String> entry : m.entrySet()){
System.out.println(entry.getKey() + "--->" + entry.getValue());
}
System.out.println();
}
注意：
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 的区别
import java.util.TreeSet;
import java.util.Iterator;
import java.util.Set;
public static void TestSet(){
Set<String> s = new TreeSet<>();
// add(key): 如果key不存在，则插入，返回ture
// 如果key存在，返回false
boolean isIn = s.add("apple");
s.add("orange");
s.add("peach");
s.add("banana");
System.out.println(s.size());
System.out.println(s);
isIn = s.add("apple");
// add(key): key如果是空，抛出空指针异常
//s.add(null);
// contains(key): 如果key存在，返回true，否则返回false
System.out.println(s.contains("apple"));
System.out.println(s.contains("watermelen"));
// remove(key): key存在，删除成功返回true
// key不存在，删除失败返回false
// key为空，抛出空指针异常
s.remove("apple");
System.out.println(s);
s.remove("watermelen");
System.out.println(s);
Iterator<String> it = s.iterator();
while(it.hasNext()){
System.out.print(it.next() + " ");
}
System.out.println();
}
用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快
1、哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有 m 个地址时，其值域必须在 0 到 m-1之间2、哈希函数计算出来的地址能均匀分布在整个空间中3、哈希函数应该比较简单
常见哈希函数
负载因子和冲突率的关系粗略演示
1、通过哈希函数获取待插入元素在哈希表中的位置2、如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素
1. 每个桶的背后是另一个哈希表2. 每个桶的背后是一棵搜索树
1. HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 Set2. java 中使用的是哈希桶方式解决冲突的3. java 会在冲突链表长度大于一定阈值后，将链表转变为搜索树（红黑树）4. java 中计算哈希值实际上是调用的类的 hashCode 方法，进行 key 的相等性比较是调用 key 的 equals 方法。所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值， 必须覆写 hashCode 和 equals 方法 ，而且要做到 equals 相等的对象， hashCode 一定是一致的。