Java集合探秘：Map和Set的魔法世界

目录

Key-Value 模型，

纯 key 模型，

Map

Set

哈希表

冲突概念

哈希函数设置的原则

解决这个冲突有两种办法，一个是闭散列，一个是开散列

put

get

---

我又来啦！

今天来介绍下Map和Set这两个集合类，但也是属于数据结构的

那么先来揭开这个Map和Set到底是何方神圣吧

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

这两个是用两种模型来进行查找的分别对应的是：Key-Value模型、纯Key模型。

那么刚刚这两个又是什么呢？

Key-Value 模型，

比如： 统计文件中每个单词出现的次数，统计结果是每个单词都有与其对应的次数： 梁山好汉的江湖绰号：每个好汉都有自己的江湖绰号

纯 key 模型，

比如： 有一个英文词典，快速查找一个单词是否在词典中 快速查找某个名字在不在通讯录中

注意：

1.Map是一个接口类，该类没有继承这个collection，该类中存储的是结构的键值对，并且k一定是唯一的，不能重复

2.同样的，Set也是一个接口类，该类继承的是collection，该类只存储这个key。

那么我们分别来看看这个他们一些常用的方法吧

Map

public static void main(String[] args) {
        Map map=new HashMap<>();
        //设置key对应的value
        map.put("齐天大圣","孙悟空");
        //返回对应的value
        map.get("齐天大圣");
        //返回key对应的value，key不存在，即返回默认值
        map.getOrDefault("齐天大圣","错误key");
        //删除key对应的映射关系
        map.remove("齐天大圣");
        //判断是否包含key或者value
        map.containsKey("齐天大圣");
        map.containsValue("孙悟空");
    }

有一些注意事项

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删除掉，然后再来进行 重新插入。

刚刚我实例化Map是用HashMap

当然也可以使用TreeMap

而两者之间的当然是有一些不同的啦

请看下面表格

Set

常用方法

public static void main(String[] args) {
        HashSet set=new HashSet<>();
        //添加元素，但重复的元素不会重新添加
        set.add(10);
        //清空集合
        set.clear();
        //判断o是否在集合中
        set.contains(10);
        //删除集合中的o
        set.remove(10);
        //返回Set中元素的个数
        set.size();
        //检测set是否为空，空返回true，否则返回false
        set.isEmpty();
 
    }

注意事项

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可以。

当然，刚刚的代码是实例化了HashSet，当然也可以使用TreeMap

而两者区别，又可以看以下的表格

讲完两个Map和Set

那么就请可以请出这个重量嘉宾啦----哈希表

那么哈希表它又是什么呢？

哈希表

有一种理想的搜索办法：

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

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

举个例子吧

假设我有一个哈希函数

hash（key）=key%capacity；其中capacity是存储元素底层空间总大小

数组集合如下：{2，4，7，9，5，8}

问题来了，如若按照以上的办法进行插入时，当插入元素是44时，发现，下标为4的位置、已经有元素了

而我们把这种情况称之为冲突

冲突概念

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

既然这样，有冲突，我们当然想是去避免啦

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

回过头想想，为什么会发生冲突呢？

有一点可能是哈希函数设置的不合理。

哈希函数设置的原则

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

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

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

所以我们就要设置一些合理的哈希函数

那么常用的的哈希函数有这两个

1.直接定址法

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

优点：简单、均匀 缺点：需要事先知道关键字的分布情况 使用场景：适合查找比较小且连续的情况 

2.除留余数法

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

那么到这里，又有问题了，我们用肉眼可以观察到是有冲突的，但不能光看，肯定要写代码给机器的，所以引入了负载因子

负载因子的定义为:a=填入表中的元素个数/散列表的长度

一般来说，负载因子范围到0.7-0.8，正如Java的系统库中限定了其为0.75

但我们的冲突率太高时，我们可以通过负载因子进行调节

注意的是，哈希表中已有的关键字个数时不可变的，我们能调整的就只有哈希表中的数组大小。

