Java中的集合-Map和set(java数据结构)

前言：

        TreeMap 和 TreeSet 即 java 中利用搜索树实现的 Map 和 Set；实际上用的是红黑树，而红黑树是一棵近似平衡的二叉搜索树，即在二叉搜索树的基础之上 + 颜色以及红黑树性质验证。

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

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

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

1. 根据姓名查询考试成绩

2. 通讯录，即根据姓名查询联系方式

3. 不重复集合，即需要先搜索关键字是否已经在集合中

Set和Map:

       一般把搜索的数据称为关键字（Key），和关键字对应的称为值（Value），将其称之为Key-value的键值对，所以模型会有两种：

1. 纯 key 模型，比如：

        有一个英文词典，快速查找一个单词是否在词典中

而Map中存储的就是key-value的键值对，Set中只存储了Key

Map的使用：

        

我们可以看到Map是一个接口类，其中该接口灭有继承Collection接口，该类存储的<K,V>键值对，并且K是唯一的，它不会存储两个相同的K！ 

Map.Entry<K,V>的说明：

        

可以理解为是一个节点，里面存放内每一个节点的信息！

最终是在HashMap和TreeMap种实现内部类并且继承了内部接口：

该内部类可以理解为一个节点，里面包含了该节点的信息和方法。

 Map常用的方法：

        

