数据结构八：二叉搜索树，Map，Set，哈希

前言：

 

目录

1.二叉搜索树

1.1：概念

 1.2：模拟实现二叉树的操作

 1.2.1:插入

1.2.2：查找 

 1.2.3：删除

2.概念和模型

2.1：概念

2.2：模型

3.Map

3.1：Map.Entry的说明,v>

3.2：Map的常用方法说明

4.Set的说明书

5.oj题练习

5.1.复制待随机指针的链表

5.2:前K个高频单词

6.哈希表

6.1：冲突

6.1.1：概念

6..2：冲突-避免-负载因子调节

6.2.3：冲突解决--闭散列

6.3.3：冲突解决-开散列/哈希桶

7.HashCode()和equals()的区别 

7.1：面试题：

---

这是数据结构的最后一篇，这篇会讲到Map和set还有哈希。学了这些，遇到莫些题，你会觉得很简单。

1.二叉搜索树

1.1：概念

二叉搜索树又称二叉排序树---二叉树节点的值都是唯一的，不重复的

1.若它的左子树不为空。则左子树的所有节点的值都小于根节点的值

2，若他的右子树不为空，则右子树的所有节点的值都大于根节点的值。

 1.2：模拟实现二叉树的操作

 1.2.1:插入

插入是在二叉树的叶子节点进行插入的

public boolean insert(int key) {
        TreeNode ret=new TreeNode(key);
        //判断此树是不是空树
        if(root==null){
            root=ret;
            return true;
        }
        TreeNode parent=null;
        TreeNode cur=root;
        while(cur!=null){
            //判断它是不是大于此节点的值
            if(cur.key//大于根节点，往右边插
                parent=cur;//记录父亲节点
                cur=cur.right;
            }else if(cur.key>key) {//小于根节点的，往左边插
                parent =cur;
                cur=cur.left;
            }
        }//此时到了叶子节点
        if(ret.key< parent.key){
            parent.left=ret;
        }else {
            parent.right=ret;
        }
        return  true;
    }

     

---

1.2.2：查找 

若根节点不为空

如果根节点key==查找的key返回true

如果根节点key>查找的key，在左子树查找。

如果根节点key<查找的key，在右子树查找。

  public TreeNode search(int key) {
      //查找根节点是否为null
        if(root==null){
            return null;
        }
        TreeNode cur=root;
        while(cur!=null){
            if(cur.key>key){//比根节点小
                cur=cur.left;
            }else if(cur.key//比根节点大
                cur=cur.right;
            }else{
                return cur;//找到
            }
        }
        return null;
    }

 1.2.3：删除

删除比较麻烦，要分为三大类。设待删除节点为cur .待删除的父亲节点为parent.

  //删除节点
    public  void removeChild(TreeNode cur,TreeNode parent){
        //分三种情况
        //1 cur.left==null
        if(cur.left==null){
            //判断是不是根节点
            if(cur.equals(root)){
                root=root.right;
            }
            if(cur.equals(parent.left)){
                parent.left=cur.left;
            }
            if(cur.equals(parent.right)){
                parent.left=cur.right;
            }
        }else if(cur.right==null){ //2.cur.right==null
           if(cur.equals(root)){
               root=root.left;
           }
           if(cur.equals(parent.right)){
               parent.right=cur.left;
           }
           if(cur.equals(parent.left)){
               parent.left=cur.left;
           }
        }else{//3.cur.left!=null&&cur.right!=null
            //用一个叫做替罪羊
            //可以找左树的最右边，就是左边最大的，也小于根节点
            //可以找右边的最左边，就是右边最小的，也大于根节点
            TreeNode target=cur.left;//左树
            TreeNode targetParent=cur;
            while(target.right!=null){//左树的最右边
                targetParent=target;
                target=target.right;
            }
            cur.key=target.key;//将替罪羊的值赋值给cur
            //将替罪羊删除
            if(target.equals(targetParent.left)){
                targetParent.left=target.left;
            }else{
                targetParent.right=target.right;
            }
        }
    }
}

---

2.概念和模型

2.1：概念

Map和Set是一种专门用来进行搜索的容器或者数据结构，其底层是一棵二叉搜索树。其搜索的效率与其具体的实际化子类有关。可能在查找时进行一些插入和删除的操作，即动态查找。

本节介绍的Map和Set是一种适合动态查找的集合容器。
 

2.2：模型

把搜索的数据称为关键字（Key)和关键字对应的称为值(Value),将其称为Key-Value的键值对

1.纯Key模型----快速查找莫个数据是否存在

2.Key-Value模型---统计文件中每个单词出现的次数。<单词，单词出现的次数>

3.Map

