1、map&set简介

1.1 概念及场景

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，该类中存储的是结构的键值对，并且K一定是唯一的，不能重复。

2.2 关于Map.Entry的说明

Map.Entry 是Map内部实现的用来存放键值对映射关系的内部类，该内部类中主要提供了的获取，value的设置以及Key的比较方式。

注意：Map.Entry并没有提供设置Key的方法

2.3 Map 的常用方法说明

注意：

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

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

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

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

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

重新插入。

6. TreeMap和HashMap的区别

3. Set 的说明

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

3.1 常见方法说明

注意：

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。

8. TreeSet和HashSet的区别

4. 哈希表

4.1 概念

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

当向该结构中：插入元素，根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放。搜索元素，对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。

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

例如：数据集合{1，7，6，4，5，9}；

哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快，但是如果数字的余数相同的时候就容易产生冲突（都在同一个位置了）

4.2 冲突-概念

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

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

4.3 冲突-避免

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

4.4冲突-避免的方法

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

所以有几种常见的设计哈希函数的方法：

直接定制法–(常用)

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

除留余数法–(常用)

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

还有几种不常用的方法也列举一下：平方取中法，折叠法，随机数法，数学分析法。

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

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

所以当冲突率达到一个无法忍受的程度时，我们需要通过降低负载因子来变相的降低冲突率。

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

4.6 冲突-解决

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

4.7 冲突-解决-闭散列

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

存放到下一个位置有两种方式比较常用：

1. 线性探测

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

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他

元素的搜索。

2. 二次探测

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

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

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

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

链地址法的图示：当有哈希桶在某个下标下，则哈希表对应下标的值为链表头结点的地址，如果没有则为null。每个结点都由key，value与next组成。

因为是用哈希桶来解决冲突，因此要创建一个每个下标底下都是结点组成的链表的数组Node[] array;，并且用size来记录数组中结点的个数，目的是求出负载因子。而每个哈希桶都是由结点组成的，因此结点类可以定义到哈希桶类里面。put、resize方法：先根据设计的哈希函数求出对应的下标，找到对应下标后去遍历该下标的链表，如果已经有相同的key值的结点，则更新完key值中的value后退出。如果没有，则创建一个哈希桶，设置cur结点从头结点开始，用头插法插入新的结点。当然，插入后要计算出负载因子是否超过了0.75，如果超过就扩容。扩容后数组的长度会变长，因此每个哈希桶根据新的哈希函数的计算结果跟原来的不同，则要重新哈希。(resize方法)等全部哈希桶重新哈希完之后，新的数组的引用要赋值给旧的数组的引用。

get方法：首先要根据哈希函数求出对应的下标，再从下标当中去找是否有相同的值的哈希桶，若有，则返回该哈希桶的value值，否则返回-1。

实现代码：

1. // key-value 模型
2. public class HashBucket {
3. private static class Node {
4. private int key;
5. private int value;
6.         Node next;
7. 
8. 
9. public Node(int key, int value) {
10. this.key = key;
11. this.value = value;
12.         }
13.     }
14. 
15. 
16. 
17. private Node[]  array;
18. 
19. public HashBucket() {
20. // write code here
21.         array=new Node[DEFAULT_SIZE];
22.     }
23. 
24. private int size;   // 当前的数据个数
25. private static final double LOAD_FACTOR = 0.75;
26. private static final int DEFAULT_SIZE = 8;//默认桶的大小
27. 
28. public void put(int key, int value) {
29. // write code here
30. //获取下标
31. int index=key%array.length;
32.         Node cur=array[index];
33. //找位置,如果有相同的就覆盖
34. while (cur!=null){
35. if(cur.key==key){
36.                 cur.value=value;
37. return;
38.             }
39.             cur=cur.next;
40.         }
41. //进行插入（头插）
42.         Node head=new Node(key,value);
43.         head.next=array[index];
44.         array[index]=head;
45.         size++;
46. //负载因子大于0.75时扩容
47. if(loadFactor()>=0.75){
48.             resize();
49.         }
50. 
51.     }
52. 
53. 
54. private void resize() {
55. // write code here
56.         Node[]newArray=new Node[2*array.length];
57. //对原array中的每一个数据进行重新哈希
58. for(int i=0;i<array.length;i++){
59.             Node cur=array[i];
60. while(cur!=null){
61.               Node curNext=cur.next; //保存后续结点
62. int newIndex=cur.key%newArray.length;
63.               cur.next=newArray[newIndex];
64.               newArray[newIndex]=cur;
65.               cur=curNext;
66. 
67.             }
68. 
69.         }
70.         array=newArray;//重新赋值
71. 
72. 
73.     }
74. 
75. 
76. private double loadFactor() {
77. return size * 1.0 / array.length;
78.     }
79. 
80. 
81. 
82. public int get(int key) {
83. // write code here
84. int index=key%array.length;
85.         Node cur=array[index];
86. //找位置
87. while (cur!=null){
88. if(cur.key==key){
89. return cur.value;
90.             }
91.             cur=cur.next;
92.         }
93. return -1;
94.     }
95. }

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

一些要注意的点：

1. HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 Set

2. java 中使用的是哈希桶方式解决冲突的

3. java 会在冲突链表长度大于一定阈值后，将链表转变为搜索树（红黑树）

4. java 中计算哈希值实际上是调用的类的 hashCode 方法，进行 key 的相等性比较是调用 key 的 equals 方法。所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值，必须覆写 hashCode 和 equals 方法，而且要做到 equals 相等的对象，hashCode 一定是一致的

5.哈希表查找成功与查找失败的求法

5.1 查找成功的求法

一个哈希表如下图：

假设现在要查找4，则根据哈希函数Hash(key)=key%array.length，找到了4下标，因为4下标下的数据就是4，则查找一次就成功，1和9数据的查找成功次数求法也是一致。

假设此时要查找24，则先根据哈希函数求出下标为4，但是4下标的数据是4，而不是24，算查找一次。此时往后移一个单位，发现是44不是我们查找的24，则算查找第二次。此时再往后移一个单位，发现是24，算是查找的次数是第三次。

因此上图中查找成功的平均查找长度：(1+1+2+3+1)/5=8/5。

如果找9下标的值查找的不是要查找的数据，则返回到0下标开始找，并且找9下标失败后算查找1次。

5.2 查找失败的求法

一个哈希表如下图：

第一次假如找数据1，则根据哈希函数Hash(key)=key%array.length求得下标为1，假设下标1中的数据不是我们找的数据1，算查找失败了一次，则向后移一个单位去找。此时下标2的值为空，则说明查找失败，算查找失败了两次。

假如此时找数据44，根据哈希函数求得下标为4，但此时下标4下的数据不是44，则没有保证在查找成功的前提下去查找。因此向后移一个单位去找，此时发现下标5的数据是44，则查找失败的次数从此时才开始计算。我们还是要假设当前5下标是查找失败的，算查找失败一次，则再向后移一个单位去找。还是一样，假设下标6的值不是44，查找失败，则向后移一个单位去找。到下标7后，发现该下标的数据为空，则肯定是查找失败，这次也算查找一次，因此查找失败的长度加起来一共有三次。

注：查找失败的操作是从真正找到要找的值开始向后找下一个空的地方。