数据结构之Map和Sat

一.Map和Sat的概念

概念: Map和Sat是一种专门用来进行搜索的容器或者数据结构,其具体效率与具体的实例化子类有关.

模型: 模型分为两种分别为:

1. 纯 K 模型,如: 快速查找某个名字在不在通讯录中
2. K–Value模型:,如: 统计文件中每个单词出现的次数，统计结果是每个单词都有与其对应的次数：<单词，单词出现的次数>

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

Map:

Map是一个接口类，该类没有继承自Collection，该类中存储的是结构的键值对，并且K一定是唯一的，不能重复。

Map对应的相关操作:

1. Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap
2. Map中存放键值对的Key是唯一的，value是可以重复的
3. Map中的Key可以全部分离出来，存储到Set中来进行访问(因为Key不能重复)。
4. Map中的value可以全部分离出来，存储在Collection的任何一个子集合中(value可能有重复)。

Set

Set是继承自Collection的接口类，Set中只存储了Key。

Set中对应的相关操作

1. Set 是继承自 Collection 的一个接口类
2. Set 中只存储了 key，并且要求 key一定要唯一
3. Set 的底层是使用 Map 来实现的，其使用 key 与 Object 的一个默认对象作为键值对插入到 Map 中的
4. Set最大的功能就是对集合中的元素进行去重
5. 实现Set接口的常用类有 TreeSet 和 HashSet，还有一个LinkedHashSet， LinkedHashSet 是在 HashSet 的基础
   上维护了一个双向链表来记录元素的插入次序。
6. Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入
7. Set中不能插入 null 的 key。

总共会出现 4 中情况 , 分别是: HashMap , HashSet , TreeMap , TreeSet.

二.TreeMap 和 TreeSet 的相关操作

1.TreeMap 的部分相关操作

put 方法

put 方法是将元素进行存放的方法.

代码如下:

        public static void main(String[] args) {
            Map<String,Integer> map = new TreeMap<>();
            map.put("hello",2);
            map.put("abc",4);
            System.out.println(map);
        }
1
2
3
4
5
6

put 方法在 TreeMap 底层中会对元素的 key 值进行比较 , 必须存储可以比较的元素 , 然后进行存储 , 因此结果如下:

get 方法

get 方法是用来获取元素 key 值对应的 value 的方法

代码如下：

        public static void main(String[] args) {
            Map<String,Integer> map = new TreeMap<>();
            map.put("hello",2);
            map.put("abc",4);

            int val = map.get("hello");
            System.out.println(val);
        }
1
2
3
4
5
6
7
8

getOrDefault(Object key, V defaultValue) 方法

这个方法是指当要查找的元素不存在时 , 将会输出自己设定的值.

代码如下

        public static void main(String[] args) {
            Map<String,Integer> map = new TreeMap<>();
            map.put("hello",2);
            map.put("abc",4);
            
            //这里 hello2 并没有在 put 中进行定义
            int val = map.getOrDefault("hello2",1000);
            System.out.println(val);
        }
1
2
3
4
5
6
7
8
9

Set< K > keySet()

keySet 方法是存储的元素中的 key 值提取出来进行展示

代码如下:

        public static void main(String[] args) {
            Map<String,Integer> map = new TreeMap<>();
            map.put("hello",2);
            map.put("abc",4);

            System.out.println("取出key的值,进行组织");

            Set<String> set = map.keySet();
            System.out.println(set);
        }
1
2
3
4
5
6
7
8
9
10

Collection< V > values()

Collection 方法是将存储的元素对应的 value 值进行组织并展示.

代码实现

        public static void main(String[] args) {
            Map<String,Integer> map = new TreeMap<>();
            map.put("hello",2);
            map.put("abc",4);

            int val = map.getOrDefault("hello2",1000);

            Set<String> set = map.keySet();

            Collection<Integer> collection = map.values();
            System.out.println(collection);
        }
1
2
3
4
5
6
7
8
9
10
11
12

Set> entrySet()

Entry 这个方法比较特殊 , 如图所示:

我们已知 , 存放的元素由两部分组成 , 这个方法是通过设定一个范围 (类似于一个大水池) , 将存入的元素无规律存放到这个范围之中(类似于水池中的鱼).

代码如下:

        public static void main(String[] args) {
            Map<String,Integer> map = new TreeMap<>();
            map.put("hello",2);
            map.put("abc",4);

            //在这里被存储的元素两个值可以看做为Map.Entry这样一个整体类型
            Set<Map.Entry<String,Integer>> entries = map.entrySet();

			//需要运用到for循环来进行遍历
            for (Map.Entry<String,Integer> entry:entries) {
                System.out.println("key: " + entry.getKey() + " value: "+ entry.getValue());
            }
       }
1
2
3
4
5
6
7
8
9
10
11
12
13

2.TreeSet 的部分相关操作

add 方法

重复元素不能被添加成功 , 重复元素只能添加一个.

添加的元素 key 值 , 必须是可比较的元素

代码如下:

    public static void main(String[] args) {
         TreeSet<String> set = new TreeSet<>();
         set.add("hello");
         set.add("world");
         set.add("hello");
        System.out.println(set);
    }
1
2
3
4
5
6
7

注: 以本方法为例 , 解释不能重复存储相同元素的原因. 如图:

contains 方法

该方法是用来判断元素是否在表内 如果存在就会返回 boolern 类型

代码如下

    public static void main(String[] args) {
         TreeSet<String> set = new TreeSet<>();
         set.add("hello");
         set.add("world");

        System.out.println(set.contains("hello"));
    }
1
2
3
4
5
6
7

其余方法的实现相对较好理解 , 就不进行多余解释.

三. 哈希表

1.哈希表的概念

最理想的搜索方法 , 即就是在查找某元素时 , 不进行任何比较的操作 , 一次直接查找到需要搜索的元素 , 可以达到这种要求的方法就是哈希表.

哈希表就是通过构造一种存储结构 , 通过某种函数使元素存储的位置与其关键码位形成一 一映射的关系 , 这样在查找元素的时候就可以很快找到目标元素.

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

例如:

存在一个数组集合 {1，7，6，4，5，9}.
哈希函数设置为：hash(key) = key % capacity;
capacity 为存储元素底层空间总的大小。

如图所示: 这样存储数据更加便于查找

但是 , 不难发现 , 这样存储的缺陷十分明显 , 假设插入元素 44 这样就会出现很明显的问题.

2.哈希表中存在的问题

这里我们就可以提出一个新的概念 ---- 冲突
即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

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

常见的哈希函数:

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

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

冲突避免 ---- 负载因子调节

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

负载因子和冲突率的关系粗略演示

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

3.冲突解决----闭散列

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

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

如图所示:

这里要插入 44 这样的话就与 4 发生了冲突,通过线性探测找到在 8 下标中的空位,将元素存入其中.

注意: 在这里要实现删除比较麻烦 , 不能随便删掉其中的元素 , 。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素.

这样一来就不难发现 , 闭散列的存储对于空间的利用率较低 , 这也就是哈希的缺陷.

4.冲突解决 ---- 开散列 / 哈希桶

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

如图所示:

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

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

所以 , hash 表 就是一个数组+链表的结构 , 随着数据的增多 , 最终 , 链表会变成红黑树的结构

总结: Hash 和 Tree 的用法基本相同 , 在 HashMap 中添加元素时 在底层中不需要进行元素的比较 , 除此之外一些性质基本上完全相同,如图: