如何高效实现随机池结构、布隆过滤器、一致性哈希、岛问题和并查集？
摘要：package com.zuoshen.jichutisheng.class01; import java.util.HashMap; import java.util.List; import java.util.Stack; ** *
package com.zuoshen.jichutisheng.class01;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;
/**
* @author ShiZhe
* @create 2022-03-15 12:36
*/
public class code01 {
/**
* Insert、delete和getRandom方法的时间复杂度都是O(1)
* @param <K>
*/
public static class Pool<K> {
// 加入不重复
public HashMap<K, Integer> keyIndexMap;
// 随机返回
public HashMap<Integer, K> indexKeyMap;
public int size;
/**
* 无参构造函数
*/
public Pool() {
this.keyIndexMap = new HashMap<K, Integer>();
this.indexKeyMap = new HashMap<Integer, K>();
this.size = 0;
}
/**
* 插入不重复
* @param key
*/
public void insert(K key) {
if (!this.keyIndexMap.containsKey(key)) {
this.keyIndexMap.put(key, this.size);
this.indexKeyMap.put(this.size++, key);
}
}
/**
* 获得需要删除的key与对应的位置
* 获得最后一个的值，size减1
* 用最后一个替换删除key的下标
* 删除key
* @param key
*/
public void delete(K key) {
if (this.keyIndexMap.containsKey(key)) {
int deleteIndex = this.keyIndexMap.get(key);
int lastIndex = --this.size;
K lastKey = this.indexKeyMap.get(lastIndex);
this.keyIndexMap.put(lastKey, deleteIndex);
this.indexKeyMap.put(deleteIndex, lastKey);
this.keyIndexMap.remove(key);
this.indexKeyMap.remove(lastIndex);
}
}
/**
* 随机返回
* @return
*/
public K getRandom() {
if (this.size == 0) {
return null;
}
int randomIndex = (int) (Math.random() * this.size); // 0 ~ size -1
return this.indexKeyMap.get(randomIndex);
}
}
/**
* https://developer