数据结构--Map和Set-EW帮帮网

一.二叉搜索树

概念：

1. 左子树的值都小于根节点的值，右子树的值都大于根节点的值

2.中序遍历为一个有序集合

二.模拟实现

1.查找

2.插入

3.删除

三.搜索

概念：

Map和set是一种专门用来进行搜索的容器或者数据结构，其搜索的效率与其具体的实例化子类有关。以前常见的搜索方式有：

1. 直接遍历，时间复杂度为O(N)，元素如果比较多效率会非常慢

2. 二分查找，时间复杂度为LogN,但搜索前必须要求序列是有序的

上述排序比较适合静态类型的查找，即一般不会对区间进行插入和删除操作了，而在现实查找中，可能在查找时进行一些插入和删除的操作，即动态查找，那上述两种方式就不太适合了，本节介绍的Map和Set是一种适合动态查找的集合容器。

模型：

一般把搜索的数据称为关键字（Key），和关键字对应的称为值（Value），将其称之为Key-value的键值对，所以模型会有两种，分别为纯 key 模型和Key-Value 模型，而Map中存储的就是key-value的键值对，Set中只存储了Key。

四.复习

五.TreeMap和TreeSet

TreeMap:

Map是一个接口类，该类没有继承自Collection，该类中存储的是结构的键值对，并且K一定是唯一的，不能重复。TreeMap.Entry <K,V>也是接口，TreeMap.Entry <K,V>是Map内部实现的用来存放键值对映射关系的内部类(类似于链表中的节点),并且实现了Map.Entry <K,V>接口，而MapTree 实现了Map接口.

1.方法及其解释

2.方法的使用

public static void main1(String[] args) {
        TreeMap<String,Integer> map =new TreeMap<>();
        //设置key和 value值
        map.put("zhangshang",1);
        map.put("abc",3);
        //key值可以相同，如果相同只会改 value值，此时“abc”的value值为2
        //此时返回的是替换前的value值，即为3
        System.out.println(map.put("abc", 2));
        //不能插入null，因为底层为一个红黑树，也是一个搜索树
        //而搜索树每次插入都得进行比较,null值不能进行比较
        map.put(null,22);
        //得出key对应的value值
        System.out.println(map.get("abc")); //得出结果为2
        //报错，原因是返回null后用int接收拆箱操作
        //会转化为 null.intValue 导致为空指针异常
        int ret = map.get("abc1");
        System.out.println(ret);
        System.out.println(map.remove("abc"));//结果为2，删除key值并返回对应的 Value
        System.out.println(map.get("abc")); //由于删除结果为空
        System.out.println(map.containsKey("abc")); //查看是否有key 结果为 false
        System.out.println(map.containsValue(2)); // 查看是否有value 结果为 false
        //也是找 key 值并返回对应的 value 值，但如果没找到返回自己设置的默认值而不是 null
        //所以结果为 555
        System.out.println(map.getOrDefault("abc", 555));
        //遍历map中的所有节点的 key和 value
        //不能使用迭代器，因为 Map没实现 iterable 接口，不能得到迭代器
        Set<Map.Entry<String, Integer>> entries = map.entrySet();
        for (Map.Entry<String,Integer> node:entries) {
            System.out.println("key :"+node.getKey()+"value :"+node.getValue());
        }
        for (Integer s: map.values()) {
            System.out.print(s+" ");
        }
        System.out.println();
        for (String s: map.keySet()) {
            System.out.print(s+" ");
        }
        System.out.println();
        System.out.println(map);  //调用了底层实现的toString()方法
    }

3.方法的底层

补充：

TreeSet:

Set与Map主要的不同有两点：Set是继承自Collection和 iterable的接口类，可以得到迭代器，Set中只存储了Key。SetTree继承了Set.

方法及其解释：

使用：

   public static void main(String[] args) {
        TreeSet<String> set =new TreeSet<>();
        System.out.println(set.add("123")); //返回 true
        System.out.println(set.add("123")); //返回 false,key必须唯一
        set.add("abc");
        set.add("lisi");
        set.add(null); //报错，和 TreeMap一样的原因
        set.remove("123"); //删除key
        System.out.println(set.contains("123")); //结果为 false,看集合里是否存在key
        System.out.println(set.size());          //查看集合中元素的个数
        //遍历 set 集合中的所有key
        Iterator<String> iterator = set.iterator();
        while (iterator.hasNext()){
            System.out.print(iterator.next()+" ");
        }
        System.out.println();
        set.clear();            //清空set中的所有元素
        System.out.println(set.isEmpty()); //结果为true， 看集合是否为空
    }

注意：

1.TreeSet的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的

六.哈希表

1.概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(logN )，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

当向该结构中：

插入元素

根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

搜索元素

对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)

举例：

2.冲突 --概念

不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。如上述举例中如果插入14，就会与4冲突。

3.冲突 --避免

首先，我们需要明确一点，由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的，这就导致一个问题，冲突的发生是必然的，但我们能做的应该是尽量的降低冲突率。

3.1 冲突-避免-哈希函数设计

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。哈希函数设计原则：

1.哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1 之间

2.哈希函数计算出来的地址能均匀分布在整个空间中

3.哈希函数应该比较简单

3.2 冲突-避免-负载因子调节（重点掌握）

所以当冲突率达到一个无法忍受的程度时，我们需要通过降低负载因子来变相的降低冲突率。已知哈希表中已有的关键字个数是不可变的，那我们能调整的就只有哈希表中的数组的大小(重点)。

4.冲突 --解决

解决哈希冲突两种常见的方法是：闭散列和开散列

4.1冲突 --解决--闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢？

1.线性探测

比如上面的场景，现在需要插入元素44，先通过哈希函数计算哈希地址，下标为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。

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

通过哈希函数获取待插入元素在哈希表中的位置如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

2.二次探测

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

因此：比散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。

4.2 冲突 --解决 --开散列/哈希桶（重点掌握）

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

数据结构--Map和Set