Hash Table



Today I learned about Hash Tables, it's basicly a data-structure of a an pre-determine length with a key and value pair as it's data. An object in most coding languages.

{
  key: "John",
  value: "123-456-7890"
}

It's a really cool way of storing data because it's super fast.
It's consistent time insertion and look up.

Big O notation of 1.
O(1) run time, if you do your hash function correctly.

Which bring me to the next part the "Hash Function"

A hash function is a function that takes an input, the keys in this case and do some kind of "magic" with it and give you some kind of indexes as it's output. The output is uses in this case as the indexes for your hash table.

When you have to look up the data you can gave your query the key of the data and the hash will always give you back the same index, which you can use to find your data.

One issue you are going to run into...get it run into...is when an collision happens. When the index given by the hash function gives the same index as another key when the keys have different values.
One way to avoid this issue is to have a very good hash function that always generate unique indexes...or.

You create a Linked List inside of your hash table, and build a list one after another if they happen to be in collision.

At this point I know all the memes and jokes about imagery scaling issue, but doing it this way with linked list inside of hash table is kind of a scaling issue. Having many many linked list can slow down the Hash Table run time, so it really depends how good your hash function is.

Thats it for Hash Tables.
Up next I will try to write out in Js the Alogorithms in Aditya Y.Bhargava's book which is mostly written in Python.

Comments

Popular posts from this blog

Linked List

CSS Review