Hash Tables Under The Hood - Deepstash

Hash Tables Under The Hood

In a slightly simplified explanation, hash tables are just arrays that with the keys mapped to the indexes. A key is transformed in an index through a hash function.

A good hash function must be:

  • consistent: it should always produce the same output for the same key
  • collision-free: it should minimize the number of keys that are mapped to the same number

In case the hash function still causes collisions (e.g. for memory reasons), it could be changed so that an entry in the array no longer contains a single value, but a new data structure (such as a linked list or even a new hash table).

22

293 reads

CURATED FROM

IDEAS CURATED BY

The book covers algorithms at a basic level. I knew most of the stuff, so here are only so brief notes I took.

Similar ideas to Hash Tables Under The Hood

B-Trees

B-Trees

PostgreSQL implements several types of indexes, such as btree, hash, gist, spgist. The default and most common type of index is btree. A btree (balanced tree) allows for easier and faster searching. This can be seen in the image above where we search for the key with the value of 53. 

Btree...

Read & Learn

20x Faster

without
deepstash

with
deepstash

with

deepstash

Personalized microlearning

100+ Learning Journeys

Access to 200,000+ ideas

Access to the mobile app

Unlimited idea saving

Unlimited history

Unlimited listening to ideas

Downloading & offline access

Supercharge your mind with one idea per day

Enter your email and spend 1 minute every day to learn something new.

Email

I agree to receive email updates