Can you create a simple hash table? | brush title punch

Usually when we are programming, we often use hash table to process and store data, so if you implement a simple hash table, how will you achieve it?

Designing a hash set

First, look at the problem

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 value key exists in the hash set.
• void remove(key)Removes the given value key from the hash set. If it’s not in the hash set, do nothing.

Example:

Input:

• [“MyHashSet”, “add”, “add”, “contains”, “contains”, “add”, “contains”, “remove”, “contains”]
• [[], [1], [2], [1], [3], [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, (removed)

Tip:

• 
  $0 <= key <= 10^6$
• Maximum 104 callsadd,remove 和 contains

Second, organize your thoughts

Before we realize the simple hash table data structure, we should first analyze, for the simple hash table given in the question should have what functions, as well as the preliminary implementation ideas.

The first step:

Confirm input and output:

Input: 0−1060-10^60−106 number

Output: As you can see from the example, only the contains method returns a bool. The other methods do not return a value

The second step

How do you implement this data structure?

As a hash table, we must first have an attribute to store the data, which we’ll call Data.

In addition to data, there are three methods given in the stem: add, contains, and remove.

Since we can’t use a built-in hash table library, we can take arrays for simulation. Besides the three methods mentioned in the question, there are no other requirements, so we can take some optimization measures, such as grouping numbers when storing, so as to avoid conflicts.

Here we use integer division as a hash function. To avoid conflicts, we make the divisor BASE a prime number.

Therefore, the following algorithm is obtained:

/** * Initialize your data structure here. */
var MyHashSet = function () {
    this.BASE = 971;
    this.data = new Array(this.BASE).fill(0).map(() = > new Array())};/ * * *@param {number} key
 * @return {void}* /
MyHashSet.prototype.add = function (key) {
    const h = key % this.BASE
    for (let ele of this.data[h]) {
        if (ele === key) return
    }
    this.data[h].push(key)
};

/ * * *@param {number} key
 * @return {void}* /
MyHashSet.prototype.remove = function (key) {
    const h = key % this.BASE
    for (let i = 0; i < this.data[h].length; i++) {
        if (this.data[h][i] === key) {
            this.data[h].splice(i, 1)
            return}}};/**
 * Returns true if this set contains the specified element 
 * @param {number} key
 * @return {boolean}* /
MyHashSet.prototype.contains = function (key) {
    const h = key % this.BASE
    return this.data[h].includes(key)
};

/** * Your MyHashSet object will be instantiated and called as such: * var obj = new MyHashSet() * obj.add(key) * obj.remove(key) * var param_3 = obj.contains(key) */
Copy the code

For why prime numbers are modulo, use Leetcoder @Guoran’s original words:

Modulo of primes is a play on the idea of congruence: when the element is a regular arithmetic sequence, and the largest common divisor with the cardinality (array size) is not 1, the hash mapping conflict will be high (some positions in the array will never have values).

Like 0,6,12,18,24… , base is 10, and the positions in the hash table will only be 0,2,4,6,8

But if we take base 7 (the array size is even smaller than 10), the same sequence can be distributed in the hash table 0,1,2,3,4,5,6

I can make every position in the hash table useful.

Third, summary

Knowledge point: basic data structure implementation

The problem solving method:

For the basic data structures we are used to, we should also have a proper in-depth understanding of the implementation principles, so that we can better use these tools and maximize their use value.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign