https://www.cnblogs.com/grandyang/p/9966807.html
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:
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，不能用自带的哈希表的数据结构，而且要我们主要实现添加，删除，以及判断是否存在，这三个函数。我们都知道HashSet最有用的地方就是其能够在常数的时间内判断某个元素是否存在，这都得归功于哈希表的作用。但是现在不让我们用了，但我们还是得保证其常数级的查找效率，那么就用空间来换时间吧。既然题目中说了数字的范围不会超过1000000，那么我们就申请这么大空间的数组，这样对于在HashSet中的数字，我们就将其标记为1，不在或者删除了的就标记为0，检测的时候就看其值是否为1即可
https://leetcode.com/problems/design-hashset/discuss/172600/Java-Solution-with-inner-Bucket-class!
I defined a inner bucket class to make the organization clean. Arrays are used to deal with the collision under the assumption that the number of buckets are always less than the key size.
class Buckets{
private int itemsNum;
private int items[];
public Buckets(){
itemsNum = 1001;
items = new int[itemsNum];
init();
}
public void init(){
for(int i = 0; i < itemsNum; i++)
items[i] = -1;
}
public void setItem(int key,int value){
int index = hashItem(key);
items[index] = value;
}
public int getItem(int key){
int index = hashItem(key);
return items[index];
}
public int hashItem(int key){
return key / bucketsNum;
}
}
private int bucketsNum;
private Buckets buckets[];
/** Initialize your data structure here. */
public MyHashSet() {
bucketsNum = 1000;
buckets = new Buckets[bucketsNum];
}
public int hashBucket(int key){
return key % bucketsNum;
}
public void add(int key) {
int bucketID = hashBucket(key);
if(buckets[bucketID] == null) buckets[bucketID] = new Buckets();
buckets[bucketID].setItem(key, key);
}
public void remove(int key) {
int bucketID = hashBucket(key);
if(contains(key)) buckets[bucketID].setItem(key, -1);
}
/** Returns true if this set contains the specified element */
public boolean contains(int key) {
int bucketID = hashBucket(key);
return buckets[bucketID] != null && buckets[bucketID].getItem(key) != -1;
}https://leetcode.com/problems/design-hashset/discuss/143434/Beats-100-Real-Java-Solution-(Not-boolean-array)
itemsPerBucket is set to 1001 to deal with the edge case when the key is 0 even though the description specify the number value ranges from 1-100k. This will occupy 1000 additional booleans in memory.
private int buckets = 1000;
private int itemsPerBucket = 1001;
private boolean[][] table;
/** Initialize your data structure here. */
public MyHashSet() {
table = new boolean[buckets][];
}
public int hash(int key) {
return key % buckets;
}
public int pos(int key) {
return key / buckets;
}
public void add(int key) {
int hashkey = hash(key);
if (table[hashkey] == null) {
table[hashkey] = new boolean[itemsPerBucket];
}
table[hashkey][pos(key)] = true;
}
public void remove(int key) {
int hashkey = hash(key);
if (table[hashkey] != null)
table[hashkey][pos(key)] = false;
}
/** Returns true if this set did not already contain the specified element */
public boolean contains(int key) {
int hashkey = hash(key);
return table[hashkey] != null && table[hashkey][pos(key)];
}X.
int set[];
/** Initialize your data structure here. */
public MyHashSet() {
set = new int[1000001];
Arrays.fill(set, -1);
}
public void add(int key) {
set[key] = key;
}
public void remove(int key) {
set[key] = -1;
}
/** Returns true if this set contains the specified element */
public boolean contains(int key) {
return set[key] != -1;
}
No need to use int. Here's even simpler:
boolean[] set;
/** Initialize your data structure here. */
public MyHashSet() {
set = new boolean[1000001];
}
public void add(int key) {
set[key]=true;
}
public void remove(int key) {
set[key]=false;
}
/** Returns true if this set contains the specified element */
public boolean contains(int key) {
return set[key];
}
