public void remove(int key){
        TreeNode cur=root;
        TreeNode parent=null;
        while (cur!=null){
         if(cur.val>key){
               parent=cur;
               cur=cur.left;
           }
           else if(cur.val<key){
               parent=cur;
               cur=cur.right;
           }
           else  {
               remodeNode(parent,cur);
               return;
           }
        }

    }

    private void remodeNode(TreeNode parent,TreeNode cur) {
    if(cur.left==null){
if(cur==root){
    root=cur.right;
}
else if(parent.left==cur){
parent.left=cur.right;
}
else if(parent.right==cur){
    parent.right=cur.right;
}
    }
    else if(cur.right==null){
        if(cur==root){
            root=cur.left;
        }
        else if(parent.left==cur){
            parent.left=cur.left;
        }
        else if(parent.right==cur){
            parent.right=cur.left;
        }
    }
    else{
        TreeNode temp=cur;
        TreeNode t=cur.right;
        while(t.left!=null){
            temp=t;
            t=t.left;
        }
        cur.val=t.val;
        if(temp.left==t){
            temp.left=t.right;
        }
        else {
            temp.right=t.right;
        }
    }

    }

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。

对有 n 个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

1.7 和 java 类集的关系

2. 搜索

常见哈希函数

1. 直接定制法 --( 常用 )

取关键字的某个线性函数为散列地址： Hash （ Key ） = A*Key + B 优点：简单、均匀 缺点：需要事先知道关 键字的分布情况 使用场景：适合查找比较小且连续的情况 

2. 除留余数法 --( 常用 )

设散列表中允许的 地址数为 m ，取一个不大于 m ，但最接近或者等于 m 的质数 p 作为除数，按照哈希函数： Hash(key) = key% p(p<=m), 将关键码转换成哈希地址

3. 平方取中法 --( 了解 )

假设关键字为 1234 ，对它平方就是 1522756 ，抽取中间的 3 位 227 作为哈希地址； 再比如关键字为 4321 ，对 它平方就是18671041 ，抽取中间的 3 位 671( 或 710) 作为哈希地址 平方取中法比较适合：不知道关键字的分 布，而位数又不是很大的情况

4. 折叠法 --( 了解 )

折叠法是将关键字从左到右分割成位数相等的几部分 ( 最后一部分位数可以短些 ) ，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。 折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

5. 随机数法 --( 了解 )

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即 H(key) = random(key), 其中 random 为随机数函数。 通常应用于关键字长度不等时采用此法

6. 数学分析法 --( 了解 )

设有 n 个 d 位数，每一位可能有 r 种不同的符号，这 r 种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。例如：

2. 二次探测

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为 , 或者：= (- )% m。其中：i = 1,2,3… ，是通过散列函数Hash(x) 对元素的关键码 key 进行计算得到的位置，m是表的大小。 对于 2.1 中如果要插入 44 ，产生冲突，使用解决后的情况

public class Hashbuck {
  static  class Node{
        public  int val;
        public  int key;
        public Node next;
        public Node(int val,int key){
            this.val=val;
            this.key=key;
        }
    }
    public static final double DE_FAC=0.75f;
    public Node[] array=new Node[10];
    public int usedSize;

2、插入

我们插入的时候，采用尾插法，以4下标为例，要插入的key=14，用key%array.length得到插入数组链表下标值，然后去遍历这个下面的链表，找到相同key，并更新，如果没有找到，则进行头插法

然后usedsize++，我们在算一下负载因子，usedsize是填入的个数去除以array.length,当负载因子大于0.75的时候，就需要进行扩容，而扩容的时候，我们的思路是定义一个新的链表数组，去遍历旧的数组链表每一个下标的链表每一个节点，用他的key去%新数组长度，然后采用头插

 public void put(int val,int key){
        int index=key%array.length;
        Node cur=array[index];
        while(cur!=null){
            if(cur.key==key){
                cur.val=val;
                return;
            }
            cur=cur.next;
        }
        //没有找到当前链表中有这个key节点
        //jdk8就是尾插
        Node node=new Node(key,val);
        node.next=array[index];
        array[index]=node;
        usedSize++;
        if(dloadFactor()>=DE_FAC){
        resize();
        }
    }

    private void resize() {
        //array= Arrays.copyOf(array,array.length)
    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;
    }

    private double dloadFactor(){
        return usedSize*1.0/array.length;
    }

3获取元素

 public int getval(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;
  }

下面是带有泛型的hashbuck

初始化

   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 void put(K key,V val){
        int hashcode=key.hashCode();
        int index=hashcode%array.length;
        Node<K,V> cur=array[index];
        while(cur!=null){
            if(cur.equals(val)){
                cur.val=val;
            }
            cur=cur.next;
        }
        Node<K,V> node=new Node<>(key,val);
        node.next=array[index];
        array[index]=node;
        usedsize++;
    }

获取元素

   public V getval(K key){
        int hashcode=key.hashCode();
        int index=hashcode%array.length;
        Node<K,V> cur=array[index];
        while(cur!=null){
            if(cur.key.equals(key)){
                return cur.val;
            }
            cur=cur.next;
        }
        return null;
    }

只出现一次数字

我们去遍历这个数组，然后去判断集合里面没有相同的值set.contains，没有就用set.add,有就删除，最后集合里面只剩下一个元素，去遍历集合

    public int singleNumber(int[] nums) {
        HashSet<Integer> set=new HashSet<>();
        for(int i=0;i<nums.length;i++){
            if(set.contains(nums[i])){
                    set.remove(nums[i]);
            }
            else{
                    set.add(nums[i]);
            }
        }
             for(int i=0;i<nums.length;i++){
           if(set.contains(nums[i])){
            return nums[i];
           }
        }
        return -1;
    }

复制带随机指针链表

5.12 和 java 类集的关系

1. HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 Set

2. java 中使用的是哈希桶方式解决冲突的

3. java 会在冲突链表长度大于一定阈值后，将链表转变为搜索树（红黑树）

4. java 中计算哈希值实际上是调用的类的 hashCode 方法，进行 key 的相等性比较是调用 key 的 equals 方法。所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值， 必须覆写 hashCode 和 equals 方 法 ，而且要做到 equals 相等的对象， hashCode 一定是一致的。