哈希表、集合

哈希表

通过哈希函数求出 key，往里面存 value

但这样会存在哈希碰撞的情况

时间复杂度

查找：O(1)，在最坏情况下能达到 O(n)（哈希碰撞）

添加：O(1)

删除：O(1)

代码

Map<Object, Object> map = new HashMap();

// 添加
map.put(o1, o2);
// 获取
map.get(o1);
map.getOrDefault(o1, o2); // 有则返回，没有则返回第二个参数
// 移除
map.remove(o1);
map.clear(); // 清楚全部
// 查询，是否存在
map.containsKey(o1);
// 遍历
for (Object key : map.keySet()) {}
for (Object value : map.values()) {}

集合

时间复杂度

查找：O(1)，在最坏情况下能达到 O(n)（哈希碰撞）

添加：O(1)

删除：O(1)

代码

Set<Object> set = new HashSet<Object>();

// 添加，如果重复则不再添加
set.add(o);
// 查询，是否存在
set.contains(o);
// 删除
set.remove(o);
// 获取长度
set.size();
// 循环
for (Object o : set) {}