描述
Design a HashSet without using any built-in hash table libraries.
To be specific, your design should include these functions:
add(value)
: Insert a value into the HashSet.
contains(value)
: Return whether the value exists in the HashSet or not.
remove(value)
: Remove a value in the HashSet. If the value does not exist in the HashSet, do nothing.
Example:
1 2 3 4 5 6 7 8 9 MyHashSet hashSet = new MyHashSet(); hashSet.add(1); hashSet.add(2); hashSet.contains(1); // returns true hashSet.contains(3); // returns false (not found) hashSet.add(2); hashSet.contains(2); // returns true hashSet.remove(2); hashSet.contains(2); // returns false (already removed)
Note:
All values will be in the range of [0, 1000000]
.
The number of operations will be in the range of [1, 10000]
.
Please do not use the built-in HashSet library.
分析
题目要求自己实现一个 HashSet,不能使用内置的库。key 的范围在 [0, 1000000],可以用数组来当做哈希表,解决哈希冲突可以使用链地址法和开放寻址法,这里我们使用链表来实现链地址法。
下一题 706. Design HashMap 简直和这道题一模一样,只不过下一题是实现 HashMap,就两行代码的差别。
解决方案1(Java)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 class MyHashSet { final Bucket[] buckets = new Bucket[10000 ]; int index (int key) { return Integer.hashCode(key) % buckets.length; } ListNode find (Bucket bucket, int key) { ListNode node = bucket.head, prev = null ; while (node != null && node.key != key) { prev = node; node = node.next; } return prev; } public MyHashSet () { } public void add (int key) { int i = index(key); if (buckets[i] == null ) { buckets[i] = new Bucket(); } ListNode prev = find(buckets[i], key); if (prev.next == null ) { prev.next = new ListNode(key, 1 ); } else { prev.next.val = 1 ; } } public void remove (int key) { int i = index(key); if (buckets[i] == null ) { return ; } ListNode node = find(buckets[i], key); if (node.next == null ) { return ; } node.next = node.next.next; } public boolean contains (int key) { int i = index(key); if (buckets[i] == null ) { return false ; } ListNode node = find(buckets[i], key); if (node.next == null ) { return false ; } return true ; } } class Bucket { final ListNode head = new ListNode(-1 , -1 ); } class ListNode { int key, val; ListNode next; ListNode(int key, int val) { this .key = key; this .val = val; } }
相关问题