Data Structures - Create a Hash Table

I understand how a hash table works and is implemented. The only thing I am caught up on when creating a hash table is the verbiage. After watching many YouTube videos and online explanations, everyone (in the constructor) uses some combination of 2 of these —> size, buckets and length. I am having difficulty extracting the meaning of what is being done/ created in the constructor. Creating a size and a length is confusing bc they seem to mean the same thing. The same for buckets and size. Would the amount of buckets available not be the size available? I have included two examples of the many variations i’ve come across. Any insight would be greatly appreciated!!

Example 1: Why is size 0? Wouldn’t the size be the amount of buckets which is 127? Why is size even necessary when the table is stated to be 127?

class HashTable {
constructor() {
this.table = new Array(127);
this.size = 0;
}
}

Example 2:

class HashTable {
constructor() {
this.size = 20
this.buckets = Array(this.size)
}
}

Your code so far

var called = 0;
var hash = string => {
  called++;
  var hashed = 0;
  for (var i = 0; i < string.length; i++) {
    hashed += string.charCodeAt(i);
  }
  return hashed;
};

var HashTable = function() {
  this.collection = {};
  // Only change code below this line
  this.add = (key, value) => {
    const hashedKey = hash(key);
    
  }
  
  // Only change code above this line
};

Your browser information:

User Agent is: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/105.0.0.0 Safari/537.36

Challenge: Data Structures - Create a Hash Table

Link to the challenge:

I’m gonna take a stab at this. So I hope I don’t ‘hash it up’ for you.

so if a hash table is a table, what words do we associate with tables?
Tables have rows. The number of rows helps us know the size of the table. But what if the table is actually a list of stuff. Then size would be ‘length’ right? So let’s call it length from now on.

Normally tables also have ‘cells’. But what if the ‘cell’ at each row was actually a ‘bucket’ instead?

So a table of buckets. Which has a number of rows. That number is the length of the hash table. Great.

But buckets can hold more than one thing? how big are these buckets? What are their size? Depends. Some buckets are elastic some are fixed in size. If they’re elastic, their size can change depending on how many things are in them.

So size then is how many things the bucket can hold or is holding? Yeah, that could be true (depends on the implementation)

And working backwards, buckets are just cells in the table? Yup.

And the number of rows in this table is the length cuz it’s just a list in many cases (could be an array too). Yes, the length of the hash is how many rows it has (or how many buckets)

ps. size and length are interchangeable in my view (depends on the implementation. Arrays have size, lists have lengths)

Wow. That was a great breakdown. Better than anything I came across on the web. So using this example which was taken from an FCC article https://www.freecodecamp.org/news/javascript-hash-table-associative-array-hashing-in-js/:

class HashTable {
  constructor() {
    this.table = new Array(127);
    this.size = 0;}}

127 would be the number of rows as well as the length (depicted in the image under “buckets)”?

And this.size would indicate the size of the bucket or how much it can hold? Strange that it is 0. Would that mean the bucket couldn’t hold anything? lol

yes 127 is the size of the array which we are using to hold the buckets.

in the article you linked size is the number of things currently hashed (so every time you add something to the table, the size gets incremented by one)

This is not the same thing as the size of the bucket (in the article the bucket holds only one thing so they don’t keep track of its size. Other implementations, buckets can hold any number of things)

In the article, calling remove decrements the size variable.

Copy that. So, by default, if not stated explicitly in some way, a bucket will hold one key/ value pair, and if another item happens to hash to an occupied bucket, the former will be overwritten?

Also, if a bucket can hold more than one item, would that be considered accounting for collision by using some implementation to allow for multiple items in a single bucket?

by default no.
This is code that someone wrote to work a specific way (it is a custom implementation of a hash table)

If you are talking about the basic JavaScript implementation of a hashtable using a Map object or an Object object then yes, there is one key and one value. (that value may also be a map or an object though) I hope I’m not confusing you.

collision handling… big subject.
It depends on whether you are asking about the specific implementation you are quoting from (they have their own way of dealing with it) or the basic one (a simple map would just overwrite the value if you wrote another one on top)

Your input has been exactly what I needed. I think I am going to revisit all the material I was going through and see if I can piece it together better now. Your original breakdown was far better than anything I found on the web or YouTube. It should be used in the lesson TBH :joy:

1 Like

So is the hash table code we have been speaking of just what is happening behind the scenes in the JS Map data structure (more or less). Basically, it is up to the JS engine/ browser to decide what type of hash table custom code they want to implement to meet the specifications for the Map data structure? From MDN: “specification requires maps to be implemented "that, on average, provide access times that are sublinear on the number of elements in the collection””. I think a large part of my confusion lies in assuming they are different which I am learning is not the case. I’m assuming the reason we are learning hash tables is to understand what goes on under the hood with Maps and also to be able to adjust the code to accommodate for unique situations that call for it. Is that correct?

I cannot speculate about how the JS engines are implementing their Map structures. They may or may not use a hash table type of structure under the covers.

When I learned about hash tables, I had never heard of Maps. (I wasn’t learning Javascript at the time). The hash table is a data structure that has nothing to do with javascript. (you can use javascript to implement it but it is not of javascript).
Understanding what a hash table is and how to make one is useful for software engineering purposes. You may never have to make a custom implementation (I have never had to except for the purpose of a course I was taking). You can certainly just use Maps for instance and never have to worry about making a custom data structure of your own.

So I would say, you should learn about hash tables because it is a valuable data structure in software engineering but not so that you can understand how JS maps work. (that’s my 2 cents anyway, others may have different thoughts).

Since I can still sense some confusion in your post. I will suggest that you make sure you 100% understand maps first. Then you can slowly add to your understanding by looking at hash tables again (you can do that for eg by building a custom table to hash a large dictionary of words to make look-ups for misspelled words quickly)

hope this helps

1 Like

Very helpful. Thank you.

1 Like