【HashMap和HashSetyi以及散列表的拉链法，线性探测法详解】

个人主页：SKY-30
个人推荐：基于java提供的ArrayList实现的扑克牌游戏 |C贪吃蛇详解
学好数据结构，刷题刻不容缓：点击一起刷题
心灵鸡汤：总有人要赢，为什么不能是我呢

Map 和Set 概念

map和set是一种用来搜索的数据结构，其搜索效率与具体实例化的子类有关，之前我们搜索的方法有：

• 直接遍历：利用for循环，暴力求解，事件复杂度为O(N)
• 二分查找：时间复杂度：O(logN),搜索之前要求序列是有序的

但是如果我们对于存储的数据，经常要执行修改和删除的操作，那么上述的两种操作就非常不适合了，我们这里就引出两个新的数据结构-map和set。

模式

对于map来说，它的存储形式是形如K-（key），V-（value），这种类似于键值对的这种形式，进行存储，而set，则是只有key这一种形式。

Map

Map是一个接口，没有继承collection，该类的存储形式是<K,V>并且这里的K是唯一的，不能重复。

Map.Entry<K,V>

Map.Entry<K,V>是Map内部用来存放<key,value>键值对的映射关系的一个内部类，该类提供了<Key,value>获取，value的设置，即Key的比较形式

Map的一些常用方法

Map的一些注意事项

• Map是一个接口，不能直接实例化对象，如果要实例化，我们只能实例实现其接口的类，TreeMap和HashMap。
• Map中Key的元素是唯一的，Value可以重复的
• 在Treemap中插入元素时，Key不能为空，否则会报错，value却可以为空，需要注意在HashMap中是可以插入为空的
• Map中的Key是不能修改的，要想修改的话，只能删除对应的数据，然后重新插入，但是Value是可以重新修改的。
• Treemap和HashMap的区别，这个后面说

import java.util.TreeMap;
import java.util.Map;
public static void TestMap(){
Map<String, String> m = new TreeMap<>();
// put(key, value):插入key-value的键值对
// 如果key不存在，会将key-value的键值对插入到map中,返回null
m.put("林冲", "豹子头");
m.put("鲁智深", "花和尚");
m.put("武松", "行者");
m.put("宋江", "及时雨");
String str = m.put("李逵", "黑旋风");
System.out.println(m.size());
System.out.println(m);
// put(key,value): 注意key不能为空，但是value可以为空
// key如果为空，会抛出空指针异常
//m.put(null, "花名");
str = m.put("无名", null);
System.out.println(m.size());
// put(key, value):
// 如果key存在，会使用value替换原来key所对应的value，返回旧value
str = m.put("李逵", "铁牛");
// get(key): 返回key所对应的value
// 如果key存在，返回key所对应的value
// 如果key不存在，返回null
System.out.println(m.get("鲁智深"));
System.out.println(m.get("史进"));
//GetOrDefault(): 如果key存在，返回与key所对应的value，如果key不存在，返回一个默认值
System.out.println(m.getOrDefault("李逵", "铁牛"));
System.out.println(m.getOrDefault("史进", "九纹龙"));
System.out.println(m.size());
//containKey(key)：检测key是否包含在Map中，时间复杂度：O(logN)
// 按照红黑树的性质来进行查找
// 找到返回true，否则返回false
System.out.println(m.containsKey("林冲"));
System.out.println(m.containsKey("史进"));
// containValue(value): 检测value是否包含在Map中，时间复杂度: O(N)
// 找到返回true，否则返回false
System.out.println(m.containsValue("豹子头"));
System.out.println(m.containsValue("九纹龙"));
// 打印所有的keyfor(String s : m.keySet()){
System.out.print(s + " ");
}
System.out.println();
// 打印所有的value
// values()是将map中的value放在collect的一个集合中返回的
for(String s : m.values()){
System.out.print(s + " ");
}
System.out.println();
// 打印所有的键值对
// entrySet(): 将Map中的键值对放在Set中返回了
for(Map.Entry<String, String> entry : m.entrySet()){
System.out.println(entry.getKey() + "--->" + entry.getValue());
}
System.out.println();
}
// keySet是将map中的key防止在Set中返回的

}

Set-详解

Set与Map很大的一个不同就是Set继承了collection而map并没有。

一些常见的方法

针对Set的一些注意事项

