-1

I am trying to implement hashmap functionality in JavaScript and want to keep everything in constant time.

Problem 1: Remove element from array in constant time (O(1)) And I am using array.

Problem 2: Best way to resolve collision problem in case we same hash for different keys.

Problem 3: Best way to create hashcode. Currently I am using some of ASCII values of each character.

Code example

class myHashMap {
    constructor(size = 0 ){
        if(size){
            this.hashMap = new Array(size).fill(null);
            this.size = size;
        }
            else{
            this.hashMap = new Array();
            this.size = 0;
            }

    }
    hash(key){

// Here hashing can have collision 
//for example: 122 and 212 will have same hash which is not correct
        let CharArray = key.split("");
       return CharArray.reduce((acc,current) => {
            return acc+current.charCodeAt(0);
        },0);
      
    }
    set(key,value)
    {
        this.size++;
        this.hashMap[this.hash(key)] = value;
    }

    get(key){
        return this.hashMap[key];

    }
    has(key){
        return this.hashMap[key];
    }
    remove(key)
    {

        this.size--;
         this.hashMap.splice(this.hash(key),1); 
      // Here I need to remove element in O(1)
    }
}
Faisal
  • 45
  • 1
  • 8
  • 1
    Show us what you've tried so far and provide a minimum reproducible example https://stackoverflow.com/help/minimal-reproducible-example – ᴓᴓᴓ Dec 22 '21 at 22:28
  • Does this answer your question? [JavaScript hashmap equivalent](https://stackoverflow.com/questions/368280/javascript-hashmap-equivalent) – Randy Casburn Dec 22 '21 at 22:31
  • 1
    @wooooooo I have updated question with code example – Faisal Dec 22 '21 at 22:40
  • @RandyCasburn not exactly :) – Faisal Dec 22 '21 at 22:48
  • `this.hashMap` better be called `this.backingArray` or something. It's not a hash map, the `myHashMap` instance itself is. – Bergi Dec 22 '21 at 22:56
  • 1
    Just use `this.hashMap[this.hash(key)] = null;`! Don't do any splicing, which modifies the size of the array and moves all elements after the index (`O(n)`). – Bergi Dec 22 '21 at 22:58
  • @Bergi I agree with you and I need to improve naming conventions – Faisal Dec 22 '21 at 22:59
  • @Bergi Exactly, I wanted to avoid O(N). – Faisal Dec 22 '21 at 23:00
  • 1
    "*Problem 2: Best way to resolve collision problem*", "*Problem 3: Best way to create hashcode*" - please keep it to one problem per question. And notice that Wikipedia has entire articles on [resolving hash collisions](https://en.wikipedia.org/wiki/Hash_table#Collision_resolution) and [choosing good hash functions](https://en.wikipedia.org/wiki/Hash_table#Choosing_a_hash_function) – Bergi Dec 22 '21 at 23:03
  • @Bergi Currently, I am using reduce method which will also take O(N). I need to calculate hash in O(1) also. – Faisal Dec 22 '21 at 23:03
  • 1
    @Faisal "*I need to calculate hash in O(1) also.*" - no you don't. Or, you already do - the `n` in `O(n)` refers to the size of the hash table, not the size of the key. – Bergi Dec 22 '21 at 23:05
  • @Bergi Ok. Let me post different question and yes I can see a lot of articles but its always good idea to discuss it on forums like this. Thank you :) – Faisal Dec 22 '21 at 23:05
  • 1
    @Faisal No, StackOverflow is not a discussion forum. An open-ended question like this (or even worse, something like "*What's your favourite hash function?*") will be received badly. – Bergi Dec 22 '21 at 23:06
  • @Bergi OK. Thank you for your valuable comments :) – Faisal Dec 22 '21 at 23:07

1 Answers1

0

Problem 1: Remove element from array in constant time (O(1)) And I am using array.

Unless you are using some nonstandard definition of "array", you can't remove an element from an array in constant time. You can set an item to some null value in constant time. But the standard usage of "array" means multiple items of known size that are layed out in contiguous memory such that they can be accessed by an index in constant time via pointer arithmetic. To remove an element from such a structure, meaning the array actually gets smaller, you would need to at least copy the items in the array after the item you are removing, which is an O(n) operation.

Problem 2: Best way to resolve collision problem in case we same hash for different keys.

There is no best way. There are various solutions to this problem that make different trade-offs regarding time efficiency, space, ease of implementation, and other considerations. The two most common large classes of solutions are (1) usage of a "bucket" structure, essentially making the hash table an array of mostly empty instances of another kind of container -- historically linked lists were common -- and (2) letting the table be flat and handling collisions by "open addressing" meaning probing until you find an empty slot starting at the slot found by the hash index. Of the above, generally (1) is easier to implement.

Problem 3: Best way to create hashcode. Currently I am using some of ASCII values of each character.

This is a huge subject but, yeah, you need to use the numeric values of the characters in the string, the question is what you do with those values. Look for example of the implementation of boost::hash_combine in C++ of which there are many references to on StackOverflow.

jwezorek
  • 8,592
  • 1
  • 29
  • 46