Map是一个接口类，没有继承Collection(Set和List都继承了），该类存储的是结构的键值对，并且K一定是唯一的。

3.1：Map.Entry的说明

Map.Entry是Map内部实现的用来存放键值对映射关系的内部类

 

 

 

 

public class Test {
    public static void main(String[] args) {
        TreeMapmap=new TreeMap<>();
        map.put("hello",4);//h-104
        map.put("world",1);//w-119
        map.put("abc",7);//a-97
        //返回所以的Key-Value的映射关系
        Set< Map.Entry>entrySet=map.entrySet();
        for (Map.Entryentry:entrySet) {
            System.out.println("Key:"+entry.getKey()+" "+
                             "Value"+entry.getValue());
        }
    }
}

 从中，看出了什么吗？

Key的是安找升序排序的，故：Key一定要比较，不然会报错。

3.2：Map的常用方法说明

 

 

 

 

 

 

 

 

 

 

注意：

1.Map是一个接口，不能直接实例化对象。

2.Map中存放键值对的Key是唯一的，Value是可以重复的。

3.Key不能为空，否则就会包空指针异常。

4.Map中键值对的Key不能直接修改（如果要修改，只能先删除，再进行重新插入！）

---

4.Set的说明书

Set继承Collection的接口类，Set中存储Key

 

 

 

 

 

 

 

 

 

 

注意：

1.set中只存储了key，并且要求key一定要唯一。

2.Set的底层是使用map来实现的。

3.set最大的功能就是对集合中的元素去重

4.set中不能插入null的key。

5.oj题练习

5.1.复制待随机指针的链表

在笔试中出现过。可以注意下哟

138. 复制带随机指针的链表 - 力扣（LeetCode）

class Solution {
    public Node copyRandomList(Node head) {
        HashMap map=new HashMap<>();
        Node cur=head;//将链表都存到map中
        while(cur!=null){
            Node node=new Node(cur.val);//创建一个节点
             map.put(cur,node);
            cur=cur.next;
        }
        //第二次遍历链表
        cur=head;
        while(cur!=null){
            map.get(cur).next=map.get(cur.next);
            map.get(cur).random=map.get(cur.random);
            cur=cur.next;
        }
    return map.get(head);
}
}

5.2:前K个高频单词

 692. 前K个高频单词 - 力扣（LeetCode）

 这道题我就说说思路就不画图了。

1.我们用HashMap 来存放单词。key是单词。value 是单词出现的次数

2.Top-k问题。将前K个单词按照频率来建立小堆。

3.K后面的单词，依次和堆顶元素相比较，单词出现频率大于堆顶的。该单词入堆。堆顶元素出堆。如果频率出现相同。比堆顶单词首字母大。该单词入堆，堆顶元素出堆。按照单词大小建立大堆。

4.用列表保存堆中元素,之后逆转。

class Solution {
    public List topKFrequent(String[] words, int k) {
            HashMap map = new HashMap<>();
        //保存字符串数组到map
        for (String x : words) {
            if (map.containsKey(x)) {
                int val = map.get(x);
                map.put(x, val + 1);
            } else {
                map.put(x, 1);
            }
        }
        //Top-K问题
        PriorityQueue> q1 =
                new PriorityQueue<>(new Comparator>() {
                    @Override
                    public int compare(Map.Entry o1,
                                       Map.Entry o2) {
                        if (o1.getValue().compareTo(o2.getValue()) == 0) {
                            //频率相同,按照单词首字母大小建立大堆
                            return o2.getKey().compareTo(o1.getKey());
                        }//频率不同，按照频率大小建立小堆
                        return o1.getValue().compareTo(o2.getValue());
                    }
                });
        //遍历map当中的entry
        for (Map.Entry entry : map.entrySet()) {
            //把前k个元素建成小堆
            if (q1.size() < k) {
                q1.offer(entry);
            } else {//后k个元素，逐渐和堆顶元素进行比较
                Map.Entry s1 = q1.peek();
                //频率大
                if (entry.getValue().compareTo(s1.getValue()) > 0) {
                    //比堆顶元素大
                    //将堆顶元素出堆
                    q1.poll();
                    //再将这个元素入堆
                    q1.offer(entry);
                }//和堆顶元素频率相等
                else {
                    if (entry.getValue().compareTo(s1.getValue()) == 0) {
                        //比较单词首字母的大小
                        if (s1.getKey().compareTo(entry.getKey()) > 0) {
                            //比堆顶元素的首字母大，堆顶元素出堆，
                            q1.poll();
                            q1.offer(entry);
                        }
                    }
                }
            }
        }
        //将堆的元素赋值给List
        List list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry m1 = q1.poll();
            list.add(m1.getKey());
        }
        Collections.reverse(list);
        return list;
    }
}

---

6.哈希表

使元素存储位置与它的关键码之间能够建立一一映射的关系。

6.1：冲突

6.1.1：概念

不同关键字通过相同哈希计算出相同的哈希地址，这种现象称为哈希冲突或哈希碰撞。

冲突的发生使必然的，我们只能尽量降低冲突。

6..2：冲突-避免-负载因子调节

载荷因子：填入表中的元素个数/散列表的长度（严格限制在0.7-0.8）之间

6.2.3：冲突解决--闭散列

闭散列：也叫开放定址法。可以将key存放到冲突位置中的‘下一个'空位置中。

1.线性探测：

从发送冲突的位置开始，依次向后探测，直至找到下一个空位置。---冲突数据堆积在一起

2.二次探测：

找下一个空位置的方法：Hi=(Ho+i^2)%m

Hi:要插入的位置

Ho:hash(key)=key%capacity--长度。计算出来的位置

i:第几次冲突。m:长度。

6.3.3：冲突解决-开散列/哈希桶

7.HashCode()和equals()的区别 

hashCode（） 方法的作用是获取哈希码。返回的是一个整数，作用是：确定对象在哈希表的索引下标。

equals()判断两个对象是否相等。

1.两个对象的hashcode一样，equals一定一样？

不一定

2.两个对象的equals一样，hashcode一定一样？

一定

7.1：面试题：

重写equals()方法就可以比较两个对象是否相等，为什么还要重写hashcode()方法？

HashSet和HashMap在判断两个元素是否相等时，会先判断hashCode是否相等，如果

hashCode相等，才会用equals()方法比较是否相等。

---

总结：以上就是我总结的Map和Set，如果有错，请各位铁子留言改正，若感觉不错，一键三连。

 

 

 

 

---