数据结构（Java）：Map集合Set集合哈希表

目录

1、介绍

1.1 Map和Set

1.2 模型

2、Map集合

2.1 Map集合说明

2.2 Map.Entry<K，V>

2.3 Map常用方法

2.4 Map注意事项及实现类

 3、Set集合

3.1 Set集合说明

 3.2 Set常用方法

 3.3 Set注意事项及其实现类

4、TreeMap&TreeSet

4.1 集合类TreeMap（Key-Value模型）

4.1.1 底层结构

4.2 集合类TreeSet（纯Key模型）

4.2.1 底层结构

4.3 TreeMap与TreeSet之间的关系

4.3.1 再谈TreeSet之构造方法

 4.3.2 再谈TreeSet之add方法

4.4 TreeMap&TreeSet总结

 5、哈希表

5.1 概念

5.2 冲突-概念

5.2 冲突-避免

5.2.1 设计合理的哈希函数

 5.2.2 调节负载因子

5.3 冲突-解决

5.3.1 闭散列

 5.3.2 🌟开散列/哈希桶/开链法

5.4 HashMap&HashSet

5.4.1 hashCode与equals方法

5.5 性能分析

5.6 总结

---

1、介绍

1.1 Map和Set

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

Map和Set能够在查找时进行一些插入和删除的操作，即动态查找。

1.2 模型

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

1. 纯Key模型：数据仅包含关键字。
2. Key-Value模型：数据除关键字外，还有关键字所对应的值。例如：统计文件中每个单词出现的次数，统计结果是每个单词都有与其对应的次数：<单词，单词出现的次数>。

 Map集合是Key-Value模型；而Set集合是纯Key模型。

---

2、Map集合

2.1 Map集合说明

Map是一个接口类，该接口没有继承自Collection，是一个单独的接口，为Key-Value模型，存储的是<K，V>结构的键值对，并且K一定是唯一的，不能重复。  （K不可重复，V可重复）

2.2 Map.Entry<K，V>

Entry是Map接口的一个内部接口，是用来存放<Key，Value>键值对映射关系的内部接口。

内部接口Map.Entry<K，V>主要提供了<Key，Value>的获取，Value的设置以及Key的比较方式。

注意：Map.Entry<K，V>并没有提供设置Key的方法 ！！！Key无法修改！！！

同样，实现Map接口的类也需要实现Entry接口：

这里以TreeMap的内部类Entry为例，Entry实现了的Map.Entry接口，而Entry就相当于我们之前所学二叉树的一个节点TreeNode。

TreeMap的底层是一个红黑树（下文详解），TreeMap的内部类Entry就相当于红黑树的一个节点，有key、value等属性。

2.3 Map常用方法

 演示如下：

若我们使用get方法来获取一个不存在的key的value值时，返回的value为null，

所以当value为Integer类型时，最好使用包装类Integer接收，若使用int基本类型接收会自动拆箱，可能抛出空指针异常：

需要注意的是keySet、values、entrySet方法：

• keySet，可以将key值放在Set集合中，返回Set集合；
• values，可以将value值放在Collection集合中，返回Collection集合；
• entrySet，可以将key-value映射关系放在Set集合中，返回Set集合。

注意：Map系列集合是不能用迭代器实现遍历的，若想使用迭代器遍历，需要使用keySet、values、entrySet方法转换为Set集合，再使用迭代器遍历！！！

2.4 Map注意事项及实现类

1. Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap
2.  Map中存放键值对的Key不能重复，value是可以重复的
3. 在TreeMap中插入键值对时，key不能为空，否则就会抛NullPointerException异常，value可以为空。（TreeMap底层是一颗红黑树，涉及key之间的比较）
4. HashMap的key和value都可以为空。
5. Map中的Key可以全部分离出来，存储到Set中来进行访问(Key不能重复)。
6. Map中的value可以全部分离出来，存储在Collection的集合中，若存储在其子集中则强转为Collection(value可以有重复)。
7. Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入。 
8. TreeMap和HashMap是实现Map的集合类

 TreeMap与HashMap：

下文细讲TreeMap与HashMap。 

---

 3、Set集合

3.1 Set集合说明

Set集合是纯Key模型，也就是说，Set只存储了Key。

Set集合中的Key值也不能重复存在，能够达到天然去重的效果。