这些方法在TreeMap和HashMap都已经重写过，那么直接先来看看这些方法的作用。

    public static void main(String[] args) {Map<String, Integer> m = new TreeMap<>();//设置K代表的Vm.put("abc",4);m.put("a",1);m.put("b",2);//如果插入相同的K，此时要更新K对应的V/*    m.put("a",4);System.out.println(m.get("a"));*///返回k对应的VSystem.out.println(m.get("abc"));//如果没有找到K，那么就返回nullSystem.out.println(m.get("abcd"));//如果没有找到想要返回我们自定义的值，可以这样设置//如果没有找到K，就返回99，如果找到了K，就返回对应的VSystem.out.println(m.getOrDefault("abcd", 99));System.out.println(m.getOrDefault("abc", 99));//也可以删除K对应的V,此时就相当于也同时删除了Km.remove("abc");//此时找不到K了System.out.println(m.getOrDefault("abc", 99));//返回k的所有不重复集合,返回类型是Set<k>类型System.out.println(m.keySet());//返回v的所有不重复集合，返回类型是Collection<V>类型System.out.println(m.values());//返回所有k于v的不重复集合，返回类型是Set<Map.Entry<K,V>>类型//可以用for each分别接收K，VSystem.out.println(m.entrySet());Set<Map.Entry<String,Integer>> m1 = m.entrySet();for(Map.Entry<String,Integer> m2: m1) {//此时就相当于接收每个节点的信息//再打印每个节点中K，V的值System.out.println("K = "+m2.getKey()+" "+"V = "+m2.getValue());}//判断是否包含KSystem.out.println(m.containsKey("abc"));//判断是否包含VSystem.out.println(m.containsValue(1));}

注意：

1. Map 是一个接口，不能直接实例化对象 ，如果 要实例化对象只能实例化其实现类 TreeMap 或者 HashMap

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

3. 在 TreeMap 中插入键值对时， key 不能为空，否则就会抛 NullPointerException 异常 ， value 可以为空。但

是 HashMap 的 key 和 value 都可以为空。

4. Map 中的 Key 可以全部分离出来，存储到 Set 中 来进行访问 ( 因为 Key 不能重复 ) 。

5. Map 中的 value 可以全部分离出来，存储在 Collection 的任何一个子集合中 (value 可能有重复 ) 。

6. Map 中键值对的 Key 不能直接修改， value 可以修改，如果要修改 key ，只能先将该 key 删除掉，然后再来进行重新插入。

 Set的使用：

        Set与Map主要的不同有两点：Set是继承自Collection的接口类，Set中只存储了Key。

boolean add (E e)                       添加元素，但重复元素不会被添加成功

void clear ()                                清空集合

boolean contains (Object o)       判断 o 是否在集合中

Iterator<E> iterator ()                 返回迭代器

boolean remove (Object o)        删除集合中的 o

int size()                                    返回set 中元素的个数

boolean isEmpty()                     检测set 是否为空，空返回 true ，否则返回 false

Object[] toArray()                       将set 中的元素转换为数组返回

boolean containsAll(Collection<?> c)      集合c 中的元素是否在 set 中全部存在，是返回 true ，否则返回 false

 

boolean addAll(Collection<? extends E> c)      将集合 c 中的元素添加到 set 中，可以达到去重的效果

    public static void main(String[] args) {Set<String> m = new TreeSet<>();m.add("a");m.add("b");m.add("c");m.add("d");//该元素不会被添加成功，原因在于TreeSet的底层还是TreeMap,就相当于K的值，不可以重复添加m.add("d");System.out.println(m);//也可以用for each打印，应为继承了Iterable接口(迭代器)for(String s: m) {System.out.print(s+" ");}System.out.println();//清空集合中的元素
//        m.clear();
//        System.out.println(m);//判断o是否在集合中System.out.println(m.contains("a"));//利用迭代器遍历Iterator<String> it = m.iterator();while(it.hasNext()) {System.out.print(it.next()+" ");}
//    删除集合中的o,删除成功返回true，删除失败返回falseSystem.out.println(m.remove("a"));//返回set集合中元素的个数System.out.println(m.size());//检测是否为空System.out.println(m.isEmpty());//将集合c中的元素添加到集合set中，达到去重效果String[] arr = {"abc","a","b"};List<String> l1 = new ArrayList<>();l1.add("abc");l1.add("a");l1.add("b");System.out.println(m.addAll(l1));System.out.println(m.size());System.out.println(m);}

 Set和Map的本质区别就是在于，Set只能存K，Map可以存K,V，相同点在于都可以达到对K去重的效果。

TreeSet和TreeMap：

        二者底层都是通过红黑树实现的，对于红黑树不了解的可以看我这一篇文章：

红黑树(Java数据结构)-CSDN博客

他们查找元素的时间复杂度是O(log N)。

哈希表：

        前面碰到了HashSet和HashMap，可能是有点懵的的，但是当我们学习完哈希表后就会理解到其内部的深层原理：        

 

这样存放数据有好处，可以直接通过关键码找到我们想要的数据。

但是此时这样设计有一点问题，如果我此时要存放14、24，那么都会放在4下标，此时产生了冲突！！

冲突：

        在设计哈希表的时候会出现上述的冲突，但是，我们可以通过一些方法解决上面的冲突！

方法一：直接定制法：

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

(也就是自己设计一个线性函数，将对应的元素存放在对应的位置上面！！)

方法二：. 除留余数法--(常用)：

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：

Hash(key) = key% p(p<=m),将关键码转换成哈希地址

这样做可以减小冲突，但是不会消除冲突！！

负载因子的调节：

当冲突出现的时候，我们应该尽可能的降低冲突，但是要想消除冲突是不可能的，但是这里提供了一种有效降低冲突的方法，就是调节负载因子。

负载因子 = 元素个数 / 表的长度。

一般规定，负载因子的大小要保持在0.75，也就是每插入一个元素，就要调整表的长度，使其负载因子控制在0.75！！

这样的思能够有效降低冲突发生的机率！！

但是Java中提供的方法更为厉害，接下俩就来了解一下：

闭散列--解决冲突：

        当发生冲突时，此时有一个思路：

        从发生冲突的位置开始，依次向后寻找空位，如果找到空位九江元素放在对应的空位位置。

这种方法称为---一次探测

        当然这种方法是可以降低冲突，但是有一个问题---会使得元素堆积在一起，所以就进行了改进：

        现在找下一个空位置的方法为：Hi = (H0+i^2 )% m,H0表示发生冲突的位置，Hi表示元素存放的位置，i表示第几次发生冲突，m表示表的长度！！

44%10 = 4，4发生冲突了，所以H0 = 4

H1 = (4+1^2)/10 = 5,此时还是发生冲突了，所以H0 = 5

H1 = (5+2^2)/10 = 9,此时还是发生冲突了，所以H0 = 9

H1 = (9+3^2)/10 = 8,该位置没有放元素，所以直接放到该位置即可！

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

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

开散列—解决冲突（哈希桶）：

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

实现一个简单的哈希桶：

        

    static class Node {public int val;public int key;private Node next;public Node(int key, int val) {this.val = val;this.key = key;}}private Node[] arr = new Node[10];private int usedSize;public boolean push(int key,int val) {int index = key%arr.length;//扩容if(usedSize*1.0/arr.length > 0.75) {Node[] tmp = new Node[arr.length+(arr.length<<2)];//扩容1.5倍//重新哈希reSize(tmp,arr);}if(arr[index] == null) {//尾插arr[index] = new Node(key,val);usedSize++;return true;}//尾插Node cur = arr[index];while(cur.next != null) {if(cur.key == key) {cur.val = val;return false;}cur = cur.next;}if(cur.key == key) {cur.val = val;return false;}cur.next = new Node(key,val);usedSize++;return true;}public void reSize(Node[] tmp,Node[] arr) {for(int i = 0;i<arr.length;i++) {if(arr[i] != null) {Node cur = arr[i];while(cur != null) {int index1 = cur.key%tmp.length;if(tmp[index1] == null) {//尾插tmp[index1] = cur;cur = cur.next;}else {Node cur1 = tmp[index1];while (cur1.next != null) {cur1 = cur1.next;}cur1.next = cur;cur = cur.next;}}}}arr = tmp;}public int get(int key) {//返回key对应的valint index = key%arr.length;Node cur = arr[index];while(cur != null) {if(cur.key == key) {return cur.val;}cur = cur.next;}//没有找到return -1;}public int size() {return usedSize;}