对于不同的数据结构，他们的使用场景是不一样的，map和set这两种数据结构主要用在搜索相关的场景中。学习这些之前我们先来了解一下二叉搜索树，

一、搜索树

1.1概念

---

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的右节点是curparent.right=cur.right;}else if(parent.left==cur){//parent的左节点是curparent.left=cur.right;}}else if(cur.right==null){//情况2：cur的右边为空if(cur==root){//cur是根结点root=cur.left;}else if(parent.right==cur){//parent的右节点是curparent.right=cur.left;}else{//parent的左节点是curparent.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复杂度分析

！！！Map.Entry<k,v>中没有设置key的方法。 

---

3.1Map的常用方法

---

四、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");//判断元素是否存在于集合中，存在返回trueSystem.out.println(treeSet.contains("hello"));//迭代器遍历Iterator<String> it = treeSet.iterator();while(it.hasNext()){System.out.println(it.next()+" ");}}

---

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;//随便举例的一个哈希函数//首先要遍历对应链表，看是否已经存在keyNode 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性能分析

---

5.6哈希表和Java类集的关系