跳到主要内容Java Map 与 Set 数据结构解析 | 极客日志Javajava算法
Java Map 与 Set 数据结构解析
Java Map 与 Set 是常用集合框架。Map 存储键值对,Set 存储唯一元素。TreeMap 和 TreeSet 基于红黑树,支持排序,时间复杂度 O(logN)。HashMap 和 HashSet 基于哈希表,平均查找 O(1)。哈希表需处理冲突,采用闭散列或开散列。负载因子影响性能,超限需扩容。HashMap 非线程安全。常见面试题涉及频率统计与 Top K 问题。
Map 和 Set
- map 和 set 用于搜索
- 搜索树,二叉搜索树 -> AVL 树 -> 红黑树
- AVL 树:高度平衡的二叉搜索树
- TreeMap 和 TreeSet 底层是红黑树,每次存储元素都得进行大小比较
二叉搜索树
- 二叉搜索树:如果左子树不为空,那么左子树所有节点都小于根节点,如果右子树不为空,那么右子树所有节点都大于根节点,它的左右子树都是二叉搜索树
- 二叉搜索树的中序遍历是有序的
查找
- 比 key 大往右找,比 key 小往左找
public boolean search(int key) {
TreeNode cur = root;
while (cur != null) {
if (cur.val > key) {
cur = cur.left;
} else if (cur.val < key) {
cur = cur.right;
} else {
return true;
}
}
return false;
}
分析:
- 时间复杂度:
- 最好情况:O(logN),完全二叉树
- 最坏情况:O(N),单分支的二叉树
插入
public boolean insert(int key) {
TreeNode node = new TreeNode(key);
TreeNode parent = null;
if (root == null) {
root = node;
;
}
root;
(cur != ) {
(cur.val < key) {
parent = cur;
cur = cur.right;
} (cur.val > key) {
parent = cur;
cur = cur.left;
} {
;
}
}
(parent.val < key) {
parent.right = node;
} {
parent.left = node;
}
;
}
相关免费在线工具
- Keycode 信息
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具,Keycode 信息在线工具,online
- Escape 与 Native 编解码
JavaScript 字符串转义/反转义;Java 风格 \uXXXX(Native2Ascii)编码与解码。 在线工具,Escape 与 Native 编解码在线工具,online
- JavaScript / HTML 格式化
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具,JavaScript / HTML 格式化在线工具,online
- JavaScript 压缩与混淆
Terser 压缩、变量名混淆,或 javascript-obfuscator 高强度混淆(体积会增大)。 在线工具,JavaScript 压缩与混淆在线工具,online
- 加密/解密文本
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
return
true
TreeNode
cur
=
while
null
if
else
if
else
return
false
if
else
return
true
删除
-
第一种情况:cur.left == null
要删除的节点是 cur
cur 是根节点
cur 是某个节点的左边
cur 是某个节点的右边
-
第二种情况:cur.right == null
要删除的节点是 cur
cur 是根节点
cur 是某个节点的左边
cur 是某个节点的右边
-
第三种情况:cur.left != null && cur.right != null
使用替换法进行删除
替换为左树中最大的值
或者是右树中最小的值
替换完之后删除这个去替换的值
private void removeNode(TreeNode cur, TreeNode parent) {
if (cur.left == null) {
if (cur == root) {
root = cur.right;
} else if (cur == parent.left) {
parent.left = cur.right;
} else {
parent.right = cur.right;
}
} else if (cur.right == null) {
if (cur == root) {
root = cur.left;
} else if (cur == parent.left) {
parent.left = cur.left;
} else {
parent.right = cur.left;
}
} else {
TreeNode parentTarget = cur;
TreeNode target = cur.right;
while (target.left != null) {
parentTarget = target;
target = target.left;
}
cur.val = target.val;
if (parentTarget.left == target) {
parentTarget.left = target.right;
} else {
parentTarget.right = target.right;
}
}
}
Map
- map 是一种 (k,v) 结构的数据结构
- map 可以进行去重,TreeMap 不可以插入 null 的 key,HashMap 可以插入 null 的 key,因为红黑树是要进行比较的,哈希表是不进行比较的
Map<String, Integer> map = new TreeMap<>();
Map<String, Integer> map1 = new HashMap<>();
Map 的使用
public static void main(String[] args) {
Map<String, Integer> map = new TreeMap<>();
Integer val = map.get("push");
Integer val1 = map.get("aaa");
Integer val2 = map.getOrDefault("bbb", 99999);
System.out.println(val);
Set<String> set = map.keySet();
System.out.println(set);
ArrayList<Integer> value = new ArrayList<>(map.values());
System.out.println(value);
Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
for (Map.Entry<String, Integer> entry : entrySet) {
System.out.println("key: " + entry.getKey() + " value: " + entry.getValue());
}
Map<String, Integer> map1 = new HashMap<>();
}
Set
Set 的使用
- Set 是要进行去重的
- TreeSet 不可以插入 null 的 key,HashSet 可以插入 null 的 key,因为红黑树是要进行比较的,哈希表是不进行比较的
public static void main(String[] args) {
Set<String> set = new TreeSet<>();
set.add("push");
set.add("hello");
set.add("world");
System.out.println(set);
Iterator<String> it = set.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
}
哈希表
哈希冲突 (碰撞):不同的 key 通过相同的哈希函数得到相同的值
哈希冲突是必然产生的,我们要做的是降低冲突的概率
解决哈希冲突:哈希函数的设计要合理
哈希函数要简单
哈希表中要均匀分到数组中去
哈希表的范围要合理,比如有 m 个地址,存储位置就是 [0,m-1]
负载因子的调节(重点)
- 负载因子影响了哈希冲突,负载因子越大冲突率越高
- 哈希表中的负载因子定义为:
a = 填入表中的元素个数 / 哈希表的长度
比如:a = 8 / 10 = 0.8
如果降低冲突率就要降低负载因子,因此要扩容哈希表的大小,不增加插入的元素是不现实的,给定一个阈值,如果超过了就扩大哈希表的容量
闭散列
-
开放定址法,如果没有达到阈值,但是冲突了,就放到冲突的下一个空的位置上,这个也叫线性探测
-
线性探测的缺点:把冲突的元素都集中放到了一起
-
二次探测:为了解决线性探测的缺点,通过公式进行处理,H0 是当前冲突的位置,i 是出现冲突的次数,m 是哈希表的大小,Hi 表示冲突后,下一次要放的位置
-
线性探测对于空间的利用率不高
开散列
-
开散列:又叫链地址法,为了解决空间利用率不高的问题,开散列是数组 + 链表 + 红黑树的模式
-
把冲突的元素挂到同一个空间下的链表上
-
Java 是采用开散列的方式实现的
-
扩容之后需要重新哈希,因为数组长度变了,要重新计算节点存放的位置
-
遍历哈希数组中每个数组元素,都要重新计算节点位置
package Demo1;
import java.util.Arrays;
public class HashBucket {
public class Node {
public int key;
public int val;
public Node next;
public Node(int key, int val) {
this.key = key;
this.val = val;
}
}
public Node[] array;
public int usedSize;
public static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashBucket() {
array = new Node[10];
}
public void put(int key, int value) {
int index = key % array.length;
Node node = new Node(key, value);
Node cur = array[index];
while (cur != null) {
if (cur.key == key) {
cur.val = value;
return;
}
cur = cur.next;
}
node.next = array[index];
array[index] = node;
usedSize++;
if (doLoadFactor() > DEFAULT_LOAD_FACTOR) {
resize();
}
}
private void resize() {
Node[] newArray = new Node[2 * array.length];
for (int i = 0; i < array.length; i++) {
Node cur = array[i];
while (cur != null) {
Node tmp = cur.next;
int newIndex = cur.key % newArray.length;
cur.next = newArray[newIndex];
newArray[newIndex] = cur;
cur = tmp;
}
}
array = newArray;
}
private float doLoadFactor() {
return usedSize * 1.0f / array.length;
}
public int get(int key) {
int index = key % array.length;
Node cur = array[index];
while (cur != null) {
if (cur.key == key) {
return cur.val;
}
cur = cur.next;
}
return -1;
}
}
- HashMap 是线程不安全的,因为采用了头插法,后面采用了尾插法变得安全了,ConcurrentHashMap 是线程安全的,之后学到了线程就可以理解了
- 如果 key 是 String,Person 类型就不能除以数组的长度了,该怎么找到对应的下标呢?
可以用 hashcode 来将自定义类型转化为整形类型
HashMap 和 HashSet
public static void main(String[] args) {
HashMap<String, Integer> hashMap = new HashMap<>();
hashMap.put("hello", 2);
hashMap.put("abcde", 10);
hashMap.put("abc", 11);
Integer val = hashMap.get("hello");
System.out.println(val);
System.out.println(hashMap);
for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {
System.out.println("key:" + entry.getKey() + " value:" + entry.getValue());
}
HashMap<Student, Integer> hashMap1 = new HashMap<>();
hashMap1.put(new Student(), 2);
hashMap1.put(new Student(), 2);
hashMap1.put(null, 2);
HashSet<String> set = new HashSet<>();
set.add("hello");
set.add("world");
set.add("hello");
System.out.println(set);
}
面试题
只出现一次的数字
宝石与石头
旧键盘
随机链表的复制
public static void main(String[] args) {
int[] array = {1, 1, 2, 2, 3, 3};
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < array.length; i++) {
if (!map.containsKey(array[i])) {
map.put(array[i], 1);
} else {
int k = map.get(array[i]);
k++;
map.put(array[i], k);
}
}
System.out.println(map);
}
如果频率相同放入堆中要使用大根堆,要让 love 排在 i 的前面
class Solution {
public List<String> topKFrequent(String[] words, int k) {
Map<String, Integer> map = new HashMap<>();
for (String s : words) {
if (!map.containsKey(s)) {
map.put(s, 1);
} else {
int val = map.get(s);
map.put(s, val + 1);
}
}
PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
if (o1.getValue().compareTo(o2.getValue()) == 0) {
return o2.getKey().compareTo(o1.getKey());
}
return o1.getValue().compareTo(o2.getValue());
}
});
for (Map.Entry<String, Integer> entry : map.entrySet()) {
if (minHeap.size() < k) {
minHeap.add(entry);
} else {
int v = minHeap.peek().getValue();
if (v < entry.getValue()) {
minHeap.poll();
minHeap.offer(entry);
} else {
if (v == entry.getValue()) {
if (minHeap.peek().getKey().compareTo(entry.getKey()) > 0) {
minHeap.poll();
minHeap.offer(entry);
}
}
}
}
}
List<String> arr = new ArrayList<>();
for (int i = 0; i < k; i++) {
Map.Entry<String, Integer> top = minHeap.poll();
arr.add(top.getKey());
}
Collections.reverse(arr);
return arr;
}
}
HashMap 的源码
如果达到一定条件会把哈希表编程红黑树:如果链表的长度大于 8 并且数组的长度大于 64 就会进行树化