建设平台网站协议,管理系统和网站哪个好做,知名网站制作全包,南宁网站建设-中国互联题目
不使用任何内建的哈希表库设计一个哈希集合#xff08;HashSet#xff09;。 实现 MyHashSet 类#xff1a; void add(key) 向哈希集合中插入值 key 。 bool contains(key) 返回哈希集合中是否存在这个值 key 。 void remove(key) 将给定值 key 从哈希集合中删除。如果…题目
不使用任何内建的哈希表库设计一个哈希集合HashSet。 实现 MyHashSet 类 void add(key) 向哈希集合中插入值 key 。 bool contains(key) 返回哈希集合中是否存在这个值 key 。 void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值什么也不做。 示例 输入 [“MyHashSet”, “add”, “add”, “contains”, “contains”, “add”, “contains”, “remove”, “contains”] [[], [1], [2], [1], [3], [2], [2], [2], [2]] 输出 [null, null, null, true, false, null, true, null, false] 解释 MyHashSet myHashSet new MyHashSet(); myHashSet.add(1); // set [1] myHashSet.add(2); // set [1, 2] myHashSet.contains(1); // 返回 True myHashSet.contains(3); // 返回 False 未找到 myHashSet.add(2); // set [1, 2] myHashSet.contains(2); // 返回 True myHashSet.remove(2); // set [1] myHashSet.contains(2); // 返回 False 已移除
分析
这道题目要求模拟一个hashset我们最直接的思路就是用一个数组元素值表示数组下标 或者换一个思路我们可以直接用位来表示数字32表示数组的索引数字32表示所在的位
public class MyHashSet {private int[] a;public MyHashSet() {a new int[1000000/321];}public void add(int key) {int bucket key / 32;int bit key % 32;a[bucket] | (1 bit);}public void remove(int key) {int bucket key / 32;int bit key % 32;a[bucket] ~(1bit);}public boolean contains(int key) {int bucket key / 32;int bit key % 32;if((a[bucket] (1bit)) ! 0) {return true;} else {return false;}}
}
public class designHashSet {public static void main(String[] args) {MyHashSet myHashSet new MyHashSet();myHashSet.add(1); // set [1]myHashSet.add(2); // set [1, 2]System.out.println(myHashSet.contains(1)); // 返回 TrueSystem.out.println(myHashSet.contains(3)); // 返回 False 未找到myHashSet.add(2); // set [1, 2]System.out.println(myHashSet.contains(2)); // 返回 TruemyHashSet.remove(2); // set [1]System.out.println(myHashSet.contains(2)); // 返回 False 已移除}
}
