数据结构---MapSet

（一）Map&Set底层

我们看这张图，今天主要讲的就是Map&Set，那底层又分为hashmap，treemap，hashset，treeset，hashset的底层本质是hashtree，treeset的底层本质是treemap

我们发现，set的key是个泛型，value就是个默认的object对象

那我们知道了treeset底层是treemap,那treemap的底层是什么呢？

他的背后是一棵搜索树（红黑树），是一棵特殊的二叉搜索树

（二）二叉搜索树

1.定义

  二叉搜索树又叫二叉排序树，因为他的中序遍历是有序的，它或者是一棵空树或者满足以下性质：

若他左子树不为空，则左子树上的节点都小于根节点的值

若他右子树不为空，则右子树上的节点都大于根节点的值

他的左右子树也都是二叉搜索树

这个就是一个二叉搜索树

这也是一个二叉树所以，我们可以对这个进行处理，变成avl树（也是一种特殊的二叉搜索树）通过左右旋转来调整树的结构，以求让树更平衡

2.实现

那么接下来我们可以自己实现一个简单的二叉搜索树

1）查找

因为左子树都小于根节点，右子树都大于根节点，所以查找是很简单的

  首先我们判断根节点的值是否等于要找的值，如果等于直接返回，再判断根节点值是否大于要找的值，如果大于就去左子树找，如果小于就去右子树找，找到了就返回，否则就一直找到null，因为遍历到节点为null，就说明要找的值不在这个树中了 

   public boolean search(int key){
        TreeNode cur=root;
        while(cur!=null){
            if(cur.val==key){
                return true;
            } else if (cur.val>key) {
                cur=cur.left;
            }else {
                cur=cur.right;
            }
        }
        return false;
    }

2）插入

如果树为空树，即根为null，那么我们就可以直接插入

  如果树不为空，我们需要先找到插入的位置（一般我们二叉搜索树是不允许出现重复值的，所以我们可以先进行判断，没有这个值再插入）但是这里我们这里只有一个节点是不可以的，因为我们插入一定要找到他的根节点，然后在根节点的左右插入，所以我们需要记录他的根节点

 public boolean insert(int key){
        if (root==null){
            root=new TreeNode(key);
            return true;
        }
        //判断是否以及有这个值，有就返回false
        final boolean search = search(key);
        if(search==false)return false;
        //没有就执行插入
        TreeNode p=null;
        TreeNode cur=root;
        while(cur!=null){
            if(cur.val>key){
                p=cur;
                cur=cur.left;
            }else {
                p=cur;
                cur=cur.right;
            }
        }
        if(p.val>key)p.left=new TreeNode(key);
        if(p.val<key)p.right=new TreeNode(key);
        return true;
    }

3）删除

  首先我们判断二叉搜索树中是否有这个值，如果没有返回false，如果有就设待删除结点为cur，待删除结点的双亲结点为parent

分为三种情况，首先就是cur.left==null

第二种就是cur.right=null那么只需要把上面的cur.right变成cur.left即可

第三种也是最麻烦的一种，他左右子树全都有，那么我们还需要找到一个结点满足根结点大于所有左子树，小于所有右子树，那么我们可以挑选右子树的最小结点或者左子树的最大结点，这两个结点是满足我们刚刚说的，我们把他的值放到被删除结点中，然后我们发现这右子树的最小结点或者左子树的最大结点肯定是缺少左子树或者右子树的，不然也不是右子树的最小结点或者左子树的最大结点了

public boolean remove(int key){
        if (root==null){
            return false;
        }
        final boolean search = search(key);
        if(search==false)return false;
        TreeNode p=null;
        TreeNode cur=root;
        while(cur!=null){
            if(cur.val>key){
                p=cur;
                cur=cur.left;
            }else if(cur.val<key){
                p=cur;
                cur=cur.right;
            }else {
                realRemove(cur,p);
                return true;
            }
        }
    }

    private void realRemove(TreeNode cur, TreeNode p) {
        if(cur.left==null){
            if(cur==root){
                root=cur.right;
            } else if (cur==p.left) {
                p.left=cur.right;
            }else {
                p.right=cur.right;
            }
        } else if (cur.right==null) {
            if(cur==root){
                root=cur.left;
            } else if (cur==p.left) {
                p.left=cur.left;
            }else {
                p.right=cur.left;
            }
        }else {
            TreeNode targetParent=cur;
            TreeNode target=cur.right;
            while(target.left!=null){
                targetParent=target;
                target=target.left;
            }
            cur.val=target.val;
            if(targetParent.left == target) {
                targetParent.left = target.right;
            }else {
                targetParent.right = target.right;
            }
        }
    }

   4）性能分析

  我们写代码的时候看到，插入和删除都要先查找有没有这个元素，所以他的性能跟查找的时间复杂度有很大关系

对于同一个关键码集合，如果插入的顺序不同，那么得到的二叉搜说树也会不同

最好情况下，二叉搜索树是一颗完全二叉树，他的时间复杂度O（logN）最坏的情况下，二叉搜索树是一棵单支树那么他的复杂度就问为O（logN），所以我们就考虑能否改进，不论按什么次序插入，都可以让二叉搜索树性能变高？

我们Treeset,Treemap就是使用的二叉搜索树，而他们实际上用到，是红黑树：一棵近似平衡的二叉树，就是在二叉搜索树基础+颜色及红黑树性质验证

（三）Map&Set用来查找