Set与Map主要的不同有两点：

1. Set是继承自Collection的接口类。
2. Set是纯Key模型，只存储了Key。

 3.2 Set常用方法

因为Set是是继承自Collection的接口类，所以其方法很多与我们之前学的Collection接口下的类是相同的，这里不再赘述。

需要注意的是：

• 如果将其他集合的元素添加到Set集合中，可以到达天然去重的效果；
• Set集合可以使用迭代器遍历；

 3.3 Set注意事项及其实现类

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

 TreeSet与HashSet：

---

4、TreeMap&TreeSet

 为什么要将TreeMap和TreeSet放到一起说呢？因为这两者间是有关系的。

4.1 集合类TreeMap（Key-Value模型）

4.1.1 底层结构

TreeMap是Map集合下的一个集合类，底层是一颗红黑树，红黑树是一颗二叉搜索树，所以其Key值必须具备可比较功能。

也就是说，如果其Key是自定义类型，则这个自定义类必须实现Comparable接口或者给TreeMap的构造方法提供比较器。

 因为TreeMap底层为红黑树，故其插入删除查找元素的时间复杂度为O（logN）

4.2 集合类TreeSet（纯Key模型）

4.2.1 底层结构

TreeSet是Set集合下的一个集合类，底层也是一颗红黑树，红黑树是一颗二叉搜索树，所以其Key值也必须具备可比较功能。

故，TreeSet插入删除查找元素的时间复杂度也为O（logN）

同样，如果其Key是自定义类型，则这个自定义类必须实现Comparable接口或者给TreeSet的构造方法提供比较器。

4.3 TreeMap与TreeSet之间的关系

虽然TreeMap是Map下的集合，TreeSet是Set下的集合，

但是细心的小伙伴已经发现，TreeMap和TreeSet的底层结构不仅都是红黑树，而且他们的Key值都不能重复出现，那么他们之间是不是有什么关系呢？

没错，其实TreeSet的底层是使用TreeMap来实现的。

可是为什么呢？接下来，让我们从TreeSet的源码中找到原因。

4.3.1 再谈TreeSet之构造方法

我们可以看到，当我们调用TreeSet的无参构造方法创建TreeSet对象时，其实是创建了一个TreeMap对象并传给了带一个参数的构造方法，并用NavigableMap类型的成员变量m将这个TreeMap对象引用起来。

而NavigableMap是什么呢，我们点过去后发现是一个接口，并且拓展了SortedMap接口，而我们发现SortedMap接口拓展了Map接口。

我们再观察TreeMap，发现TreeMap实现了NavigableMap接口。

所以，其实TreeMap有着下图的实现结构：

也就是说NavigableMap可以用来接收TreeMap对象实现向上转型，同时也说明，当我们实例化一个TreeSet对象时，实际上创建的是一个TreeMap对象。

也就是说，TreeSet的底层其实就是TreeMap！！！

 4.3.2 再谈TreeSet之add方法

因为TreeSet的底层是TreeMap，所以添加元素add时，实际上调用的是TreeMap的put方法，而其value值是PRESENT，而PRESENT永远都是一个Object对象。 

 

所以，不管add的Key是什么东西，其value值永远都是一个Object对象。

4.4 TreeMap&TreeSet总结

•  TreeMap底层是一颗红黑树，二叉搜索树。
• TreeSet的底层是TreeMap，所以TreeSet也是一颗红黑树，二叉搜索树。
• TreeSet的底层是TreeMap，所以其Key不可重复，具有Map的去重功能。

---

 5、哈希表

5.1 概念

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

而哈希表可以通过哈希函数使元素的存储位置与它的关键码之间能够建立一一映射的关系，不经过任何比较，一次直接从表中得到要搜索的元素。

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

插入元素：

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

查找元素：

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

哈希表 插入/删除/查找操作的时间复杂度为 O（1）。

5.2 冲突-概念

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

 把具有不同关键码而具有相同哈希地址的数据元素称为"同义词"。

 由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的，

这就导致一个问题：冲突的发生是必然的，但我们能做的应该是尽量的降低冲突率

5.2 冲突-避免

避免冲突有两个办法，一个是设计合理的哈希函数，一个是调节负载因子。

5.2.1 设计合理的哈希函数

