什么是 Map
在数据结构中,Map 是一种关联容器,它存储了键值对(key-value pairs),并且每个键在 Map 中都是唯一的。Map 提供了通过键快速访问其对应值的能力。简单来说,记录两个不同类型的值,一个被定义为键(Key),一个被定义为值(value),其中 Key 是唯一的,也就是说在 Map 中的 Key 是不允许重复出现的,但 value 是可以的。
Map 的作用
Map 的用途比较广泛,常见的包括:
- 缓存:Map 可以用来实现缓存系统,其中键是请求的标识符,值是请求的结果。
- 计数器:Map 可以用来计数,例如统计文本中每个单词的出现次数。
- 数据库索引:Map 可以用于实现数据库索引。
- 查找表:Map 可以作为查找表,例如汇率转换。
- 配置存储:Map 可以用来存储配置信息。
- 对象属性存储:在某些情况下,Map 可以用来存储对象的属性。
- 会话管理:在 Web 应用程序中,Map 可以用来存储用户会话信息。
- 唯一性检查:Map 可以用来检查数据的唯一性。
- 多键查找:Map 可以用于需要根据多个键查找数据的场景。
- 状态管理:在某些应用程序中,Map 可以用来管理应用程序的状态。
- 路由表:在网络编程中,Map 可以用于实现路由表。
- 依赖注入:在依赖注入框架中,Map 可以用来存储依赖项。
- 国际化:Map 可以用于实现国际化。
- 权限控制:Map 可以用于权限控制。
- 对象池:Map 可以用于实现对象池。
Map 的接口操作
在 Java 中,Map 是一个接口,它定义了映射的基本操作。Map 接口的实现类,如 HashMap、TreeMap 和 LinkedHashMap。
了解 Map.Entry
Map.Entry 是 Map 内部实现的用来存放键值对映射关系的内部类,该内部类中主要提供了获取 key、value 的设置以及 key 的比较方式。
K getKey():返回 entry 中的 key。
V getValue():返回 entry 中的 value。
V setValue(V value):将键值对中的 value 替换为指定 value。
基本方法
- put(K key, V value):将指定的值与此 Map 的指定键关联。
- get(Object key):返回指定键所映射的值。
- remove(Object key):如果存在一个键的映射关系,则将其从 Map 中移除。
- containsKey(Object key):如果 Map 包含指定的键,则返回
true。
- containsValue(Object value):如果 Map 包含指定的值映射,则返回
true。
- keySet():返回 Map 中包含的键的 Set 视图。
- values():返回 Map 中包含的值的 Collection 视图。
- entrySet():返回 Map 中包含的键值映射关系的 Set 视图。
- isEmpty():如果 Map 为空,则返回
true。
- size():返回 Map 中键值映射关系的数目。
示例代码
import java.util.HashMap;
import java.util.Map;
public class MapExample {
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
map.put("cherry", 3);
System.out.println("Get value for 'apple': " + map.get("apple"));
System.out.println("Contains 'banana': " + map.containsKey("banana"));
System.out.println("Values: " + map.values());
System.out.println("Entry Set: " + map.entrySet());
System.out.println("Key Set: " + map.keySet());
map.remove("cherry");
System.out.println("After removing 'cherry': " + map);
}
}
TreeMap 实现 Map
要想了解如何用树实现 Map,现在必须认识二叉搜索树。因为 TreeMap 就是利用二叉搜索树来实现的。
二叉搜索树
- 节点的左子树只包含小于当前节点的键。
- 节点的右子树只包含大于当前节点的键。
- 左子树和右子树也必须分别为二叉搜索树。
通俗点来说,这颗树的每个节点的左树都比自身节点小,右树都比自身节点大。
我们主要模拟实现插入,搜索,移除接口。
搜索接口(search)
解析:从根节点出发,对比当前 cur 节点的 key 与目标 key 的大小,如果 cur.key > key,那么就往左遍历,要是小于就往右走,直到相等,即找到对应的节点了,返回该节点即可。如果遍历完毕还是没有找到就返回 null。
public Node search(int key) {
Node cur = root;
while (cur != null) {
if (cur.key == key) {
return cur;
} else if (cur.key > key) {
cur = cur.left;
} else {
cur = cur.right;
}
}
return null;
}
插入接口(insert)
解析:类似搜索,不断对比 cur.key 与 key 的大小,不断遍历到最后一个叶子节点(左右孩子都为 null),然后 new 一个节点值为 key,最后判断 cur.key 与 key 的大小,决定新插入的节点是放在左边还是右边。
public boolean insert(int key) {
if (root == null) {
root = new Node(key);
return true;
}
Node cur = root;
Node parent = null;
while (cur != null) {
if (key == cur.key) {
return false;
} else if (key < cur.key) {
parent = cur;
cur = cur.left;
} else {
parent = cur;
cur = cur.right;
}
}
Node node = new Node(key);
if (key < parent.key) {
parent.left = node;
} else {
parent.right = node;
}
return true;
}
移除接口(remove)
最难的接口其实是删除接口。解析:首先找到要删除的节点,要是没找到直接返回 false 即可。找的时候也要建一个变量 prev 来记录其父节点。这里采用的是替换删除法,选择另一个合适的节点来替换掉它,使得树还是一颗二叉搜索树。通常找要删除节点的左孩子的最右的那个节点。
当然这样删除时需要注意三种情况:
- 要删除的节点左孩子为 null。
- 要删除节点的左孩子的右孩子为 null。
- 正常情况。
public boolean remove(int key) {
Node cur = root;
Node prev = null;
while (cur != null) {
if (cur.key == key) {
break;
} else if (cur.key > key) {
prev = cur;
cur = cur.left;
} else {
prev = cur;
cur = cur.right;
}
}
if (cur == null) return false;
Node tail = cur.left;
if (tail == null) {
if (prev.right == cur) {
prev.right = cur.right;
return true;
} else {
prev.left = cur.right;
return true;
}
}
if (tail.right == null) {
cur.key = tail.key;
cur.left = null;
return true;
}
while (tail.right != null) {
prev = tail;
tail = tail.right;
}
cur.key = tail.key;
prev.right = null;
return true;
}
性能分析
最优情况下,二叉搜索树为完全二叉树,其平均比较次数为 log2N。最差情况下,二叉搜索树退化为单支树,其平均比较次数为 2/N。
TreeMap 方法
我们的 TreeMap 就是利用二叉搜索树来进行的,不过时优化过二叉搜索树,也就是红黑树。我们现在暂时还不需要了解太多,知道普通二叉搜索树即可。上面模拟的时候 key 是 int 类型,但最开始我们讲过其实 key 是 Map.Entry<K,V> 内部类类型的。我们只是为了了解一下二叉搜索树才将 key 设置为 int。
那么二叉搜索树在插入时我们也知道我们需要不断进行比较才能插入数据,所以我们在使用 TreeMap 实现的 Map 时我们就必须将我们传入的 K 类必须是可比较的,即实现 Comparable 接口的。
public static void TestMap() {
Map<String, String> m = new TreeMap<>();
m.put("林冲", "豹子头");
m.put("鲁智深", "花和尚");
m.put("武松", "行者");
m.put("宋江", "及时雨");
String str = m.put("李逵", "黑旋风");
System.out.println(m.size());
System.out.println(m);
str = m.put("无名", null);
System.out.println(m.size());
str = m.put("李逵", "铁牛");
System.out.println(m.get("鲁智深"));
System.out.println(m.get("史进"));
System.out.println(m.getOrDefault("李逵", "铁牛"));
System.out.println(m.getOrDefault("史进", "九纹龙"));
System.out.println(m.size());
System.out.println(m.containsKey());
System.out.println(m.containsKey());
System.out.println(m.containsValue());
System.out.println(m.containsValue());
(String s : m.keySet()) {
System.out.print(s + );
}
System.out.println();
(String s : m.values()) {
System.out.print(s + );
}
System.out.println();
(Map.Entry<String, String> entry : m.entrySet()) {
System.out.println(entry.getKey() + + entry.getValue());
}
System.out.println();
}
HashMap 实现 Map
顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较。顺序查找时间复杂度为 O(N),平衡树中为树的高度,即 O(log2N),搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素。如果构造一种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么在查找时通过该函数可以很快找到该元素。
当向该结构中:
- 插入元素:根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放。
- 搜索元素:对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键码相等,则搜索成功。
该方式即为哈希 (散列) 方法,哈希方法中使用的转换函数称为哈希 (散列) 函数,构造出来的结构称为哈希表 (Hash Table)(或者称散列表)。
例如:数据集合{1,7,6,4,5,9};哈希函数设置为:hash(key) = key % capacity; capacity 为存储元素底层空间总的大小。
冲突
什么是冲突呢?对于两个数据元素的关键字 k1 和 k2 (k1!=k2),有 Hash(k1) != Hash(k2),但有:Hash(k1) == Hash(k2),即:不同关键字通过相同哈希函数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞。
注意:冲突无法避免,我们可以减少冲突的发生。也可以解决冲突所带来的问题。
如何减少冲突发生
一、哈希函数的优化
- 直接定制法(常用):取关键字的某个线性函数为散列地址:Hash(Key) = A*Key + B。优点:简单、均匀。缺点:需要事先知道关键字的分布情况。使用场景:适合查找比较小且连续的情况。
- 除留余数法(常用):设散列表中允许的地址数为 m,取一个不大于 m,但最接近或者等于 m 的质数 p 作为除数,按照哈希函数:Hash(key) = key % p (p<=m),将关键码转换成哈希地址。
- 平方取中法 (了解):假设关键字为 1234,对它平方就是 1522756,抽取中间的 3 位 227 作为哈希地址。
- 折叠法(了解):折叠法是将关键字从左到右分割成位数相等的几部分 (最后一部分位数可以短些),然后将这几部分叠加求和,并按散列表表长,取后几位作为散列地址。
- 随机数法 (了解):选择一个随机函数,取关键字的随机函数值为它的哈希地址,即 H(key) = random(key)。
二、负载因子的调节(重点掌握)
在哈希表中,负载因子(Load Factor)是一个重要的概念,它用来衡量哈希表中已存储元素的密度。具体来说,负载因子是已存储元素的数量与哈希表的容量之间的比率。
定义: Load Factor = n / m
- n 是哈希表中已存储的元素数量。
- m 是哈希表的总容量(即桶的数量)。
重要性:
- 查找效率:较低的负载因子(例如,< 0.7)通常意味着较少的碰撞,这样查找操作的效率较高。较高的负载因子(例如,> 0.7)可能导致更多的碰撞,从而降低查找效率。
- 扩展与收缩:当负载因子超过某个阈值时(如 0.7),许多哈希表实现会自动扩展哈希表的容量,以减少碰撞的发生。这通常会涉及到重新哈希,即将现有的元素重新分配到新的桶中。
- 内存使用:负载因子越高,内存利用率越高,但性能可能下降。反之,负载因子较低时,虽然性能更好,但可能会浪费内存。
如何选择负载因子:如果频繁插入和删除操作,可能希望使用较低的负载因子,以保持较高的查找性能。如果内存资源有限,可以接受较高的负载因子,以节省内存。一般情况我们都是选择负载因子为 0.7-0.8,在 Java 中的定义为 0.75。
负载因子是哈希表设计中的一个关键参数,它直接影响到数据结构的性能和效率。理解和合理设置负载因子可以帮助优化哈希表的使用效果。
三、解决冲突问题
1.闭散列
在哈希表中,**闭散列(Closed Hashing 或 Open Addressing)**是一种处理哈希冲突的方法。当两个或多个元素映射到哈希表的同一个索引位置时,闭散列通过在哈希表内部寻找其他空位置来解决冲突。
线性探测(Linear Probing)
线性探测是最简单的闭散列方法。当发生冲突时,哈希表会逐个检查后续的位置(即当前位置 + 1, + 2, ...)直到找到一个空位。
哈希函数 h(k) = k % m,如果冲突,检查 h(k) + 1, h(k) + 2, ...,直到 h(k) + n 是空的,然后将此地方作为索引位置。
二次探测(Quadratic Probing)
与线性探测不同,二次探测在发生冲突后使用平方增量进行检查,如果冲突就检查 h(k)+1^2, h(k)+2^2, h(k)+3^2... 直到找到空的位置,然后将此位置作为索引位置。
优点:减少了聚集的可能性。
缺点:仍然可能导致聚集,并且需要考虑表的大小,避免形成完整的循环,空间利用率低。
研究表明:当表的长度为质数且表装载因子 a 不超过 0.5 时,新的表项一定能够插入,而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置,就不会存在表满的问题。在搜索时可以不考虑表装满的情况,但在插入时必须确保表的装载因子 a 不超过 0.5,如果超出必须考虑增容。
2.开散列(哈希桶)--->重点
开散列法又叫链地址法 (开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。
hash(key)=key%capacity;
这里 capacity=10;
开散列,可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了。
哈希桶的模拟实现
public class T {
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;
for (Node cur = array[index]; cur != null; cur = cur.next) {
if (key == cur.key) {
int oldValue cur.value;
cur.value = value;
oldValue;
}
}
(key, value);
node.next = array[index];
array[index] = node;
size++;
(loadFactor() >= LOAD_FACTOR) {
resize();
}
-;
}
{
Node[] newArray = [array.length * ];
( ; i < array.length; i++) {
Node next;
( array[i]; cur != ; cur = next) {
next = cur.next;
cur.key % newArray.length;
cur.next = newArray[index];
newArray[index] = cur;
}
}
array = newArray;
}
{
size * / array.length;
}
{
array = [];
size = ;
}
{
key % array.length;
array[index];
( head; cur != ; cur = cur.next) {
(key == cur.key) {
cur.value;
}
}
-;
}
}
}
Map 与 Set 的关系
Set 与 Map 主要的不同有两点:Set 是继承自 Collection 的接口类,Set 中只存储了 Key。
也就是你只需要学会了 map 就大概也就学会了 set,set 对比 map 只储存 key 值。方法层面也是大差不差,只要将 value 排除即可。
但 Set 是继承了集合类,关于集合类的一些操作 Set 也是可以进行的。
- Set 是继承自 Collection 的一个接口类。
- Set 中只存储了 key,并且要求 key 一定要唯一。
- TreeSet 的底层是使用 Map 来实现的,其使用 key 与 Object 的一个默认对象作为键值对插入到 Map 中的。
- Set 最大的功能就是对集合中的元素进行去重。
- 实现 Set 接口的常用类有 TreeSet 和 HashSet,还有一个 LinkedHashSet,LinkedHashSet 是在 HashSet 的基础上维护了一个双向链表来记录元素的插入次序。
- Set 中的 Key 不能修改,如果要修改,先将原来的删除掉,然后再重新插入。
- TreeSet 中不能插入 null 的 key,HashSet 可以。
注意事项
Tree 实现的 Map 和 Set 的底层结构通常是红黑树。Hash 则是哈希桶。
TreeSet/TreeMap:关于 key 是有序的。key 必须能够比较,否则会抛出 ClassCastException 异常。
HashSet/HashMap:关于 key 不一定有序,自定义类型需要覆写 equals 和 hashCode 方法。
- HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 Set。
- java 中使用的是哈希桶方式解决冲突的。
- java 会在冲突链表长度大于一定阈值后,将链表转变为搜索树(红黑树)。
- java 中计算哈希值实际上是调用的类的 hashCode 方法,进行 key 的相等性比较是调用 key 的 equals 方法。所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值,必须覆写 hashCode 和 equals 方法,而且要做到 equals 相等的对象,hashCode 一定是一致的。