Same lol
Even tho I wanna go to a better college outside of my country, they just won't let me..
But when my bro want it, they just let him..
Life is so unfair.. (｀^´)
Tr.2632N.US/jH4952gp

In hash function, why are we shifting by multiples of 8?

Shifting operations are the bits level. 1 byte = 8 bits. So, we use multiple of 8 to avoid bytes overlap

Thank you for the wonderful explanation with examples.

Shouldn't insert complexity for "Queue (naive array impl.)" be O(1) as it will use Array.push for insert. In the table you mentioned the opposite "Insert (Array.shift)". Array.shift is for removing 1st element.

Nice catch! Updated the post. Thanks for letting me know!

Great post adrian.
I have a confusion of what's the difference between javascript object and a hash table?
I've read that javascript objects are implemented using hash tables at it's core.
Also insert, delete and accessing the properties of objects can be achieved in O(1) time, it's becuase of this reason i'm unable to decide what data structure i should use for the below problem statement i came across:
Build a search utility function/class that given a search query, searches the book summaries and returns the K most relevant ones. A search engine query is the set of
keywords that users will type in order to find a relevant document.
Eg: query (string): eg. 'is your problems'
No of results(integer): eg. 3
Output: List of K relevant summaries sorted according to order of relevance given a query.
A summary is a dictionary that follows the schema: {'summary': string, 'id': integer}.

Adrian Mejia Please give me some inputs on this asap.

Chaitanya Sairam You can use an Object and Map interchangably in most cases. But, it's recommended to use Map because it's optimize for that. Here are some differences:
- Objects keys should be strings or number, while on Maps can be anything. You can have a key as array or even another object.
- If you use an Object as a map and want to get the keys, you have to use `hasOwnProperty` or `Object.keys`. However, you might also get functions if you define them in the object. If you use a Map, you don't have to worry about your map being used for another thing other than map unlike objects.

6.1 Singly Linked List
Repeted the addFirst() method
Here is a solution:


removeFirst() {
let current = this.root;
if (current && current.next) {
this.root = this.root.next;
} else this.root = null;
if (current) return current.value;
};
};


Good catch, thanks for pointing that out. It's fixed now

Deletion of key from keys array will not work as on Line 83 in HashMap class "keyIndex" will be undefined as _getIndexes will never return this value.

1) Is deleting key from keys array actually required? Not deleting will have a duplicate entry for the same key.
2) To delete the key from keys array:
Add on Line 75:

const keyIndex = entry.keyIndex;
return {bucketIndex, entryIndex, keyIndex};

What implementation were you using? The most up-to-date is https://github.com/amejiaro.... All the previous implementations are simpler and builds up to this last one. Let me know if you see an issue on that one.

I had never seen such a brilliant way of explaining the HashMap. And furthermore it is in Javascript. Impressive !

Thanks! I'm glad you liked it!

1)

What is the runtime of approach #1 using two arrays? If we say, the number of words in the text is n. Then we have to search if the word in the array A and then increment the value on array B matching that index. For every word on n, we have to test if it’s already on array A. This double loop leave use with a runtime of O(n2).

Not clear description for me, could you please clarify. Is array A already contains all the unique words in text or it is empty initially and we go over the text and then fill the array A based on it and array B? If the first statement is correct then why should we check for the word existence as it is already prepopulated for us? If the second, then it makes sense, but I think a better description should be provided.

2) Seems like mistake here: insert should be called with object.

function insert(object, key, value) {
  object[key] = value;
  return object;
}

const object = {};
console.log(insert(hash, 'word', 1)); // => { word: 1 }

3) remove method in Singly Linked List: IMO it is suboptimal to iterate over the list and while being on the last item realise that we are going to remove the last item and then use removeLast() method which iterates from the beginning again. I think this method should not be used at all and the initial iteration should count for this case.

See in the buckets where the k, v objects are ... where are the values coming from? Like why is “art” 8? And “cat” 2? And “rat” 7?

I didn't know that in the ES6 `Set` has a linear time complexity for checking if an element exists or not i.e. `set.has` 😅

Handling duplicate in HashMap

set (key, value) {
const bucketIndex = this.getIndex(key);
if(this.buckets[bucketIndex]) {
const dupKeyIndex = this.buckets[bucketIndex].findIndex(bucket => bucket.key === key)
if (dupKeyIndex >= 0) this.buckets[bucketIndex][dupKeyIndex] = {key, value}
else this.buckets[bucketIndex].push({key, value})
if(this.buckets[bucketIndex].length > 1) { this.collisions++; }
} else {
this.buckets[bucketIndex] = [{key, value}];
}
}

6.1 Singly Linked List
The remove() method use index, I don't know why... and maybe been copied from another code because handle the size (this.size -- at line 12) while this class has not size properties...
I wrote a remove method with value:

remove(value) {
let current = this.root;
let target;
if (!(current)) return;
if (current.value === value) return this.removeFirst();
while (current) {
if (current.next && current.next.value === value) {
target = current.next.value;
current.next = current.next.next;
break;
}
current = current.next;
}
return target;
};


Csaba you are right, I missed adding the size attribute on the constructor, I added it back. You can see my full implementations of the LinkedList on Github repo: https://github.com/amejiaro...

In there you will notice that I have a "removeByPosition", I think it's a good idea to implement a "removeByValue" as you pointed out

What is with the native function map in JS? Is this a good hash function?

You should go with native functions whenever it fits your needs. They are optimized and battle-tested. We implemented a hash map here for learning purposes to understand how they work behind the scenes.