哈希函数设计原则：

1. 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
2. 哈希函数计算出来的地址能均匀分布在整个空间中
3. 哈希函数应该比较简单

常见哈希函数：

 注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

在实际应用中，其实也轮不到我们来设计哈希函数...hhh😂

 5.2.2 调节负载因子

负载因子的计算公式为：负载因子 = 已有键值对数量 / 散列表容量。

它表示在散列表中，当插入一个新的键值对时，可以允许的最大填充程度。

负载因子越大，散列表的填充程度越高，冲突的发生率越高。相反，负载因子越小，散列表的填充程度越低，插入和查找操作的性能可能会更好，冲突的发生率越低，但空间利用率会降低。

因为我们不能降低元素填入个数，所以我们只能扩容哈希表来降低冲突率。

当元素个数和散列表容量的比值接近或等于负载因子时，就要对哈希表进行扩容操作。

换句话说，哈希表就是以空间换取时间的一种数据结构。

Java中，定义的负载因子大小为0.75。

5.3 冲突-解决

我们知道，冲突的发生是必然的，那么，当冲突发生后，我们该如何做呢？

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

5.3.1 闭散列

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

找"下一个”"空位置，有两种方法： 

• 线性探测法：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。（线性探测的缺陷是产生冲突的数据堆积在一块）
• 二次探测法：采用移动数值的平方次来找空位置。例如：如果键15的哈希值对应的空间已经被占用，算法可能会尝试使用平方数序列（如1^2， -1^2， 2^2， -2^2， ...）来计算新的哈希值，直到找到一个空位置为止。这种方法有助于避免哈希表中数据的聚集，提高哈希表的性能和数据的均匀分布。‌

 5.3.2 🌟开散列/哈希桶/开链法

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

拉链法解决冲突的特点：

1. 将所有关键字为同义词的结点链接在同一个单链表中。
2. 拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短。

即 数组+链表模式：

也就是说，开散列中每个桶中放的都是发生哈希冲突的元素。

HashMap采用的就是开散列法解决冲突。

但是当冲突严重时，链表的长度就会过于长，这样会影响搜索性能，

在Java中，当 数组长度超过64 && 链表长度超过8 ，链表就会转化为红黑树。

5.4 HashMap&HashSet

5.4.1 hashCode与equals方法

• hashCode方法的作用是生成哈希值，通过哈希值计算出key在数组中的位置下标。
• equals方法的作用是判断，两个key的内容是否相等。

例如：在使用put或者getValue方法时，通过hashCode找到元素的位置下标后，还需要使用equals方法一个一个的和链表中的元素比较，找到该元素在链表中的具体位置，若equals为true，说明找到了该元素。

故：当哈希表中的key为自定义类时，一定要重写equals和hashCode方法！！！ 

注意：

1. 若两个key通过equals比较结果为true，说明两个key的内容相同，说明通过hashCode得到的哈希值一定是相等的；
2. 但是，若两个key 通过hashCode得到的哈希值相等，那么只能说明这两个key在数组中的位置是相同的，不能说明两个key的内容相同，也就是说equals可能为true也可能为flase。

总结：如果equals为true，那么hashCode出的哈希值一定相等； 如果hashCode出的哈希值相等，那么equals不一定为true！！！

5.5 性能分析

虽然哈希表一直在和冲突做斗争，但在实际使用过程中，我们认为哈希表的冲突率是不高的，冲突个数是可控的， 也就是每个桶中的链表的长度是一个常数，所以，通常意义下，我们认为哈希表的插入/删除/查找时间复杂度是 O(1) 。

5.6 总结

1. HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 Set
2. HashMap 和 HashSet 中使用的是 哈希桶/开散列 方式解决冲突的
3. java 会在冲突链表长度大于一定阈值后，将链表转变为搜索树（红黑树）
4. java 中计算哈希值实际上是调用的类的 hashCode 方法，进行 key 的相等性比较是调用 key 的 equals 方法。所以如果要用自定义类作 HashMap 的key值或者 HashSet 的key值，必须重写 hashCode 和 equals 方法。
5. equals 相等的对象，hashCode 一定是一致的。
6. hashCode一致，equals不一定相等。
7. HashMap和HashSet不涉及元素之间的比较，所以不用像TreeMap或TreeSet具备可比较功能。