Java 数据结构中 Map 接口存储键值对，HashMap 基于哈希桶实现，平均 O(1) 查找，需处理冲突；TreeMap 基于红黑树实现，按键排序，O(logN) 查找。Set 接口继承 Collection，仅存储唯一键，底层常依赖 Map 实现。文章详解 Map 基本方法、哈希函数优化、负载因子调节、闭散列与开散列冲突解决策略，以及自定义对象作为 Key 时需覆写 hashCode 和 equals 方法的规范。
在数据结构中，Map 是一种关联容器，它存储了键值对（key-value pairs），并且每个键在 Map 中都是唯一的。Map 提供了通过键快速访问其对应值的能力。简单来说，记录两个不同类型的值，一个被定义为键（Key），一个被定义为值（value），其中 Key 是唯一的，也就是说在 Map 中的 Key 是不允许重复出现的，但 value 是可以的。
Map 的用途比较广泛，常见的包括：
在 Java 中，Map 是一个接口，它定义了映射的基本操作。Map 接口的实现类，如 HashMap、TreeMap 和 LinkedHashMap。
Map.Entry 是 Map 内部实现的用来存放键值对映射关系的内部类，该内部类中主要提供了获取 key、value 的设置以及 key 的比较方式。
K getKey()：返回 entry 中的 key。V getValue()：返回 entry 中的 value。V setValue(V value)：将键值对中的 value 替换为指定 value。true。true。true。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);
}
}
要想了解如何用树实现 Map，现在必须认识二叉搜索树。因为 TreeMap 就是利用二叉搜索树来实现的。
通俗点来说，这颗树的每个节点的左树都比自身节点小，右树都比自身节点大。
我们主要模拟实现插入，搜索，移除接口。
解析：从根节点出发，对比当前 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;
}
解析：类似搜索，不断对比 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;
}
最难的接口其实是删除接口。解析：首先找到要删除的节点，要是没找到直接返回 false 即可。找的时候也要建一个变量 prev 来记录其父节点。这里采用的是替换删除法，选择另一个合适的节点来替换掉它，使得树还是一颗二叉搜索树。通常找要删除节点的左孩子的最右的那个节点。
当然这样删除时需要注意三种情况：
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 就是利用二叉搜索树来进行的，不过时优化过二叉搜索树，也就是红黑树。我们现在暂时还不需要了解太多，知道普通二叉搜索树即可。上面模拟的时候 key 是 int 类型，但最开始我们讲过其实 key 是 Map.Entry<K,V> 内部类类型的。我们只是为了了解一下二叉搜索树才将 key 设置为 int。
那么二叉搜索树在插入时我们也知道我们需要不断进行比较才能插入数据，所以我们在使用 TreeMap 实现的 Map 时我们就必须将我们传入的 K 类必须是可比较的，即实现 Comparable 接口的。
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());
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();
}
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为 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)，即：不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
注意：冲突无法避免，我们可以减少冲突的发生。也可以解决冲突所带来的问题。
在哈希表中，负载因子（Load Factor）是一个重要的概念，它用来衡量哈希表中已存储元素的密度。具体来说，负载因子是已存储元素的数量与哈希表的容量之间的比率。
定义： Load Factor = n / m
重要性：
如何选择负载因子：如果频繁插入和删除操作，可能希望使用较低的负载因子，以保持较高的查找性能。如果内存资源有限，可以接受较高的负载因子，以节省内存。一般情况我们都是选择负载因子为 0.7-0.8，在 Java 中的定义为 0.75。
负载因子是哈希表设计中的一个关键参数，它直接影响到数据结构的性能和效率。理解和合理设置负载因子可以帮助优化哈希表的使用效果。
在哈希表中，**闭散列（Closed Hashing 或 Open Addressing）**是一种处理哈希冲突的方法。当两个或多个元素映射到哈希表的同一个索引位置时，闭散列通过在哈希表内部寻找其他空位置来解决冲突。
线性探测是最简单的闭散列方法。当发生冲突时，哈希表会逐个检查后续的位置（即当前位置 + 1, + 2, ...）直到找到一个空位。 哈希函数 h(k) = k % m，如果冲突，检查 h(k) + 1, h(k) + 2, ...，直到 h(k) + n 是空的，然后将此地方作为索引位置。
与线性探测不同，二次探测在发生冲突后使用平方增量进行检查，如果冲突就检查 h(k)+1^2, h(k)+2^2, h(k)+3^2... 直到找到空的位置，然后将此位置作为索引位置。
优点：减少了聚集的可能性。 缺点：仍然可能导致聚集，并且需要考虑表的大小，避免形成完整的循环，空间利用率低。
研究表明：当表的长度为质数且表装载因子 a 不超过 0.5 时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子 a 不超过 0.5，如果超出必须考虑增容。
开散列法又叫链地址法 (开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
hash(key)=key%capacity; 这里 capacity=10；
开散列，可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了。
public class T {
// key-value 模型
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;
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;
}
}
-;
}
}
}
Set 与 Map 主要的不同有两点：Set 是继承自 Collection 的接口类，Set 中只存储了 Key。
也就是你只需要学会了 map 就大概也就学会了 set，set 对比 map 只储存 key 值。方法层面也是大差不差，只要将 value 排除即可。 但 Set 是继承了集合类，关于集合类的一些操作 Set 也是可以进行的。
Tree 实现的 Map 和 Set 的底层结构通常是红黑树。Hash 则是哈希桶。
TreeSet/TreeMap：关于 key 是有序的。key 必须能够比较，否则会抛出 ClassCastException 异常。
HashSet/HashMap：关于 key 不一定有序，自定义类型需要覆写 equals 和 hashCode 方法。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online