Js algorithm in the hash table

1. Basic concepts of hash tables

• A Hash table is a data structure that accesses data stored in memory based on a Key. That is, it accesses records by computing a function on key values that maps the data for the desired query to a location in the table, which speeds up lookups. This mapping function is called a hash function, and the array of records is called a hash table.
• Hash function: A Hash function is a mapping function of a Hash table that transforms an input of arbitrary length into an output of fixed length, which is the Hash value. Hash functions make access to a sequence of data faster and more efficient. Data elements can be quickly located by hash functions.
• Methods to solve conflicts: 1: chain address method, 2: open address method

2. Hash table structure

3, hash table implementation

class HashTable{
    / / property
    constructor() {this.storage=[]// As an array, store elements
        this.count=0// To record the number of hashtables stored
        this.limit=7// Represents the current constant of the array
    }
    / / the Hash function
    hashFunc(str,size){
        /*1, converts the string to a larger number :hashCode,2, compresses the larger hashCode into the range of the array (size), size: represents the string passed in, size: represents the size of the array */
        //1, define the hashCode variable
        var hashCode=0
        //2, Horner algorithm, to calculate the value of hashCode
        for(var i=0; i<str.length; i++){ hashCode=37*hashCode+str.charCodeAt(i)
        }
        //3, mod
        var index=hashCode % size
        return index
    }
    // Insert and modify hashTable
    /* 1; /* 1; /* 2; /* 1; /* 1; /* 1; /* 1; /* 1; /* 1; /* 2; /* 2; /* 2; /* 2; /* 1; /* 2; /* 2; /* 2; /* 2; /* 2; /* 2; /* 2; /* 2; /* 2; /* 2; /* 2; /* 2; /* 2; /* 2; /* 2; /* 2; /* 2
    put(key,value){
        //1, obtain the corresponding index based on key
        var index=this.hashFunc(key,this.limit)
        //2; // bucket is an array
        var bucket=this.storage[index]
        // Check whether the bucket exists
        if(bucket==null){
            bucket=[]
            this.storage[index]=bucket
        }
        //4, check whether data is modified
        for(var i=0; i<bucket.length; i++){var tuple=bucket[i]
            if(tuple[0]==key){
                tuple[1]=value
                return}}//5, perform the add operation
        bucket.push([key,value])
        this.count+=1
        // Determine whether capacity expansion is required
        if(this.count>this.limit*0.75) {var newPrime=this.getPrime(this.limit*2)
            this.resize(newPrime)
        }
    }
    // Get operation
    /* 1; /* 2; /* 2; /* 1; /* 2; /* 2; /* 2; Check whether each key in the bucket is equal to the incoming key. If it is equal to the incoming key, return value 5. If no corresponding key is found, return null */
    get(key){
        // Get the corresponding index based on Key
        var index=this.hashFunc(key,this.limit)
        // Get the corresponding bucket according to index
        var bucket=this.storage[index]
        // Check whether the bucket exists
        if(bucket==null) {return null
        }
        for(var i=0; i<bucket.length; i++){var tuple=bucket[i]
            if(tuple[0]==key){
                return tuple[1]}}// Still not found
        return null
    }
    // Delete operation
    /* 1, check whether the bucket is null, if not, return null 4, linear search bucket, find the corresponding key, and delete 5. If still not found, return null */
    remove(key){
        // Get the corresponding index based on key
        var index=this.hashFunc(key,this.limit)
        // Get the corresponding bucket according to index
        var bucket=this.storage[index]
        // Check whether the bucket exists
        if(bucket==null) {return null
        }
        // If there is a bucket, do a linear search and delete it
        for(var i=0; i<bucket.length; i++){var tuple=bucket[i]
            if(tuple[0]==key){
                bucket.splice(i,1)
                this.count-=1
                // Shrink the capacity
                if(this.limit>7 && this.count<this.limit*0.25) {var newPrime=this.getPrime(Math.floor(this.limit/2))// Make sure that math.floor is an integer
                    this.resize(newPrime)
                }
                return tuple[1]}}//5
        return null
    }
    // Check whether HashTable is empty
    isEmpty(){
        return this.count==0
    }
    // Get the number of HashTable elements
    size(){
        return this.count
    }
    / / HashTable expansion
    resize(newLimit){
        //1, save the old array
        var oldStorage=this.storage
        // Reset all attributes
        this.storage=[]
        this.count=0
        this.limit=0
        // Iterate over all buckets of oldStorage
        for(var i=0; i<oldStorage.length; i++){//3.1 Remove the corresponding bucket
            var bucket=oldStorage[i]
            //3.2 Check whether the bucket is empty
            if(bucket==null) {continue
            }
            // if the bucket contains data, insert it again
            for(var j=0; j<bucket.length; j++){var tuple=bucket[j]
                this.put(tuple[0],tuple[1])}}}// Check whether a number is prime
    isPrime(num){
        var temp=parseInt(Math.sqrt(num))
        for(var i=2; i<=temp; i++){if(num % 2= =0) {return false}}return true
    }
    // If it is not prime, let it increment to get prime
    getPrime(num){
        while(!this.isPrime(num)){
            num++
        }
        return num// This number is prime}}/ / create a HashTable
var ht=new HashTable()
ht.put('one'.'1')
ht.put('two'.'2')
ht.put('three'.'3')
ht.put('four'.'4')
ht.put('five'.'5')
ht.put('six'.6)
ht.put('seven'.'7')
console.log(ht)
Copy the code