Map和Set是一种专门用来搜索的数据结构，他的搜索效率与具体new出来的子类有关，我们以前的查找方式一般都是：直接遍历（时间复杂度O（N））数据过多会很慢，二分查找（时间复杂度O(logN)但是要求序列必须是有特定的有序关系）

上面的两种查找方式，虽然可以查找，但是一旦元素过多且无序，还涉及到插入删除操作（动态查找），那么上面两种查找方式就不是很合适，这时就可以用到Map&Set

我们上面看底层代码时我们看到，Map是key-Value模型，Set是纯key模型，所以我们可以利用这两种模型进行一些操作

（四）Map与Set的使用

Map是一个接口类，存的是key-Value结构，并且我们要求key一定是唯一的不可重复

1.Map常用方法说明

我们这里只讲两个方法，Set<K>keyset和Set<Map.Entry<K,V>>entrysSet

Set<K>keyset是返回所有key的不重复集合，也就是把map中的key放到一个集合中返回

Set<Map.Entry<K,V>>entrysSet    是把key-Value映射关系当作Set的key放到set里面

我们可以遍历整个Set来获取到对应的key和value

 Map<Integer,String> m=new HashMap<>();
        final Set<Map.Entry<Integer, String>> entries = m.entrySet();
        final Set<Integer> integers = m.keySet();
        for (Map.Entry<Integer,String> e1:entries
             ) {
            e1.getKey();
            e1.getValue();
        }
    }

注：

1.Map是一个接口，是不能实例化对象的，我们只可以实例化他的实现类，TreeMap和HashMap

2.Map中的key是唯一的（treemap的key要可以比较，hashmap的key要重写hashcode方法和equals方法）

3.Treemap中插入键值对是，key不可以为空，但是value可以，Hashmap的key value都可以为空

4.Map中的key可以全部分离出来放到set中进行访问（因为key都不重复）

5.map中键值对的key是不可以直接修改的，但是value是可以修改的，如果要修改key，就只能先将key删掉，然后重新插入

6.Treemap和Hashmap区别

2.Set常用方法说明

Set的方法也都比较好理解，这里我们来讲一下这个iterator（）怎么用

注：

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的区别（因为本质还是Treemap和Hashmap，我们看Treemap和Hashmap区别就可以）

(五)哈希表

  我们之前讲到的查找，包括刚刚的二叉搜索树，他们的复杂度最好也是O(logN),那么有没有一种数据结构，复杂度为O(1)一下子就可以直接搜索到元素

那么此时就出现了哈希表

1.什么是哈希表

1.当我们插入元素时，我们根据待插入元素的hashcode再通过一个哈希函数，计算出该元素的存放位置进行存放

2.当我们搜索元素时，我们对元素的hashcode进行同样的计算，把求的函数值当作元素的存储位置，在结构中的整个位置取元素通过equals进行比较，颗相等就搜索成功

举个例子

但是这里也会有问题，如果我们再插个元素11，会发生什么？

2.哈希冲突

如果我们再插入个11，我们发现11和1都会放到同一个位置，但是很明显他的值是不同的也就是说：不同的hashcode通过哈希函数会计算出相同的哈希地址，那这种现象我们叫做哈希冲突

1）避免哈希冲突

通过哈希函数

  首先我们要知道，哈希冲突的发生是必然的，因为我们哈希表底层的数组容量大概率是小于实际要存储关键字的数量的，所以我们要做的是降低哈希冲突的概率

  那具体怎么降低，我们知道哈希冲突是因为哈希地址相同，那这个哈希地址是通过哈希函数计算出来的，我们可以先从哈希函数上下手，我们可以看看哈希函数设计的是否合理

  哈希函数的设计原则：

哈希函数的定义域要包括所有hashcode，数组有m个地址，他的值域就要再0~m-1

哈希函数计算的地址能均匀分布在整个空间且哈希函数应该比较简单（太复杂影响效率）

常见的哈希函数：

1.直接定制法

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B 优点：简单、均匀 缺点：需要事先知道关 键字的分布情况

2.除留余数法

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

其实还有很多哈希函数，但是这两个是比较常用的

通过负载因子

所以负载因子越高就代表冲突率越高，那么我们就要想办法降低负载因子，但是关键字个数是不可以删减的，那么就需要我们调整哈希表中的数组大小

2）解决哈希冲突

分为开散列和闭散列

闭散列

又叫开放地址法，其实很好理解，当我们发生哈希冲突时，如果哈希表还有空位置，我们就会把这个key存放到其他空位置

那找空位置又有两种方法：线性探测法，二次探测法

线性探测法就是说从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

但是线性探测法有一个缺陷就是，我们残生冲突的数据会堆积在一起，如果这个位置继续发生哈希冲突，那下一个空位置就会离我们很远，所以二次探测法为了避免这个问题，他找下一个位置的方法是或者i=1，2，3.....

 采用闭散列处理哈希冲突时，是有一些问题的，我们不可以随便删除哈希表中的元素，如果直接删除了，会影响其他元素的搜索，比如删除元素4，如果直接删除掉会导致44查找受到影响，所以我们一般采用伪删来删除，但是这样空间的利用率很低

而且研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不 会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情 况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。

因此：闭散列最大的缺陷就是空间利用率比较低

开散列

开散列就是把数组中的每一个结点变为链表，是与宣布对键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子 集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

当数组长度大于64且其中一个链表长度大于8就会转变为红黑树

Java中就是使用开散列的方式解决哈希冲突的