No matter what everyone in the world says, I think my feelings are right. No matter what other people think, I never break my rhythm. Like things naturally can insist, do not like how also can not long.

LeetCode: the original address

Topic request

Design a HashSet without using any built-in hash table libraries.

Implement MyHashSet class:

Void add(key) Inserts the value key into the hash set. Bool Contains (key) returns whether the hash set contains the value key. Void Remove (key) Removes the given value key from the hash set. If it’s not in the hash set, do nothing, okay

Example 1:

Input:  ["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"] [[], [1], [2], [1], [3], [2], [2], [2]] Output: [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); // Returns 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, (removed)Copy the code

Train of thought

Chain address method

  • To set the size of the hash table to base, we can design a simple hash function: hash(x) = x mod base.
  • Let’s create an array of size base, where each position is a linked list. When the hash value is calculated, it is inserted into the linked list at the corresponding location.
  • Since we use integer division as a hash function, base should be a prime number to avoid collisions as much as possible. In this case, we take base=769.
var MyHashSet = function() { this.BASE = 769; this.data = new Array(this.BASE).fill(0).map(() => new Array()); }; MyHashSet.prototype.add = function(key) { const h = this.hash(key); for (const element of this.data[h]) { if (element === key) { return; } } this.data[h].push(key); }; MyHashSet.prototype.remove = function(key) { const h = this.hash(key); const it = this.data[h]; for (let i = 0; i < it.length; ++i) { if (it[i] === key) { it.splice(i, 1); return; }}}; MyHashSet.prototype.contains = function(key) { const h = this.hash(key); for (const element of this.data[h]) { if (element === key) { return true; } } return false; }; MyHashSet.prototype.hash = function(key) { return key % this.BASE; }Copy the code