有冲突，我们就可以适当进行解决

解决这个冲突有两种办法，一个是闭散列，一个是开散列

一一来介绍吧

闭散列

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

那么空位置又如何去找呢？

这里又提供了两种办法

一个是线性探测

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

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

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

这个方法有缺陷，就是产生冲突的数据会堆积在一块。

所以也就引入了第二个办法---二次探测

二次探测：

方法就是

其中的i=1，2，3，4

比如我们拿刚刚发生冲突的场景来说，要插入44，24，34，这些值都要插入下标为4的地方

但已经有值了，所以当插入44时，H0=4，i=1，因为是第一次。

有闭散列，就有开散列咯。

开散列

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

开散列，可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了。

这时候，如若冲突严重的时候，我们还可以将这个所谓的小集合进行转化，例如

1. 每个桶的背后是另一个哈希表

2. 每个桶的背后是一棵搜索树

讲完这些概念，接下来可以来个简易实现它了

首先，很显然我们得把它定义出来

public class HashBuck {
     static class Node{
         public int key;
         public int val;
         public Node next;
         public Node(int key,int val){
             this.key=key;
             this.val=val;
         }
     }
     public Node [] arr;
     public int UsedSize;
    public HashBuck (){
         this.arr=new Node[10];
     }

解释：之前说过，这个哈希桶以数组作为存储的，且数组中每个元素中存放的是链表，同时也定一个Usedsize来记录当前有效元素个数

第一个方法

put

思路：首先设立一个哈希函数来找到存储位置，接着用一个cur去走一个循环，这个循环是用来遍历是否存在这个节点的

当这个节点存在的时候，就要更新下value的值

找到后，就是链表的操作了，链表我们可以使用头插法，也可以使用尾插法。

当我们插了足够多元素发现，已经超出负载因子了，所以这时候就要扩容了。

扩容怎么扩呢？

这个提供的方法，就要重新哈希。因为如若我们在原数组下标4中有4和14，这时候，当我们扩容成两倍后，14就有地方可以放，所以就要重新哈希

当然从新哈希就要新建一个数组啦，然后对每个数组下标中存在的链表进行哈希

上代码：

private double loadFactor=0.75;
public void put(int key,int val){
         //先找到要插入的下标
         int index=key % arr.length;
         Node cur=arr[index];
         //遍历链表是否存在这个节点
         while(cur!=null){
             if(cur.key==key){
                 cur.val=val;
                 return;
             }
             cur=cur.next;
         }
         //采用头插法
         Node node=new Node(key,val);
         node.next=arr[index];
         arr[index]=node;
         UsedSize++;
        //3.超出负载因子就要扩容
         if(localFactorCount()>=loadFactor){
             resize();
         }
     }
     private void resize(){
         Node [] NewArr= new Node[arr.length*2];
         for(int i=0;i
             Node cur=arr[i];
             //遍历当前链表进行重新哈希
             while(cur!=null){
                 int newIndex=cur.key% NewArr.length;
                 //依然采用头插法，先绑定后面，先保存后面的值，否则无法继续哈希
                 Node curN=cur.next;
                 cur.next=NewArr[newIndex];
                 NewArr[newIndex]=cur;
                 cur=curN;
             }
         }
         arr=NewArr;
     }
     private double localFactorCount(){
         return UsedSize*1.0/arr.length;
     }

注意：

我们当然也要定义这个负载因子出来先，超出了，就要扩容。

在扩容方法中，我们之前是对原数组进行操作的，结束后，肯定是要把原数组引用赋值给新的数组，这样才体现扩容和重新哈希。

第二个方法

get

public int get(int key){
         int index=key%arr.length;
         Node node=arr[index];
         while(node!=null){
             //遍历链表是否存在当前值
             if(node.key==key){
                 return node.val;
             }
             node=node.next;
         }
         return -1;
     }

这个，挺简单的，用一个循环，找到了对应key，直接返回对应的值就行了。

完！