Design a HashSet without using any built-in hash table libraries.
Implement MyHashSet class:
void add(key) Inserts the value key into the HashSet.bool contains(key) Returns whether the value key exists in the HashSet or not.void remove(key) Removes the value key in the HashSet. If key does not exist in the HashSet, do nothing.Example 1:
Input [ "MyHashSet ", "add ", "add ", "contains ", "contains ", "add ", "contains ", "remove ", "contains "] [[], [1], [2], [1], [3], [2], [2], [2], [2]] Output [null, null, null, true, false, null, true, null, false]
Explanation MyHashSet myHashSet = new MyHashSet(); myHashSet.add(1); // set = [1] myHashSet.add(2); // set = [1, 2] myHashSet.contains(1); // return True myHashSet.contains(3); // return False, (not found) myHashSet.add(2); // set = [1, 2] myHashSet.contains(2); // return True myHashSet.remove(2); // set = [1] myHashSet.contains(2); // return False, (already removed)
Constraints:
0 <= key <= 106104 calls will be made to add, remove, and contains.program main
use hashset_mod
implicit none
type(MyHashSet) :: myHashSet
call myHashSet%add(1)
call myHashSet%add(2)
print '(L1)', myHashSet%contains(1) ! true
print '(L1)', myHashSet%contains(3) ! false
call myHashSet%add(2)
print '(L1)', myHashSet%contains(2) ! true
call myHashSet%remove(2)
print '(L1)', myHashSet%contains(2) ! false
end program main
module hashset_mod
implicit none
private
public :: MyHashSet
type :: MyHashSet
integer, allocatable :: keys(:)
contains
procedure :: add => add_impl
procedure :: contains => contains_impl
procedure :: remove => remove_impl
end type MyHashSet
contains
subroutine add_impl(this, key)
class(MyHashSet), intent(inout) :: this
integer, intent(in) :: key
if (.not. allocated(this%keys)) then
allocate(this%keys(1))
this%keys(1) = key
else
allocate(this%keys(size(this%keys)+1))
this%keys(1:size(this%keys)-1) = this%keys(1:size(this%keys)-1)
this%keys(size(this%keys)) = key
end if
end subroutine add_impl
logical function contains_impl(this, key) result(res)
class(MyHashSet), intent(in) :: this
integer, intent(in) :: key
res = any(this%keys == key)
end function contains_impl
subroutine remove_impl(this, key)
class(MyHashSet), intent(inout) :: this
integer, intent(in) :: key
integer :: i
do i=1, size(this%keys)
if (this%keys(i) == key) exit
end do
if (i <= size(this%keys)) then
this%keys(i:size(this%keys)-1) = this%keys(i+1:size(this%keys))
deallocate(this%keys)
end if
end subroutine remove_impl
end module hashset_modtemp.f95:2:9:
2 | use hashset_mod
| 1
Fatal Error: Cannot open module file ‘hashset_mod.mod’ for reading at (1): No such file or directory
compilation terminated.
module MyHashSet
implicit none
private
integer, parameter :: INITIAL_SIZE = 10000
integer, parameter :: MAX_LOAD_FACTOR = 2
type :: MyHashSet
private
integer, allocatable :: keys(:)
integer :: size
integer :: count
contains
procedure, public :: add
procedure, public :: contains
procedure, public :: remove
end type MyHashSet
contains
subroutine add(this, key)
class(MyHashSet), intent(inout) :: this
integer, intent(in) :: key
integer :: i
if (this%count == 0) then
allocate(this%keys(INITIAL_SIZE))
this%size = INITIAL_SIZE
else if (this%count == this%size) then
allocate(this%keys(this%size * MAX_LOAD_FACTOR))
this%size = this%size * MAX_LOAD_FACTOR
end if
do i = 1, this%count
if (this%keys(i) == key) then
return
end if
end do
this%keys(this%count + 1) = key
this%count = this%count + 1
end subroutine add
function contains(this, key) result(res)
class(MyHashSet), intent(in) :: this
integer, intent(in) :: key
logical :: res
integer :: i
res = .false.
do i = 1, this%count
if (this%keys(i) == key) then
res = .true.
exit
end if
end do
end function contains
subroutine remove(this, key)
class(MyHashSet), intent(inout) :: this
integer, intent(in) :: key
integer :: i
do i = 1, this%count
if (this%keys(i) == key) then
this%keys(i) = this%keys(this%count)
this%count = this%count - 1
exit
end if
end do
end subroutine remove
end module MyHashSet
program test
use MyHashSet
implicit none
type(MyHashSet) :: myHashSet
call myHashSet%add(1)
call myHashSet%add(2)
print *, myHashSet%contains(1)
print *, myHashSet%contains(3)
call myHashSet%add(2)
print *, myHashSet%contains(2)
call myHashSet%remove(2)
print *, myHashSet%contains(2)
end program test
temp.f95:9:19:
9 | type :: MyHashSet
| 1
Error: MODULE attribute of ‘myhashset’ conflicts with PROCEDURE attribute at (1)
temp.f95:10:11:
10 | private
| 1
Error: PRIVATE statement at (1) follows another accessibility specification
temp.f95:18:5:
18 | end type MyHashSet
| 1
Error: Expecting END MODULE statement at (1)
temp.f95:20:8:
20 | contains
| 1
Error: Unexpected CONTAINS statement in CONTAINS section at (1)
temp.f95:23:21:
1 | module MyHashSet
| 2
......
23 | class(MyHashSet), intent(inout) :: this
| 1
Error: Type name ‘myhashset’ at (1) conflicts with previously declared entity at (2), which has the same name
temp.f95:28:14:
28 | if (this%count == 0) then
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:29:21:
29 | allocate(this%keys(INITIAL_SIZE))
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:30:12:
30 | this%size = INITIAL_SIZE
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:31:19:
31 | else if (this%count == this%size) then
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:32:21:
32 | allocate(this%keys(this%size * MAX_LOAD_FACTOR))
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:33:12:
33 | this%size = this%size * MAX_LOAD_FACTOR
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:34:7:
34 | end if
| 1
Error: Expecting END SUBROUTINE statement at (1)
temp.f95:36:20:
36 | do i = 1, this%count
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:37:16:
37 | if (this%keys(i) == key) then
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:39:9:
39 | end if
| 1
Error: Expecting END SUBROUTINE statement at (1)
temp.f95:40:7:
40 | end do
| 1
Error: Expecting END SUBROUTINE statement at (1)
temp.f95:42:10:
42 | this%keys(this%count + 1) = key
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:43:10:
43 | this%count = this%count + 1
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:48:21:
1 | module MyHashSet
| 2
......
48 | class(MyHashSet), intent(in) :: this
| 1
Error: Type name ‘myhashset’ at (1) conflicts with previously declared entity at (2), which has the same name
temp.f95:56:20:
56 | do i = 1, this%count
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:57:16:
57 | if (this%keys(i) == key) then
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:59:12:
59 | exit
| 1
Error: EXIT statement at (1) is not within a construct
temp.f95:60:9:
60 | end if
| 1
Error: Expecting END FUNCTION statement at (1)
temp.f95:61:7:
61 | end do
| 1
Error: Expecting END FUNCTION statement at (1)
temp.f95:66:21:
1 | module MyHashSet
| 2
......
66 | class(MyHashSet), intent(inout) :: this
| 1
Error: Type name ‘myhashset’ at (1) conflicts with previously declared entity at (2), which has the same name
temp.f95:71:20:
71 | do i = 1, this%count
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:72:16:
72 | if (this%keys(i) == key) then
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:73:14:
73 | this%keys(i) = this%keys(this%count)
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:74:14:
74 | this%count = this%count - 1
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:75:12:
75 | exit
| 1
Error: EXIT statement at (1) is not within a construct
temp.f95:76:9:
76 | end if
| 1
Error: Expecting END SUBROUTINE statement at (1)
temp.f95:77:7:
77 | end do
| 1
Error: Expecting END SUBROUTINE statement at (1)
temp.f95:22:21:
22 | subroutine add(this, key)
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:47:24:
47 | function contains(this, key) result(res)
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:65:24:
65 | subroutine remove(this, key)
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:84:7:
84 | use MyHashSet
| 1
Fatal Error: Cannot open module file ‘myhashset.mod’ for reading at (1): No such file or directory
compilation terminated.
class MyHashSet:
def __init__(self):
self.storage = [False] * 1000001
def add(self, key: int):
self.storage[key] = True
def remove(self, key: int):
self.storage[key] = False
def contains(self, key: int) -> bool:
return self.storage[key]
The simplest way to implement a HashSet without using any built-in hash table libraries is to use an array of boolean values. The index of the array represents the key and the value at that index represents whether the key is present in the HashSet or not. In this case, we know the key range is `0 <= key <= 10^6`, so we can create an array with a length of `1000001`.
For the add(key) method, we set the value at the index of the key to be true.
For the remove(key) method, we set the value at the index of the key to be false.
For the contains(key) method, we check the value at the index of the key and return it.
The implementations of these methods are straightforward, and they are similar in each language. We create a storage array (vector in C++, boolean array in Java, list in Python, and array in JavaScript), and then we use simple array operations to manipulate the data.
class MyHashSet {
public:
vector<bool> storage;
MyHashSet() : storage(1000001, false) { }
void add(int key) {
storage[key] = true;
}
void remove(int key) {
storage[key] = false;
}
bool contains(int key) {
return storage[key];
}
};
The simplest way to implement a HashSet without using any built-in hash table libraries is to use an array of boolean values. The index of the array represents the key and the value at that index represents whether the key is present in the HashSet or not. In this case, we know the key range is `0 <= key <= 10^6`, so we can create an array with a length of `1000001`.
For the add(key) method, we set the value at the index of the key to be true.
For the remove(key) method, we set the value at the index of the key to be false.
For the contains(key) method, we check the value at the index of the key and return it.
The implementations of these methods are straightforward, and they are similar in each language. We create a storage array (vector in C++, boolean array in Java, list in Python, and array in JavaScript), and then we use simple array operations to manipulate the data.