• Set是继承了collection的一个接口类
• Set中只存储了Key，并且要求他是唯一的，不能重复
• Set的最大的一个特点就是对数据去重。
• 实现Set接口的两个常见的类是HashSet和Treemap
• TreeSet中的key不能插入null,HashSet则可以插入null
• 在这里插入代码片

import java.util.TreeSet;
import java.util.Iterator;
import java.util.Set;
public static void TestSet(){
Set<String> s = new TreeSet<>();
// add(key): 如果key不存在，则插入，返回ture
// 如果key存在，返回false
boolean isIn = s.add("apple");
s.add("orange");
s.add("peach");
s.add("banana");
System.out.println(s.size());
System.out.println(s);

boolean isIn= s.add("apple");
// add(key): key如果是空，抛出空指针异常
//s.add(null);
// contains(key): 如果key存在，返回true，否则返回false
System.out.println(s.contains("apple"));
System.out.println(s.contains("watermelen"));
// remove(key): key存在，删除成功返回true
// key不存在，删除失败返回false
// key为空，抛出空指针异常
s.remove("apple");
System.out.println(s);
s.remove("watermelen");
System.out.println(s);
Iterator<String> it = s.iterator();
while(it.hasNext()){
System.out.print(it.next() + " ");
}
System.out.println();
}

哈希表

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

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

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

冲突

不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
如何解决哈希碰撞呢，这里几种不同的方法给大家具体说明一下。

解决哈希冲突的及汇总方法

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。 哈希函数设计原则：哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间哈希函数计算出来的地址能均匀分布在整个空间中哈希函数应该比较简单

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

除此之外，我们还发现哈希冲突与负载因子有关，所以如何利用负载因子降低冲突率呢，首先负载因子的计算公式是：填入表中的数据的个数/散列表的长度

由于我们无法改变插入表中的数据，所以我们只能改变表的长度了。

冲突-解决-闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以
把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢？
这里我们介绍一种比较常见的方法

线性探测
比如，现在需要插入元素44，先通过哈希函数计算哈希地址，下标为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

但是线性探测这种方法，存在一定的问题，比如他会导致数据全部聚集在同一块区域，导致我们后面插入数据的时候，可能要讲过多次的查找操作，所以，我们为了解决这个问题，发明了另一种探测方法。

二次探测
相比与线性探测，二次探测通过制定的函数，可以将数据均匀的插入到数组当中，避免数据扎堆的情况。
找下一个空位置的方法为： H= (H0 +i*i )% m, 其中：i = 1,2,3…， 是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，
m是表的大小。

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

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

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

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

// key-value 模型
public class HashBucket {
private static class Node {
private int key;
private int value;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
比特就业课
}
private Node[] array;
private int size; // 当前的数据个数
private static final double LOAD_FACTOR = 0.75;
public int put(int key, int value) {
int index = key % array.length;
// 在链表中查找 key 所在的结点
// 如果找到了，更新
// 所有结点都不是 key，插入一个新的结点
for (Node cur = array[index]; cur != null; cur = cur.next) {
if (key == cur.key) {
int oldValue = cur.value;
cur.value = value;
return oldValue;
}
}
Node node = new Node(key, value);
node.next = array[index];
array[index] = node;
size++;
if (loadFactor() >= LOAD_FACTOR) {
resize();
}
return -1;
}
private void resize() {
Node[] newArray = new Node[array.length * 2];
for (int i = 0; i < array.length; i++) {
Node next;
for (Node cur = array[i]; cur != null; cur = next) {
next = cur.next;
int index = cur.key % newArray.length;
cur.next = newArray[index];
newArray[index] = cur;
}
}
array = newArray;
}
private double loadFactor() {
return size * 1.0 / array.length;
}
public HashBucket() {
array = new Node[8];
size = 0;
}
public int get(int key) {
int index = key % array.length;
Node head = array[index];
for (Node cur = head; cur != null; cur = cur.next) {
if (key == cur.key) {
return cur.value;
}
}
return -1;
}
}

关于HashMap和HashSet的注意事项

1. HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 Set
2. java 中使用的是哈希桶方式解决冲突的
3. java 会在冲突链表长度大于一定阈值后，将链表转变为搜索树（红黑树）
4. java 中计算哈希值实际上是调用的类的 hashCode 方法，进行 key 的相等性比较是调用 key 的 equals 方法。所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值，必须覆写 hashCode 和 equals 方
   法，而且要做到 equals 相等的对象，hashCode 一定是一致的。