-
Notifications
You must be signed in to change notification settings - Fork 383
Expand file tree
/
Copy pathDesign HashSet.java
More file actions
145 lines (122 loc) · 3.08 KB
/
Design HashSet.java
File metadata and controls
145 lines (122 loc) · 3.08 KB
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
class MyHashSet {
/** Initialize your data structure here. */
private Bucket[] bucketArray;
private int keyRange;
public MyHashSet() {
this.keyRange = 769;
this.bucketArray = new Bucket[this.keyRange];
for (int i = 0; i < this.keyRange; i++) {
this.bucketArray[i] = new Bucket();
}
}
protected int _hash(int key) {
return key % this.keyRange;
}
public void add(int key) {
int bucketIndex = this._hash(key);
this.bucketArray[bucketIndex].insert(key);
}
public void remove(int key) {
int bucketIndex = this._hash(key);
this.bucketArray[bucketIndex].delete(key);
}
/** Returns true if this set contains the specified element */
public boolean contains(int key) {
int bucketIndex = this._hash(key);
return this.bucketArray[bucketIndex].exists(key);
}
}
class Bucket {
private BSTree tree;
public Bucket() {
tree = new BSTree();
}
public void insert(Integer key) {
this.tree.root = this.tree.insertToBST(this.tree.root, key);
}
public void delete(Integer key) {
this.tree.root = this.tree.deleteFromBST(this.tree.root, key);
}
public boolean exists(Integer key) {
TreeNode node = this.tree.searchBST(this.tree.root, key);
return node != null;
}
}
class BSTree {
TreeNode root = null;
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || val == root.val) {
return root;
}
return root.val > val ? searchBST(root.left, val) : searchBST(root.right, val);
}
public TreeNode insertToBST(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}
if (root.val < val) {
root.right = insertToBST(root.right, val);
}
else if (root.val > val) {
root.left = insertToBST(root.left, val);
}
else {
return root;
}
return root;
}
public TreeNode deleteFromBST(TreeNode root, int key) {
if (root == null) {
return null;
}
if (root.val < key) {
root.right = deleteFromBST(root.right, key);
}
else if (root.val > key) {
root.left = deleteFromBST(root.left, key);
}
else {
if (root.left == null && root.right == null) {
root = null;
}
else if (root.right != null) {
root.val = successor(root);
root.right = deleteFromBST(root.right, root.val);
}
else {
root.val = predecessor(root);
root.left = deleteFromBST(root.left, root.val);
}
}
return root;
}
private int successor(TreeNode root) {
root = root.right;
while (root.left != null) {
root = root.left;
}
return root.val;
}
private int predecessor(TreeNode root) {
root = root.left;
while (root.right != null) {
root = root.right;
}
return root.val;
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int x) {
val = x;
}
}
/**
* Your MyHashSet object will be instantiated and called as such:
* MyHashSet obj = new MyHashSet();
* obj.add(key);
* obj.remove(key);
* boolean param_3 = obj.contains(key);
*/