Hash Table Flashcards
What is hash functions?
A hash function is a function where you put in a string and you get back a number.
“maps strings to numbers.”
requirements for a hash function:
• It needs to be consistent. For example, suppose you put in “apple” and get back “4”. Every time you put in “apple”, you should get “4” back. Without this, your hash table won’t work.
• It should map different words to different numbers. For example, a hash function is no good if it always returns “1” for any word you put in. In the best case, every different word should map to a different number.
it assigns a spot in the array alphabetically.
What is hash table?
It’s a Data structure, combined array and hash functions,
Hash table have keys and value,
- hashes are good for:
• Modeling relationships from one thing to another thing
• Filtering out duplicates
• Caching/memorizing data instead of making your server do work
What is collisions?
It’s when two values assign to the same key,
What the solution collision?
The simplest solution is this: if multiple keys map to the same slot, start a linked list at that slot.
What is the “constant time”?
It’s where algorithm take o(1), that’s mean that the time taken to perform will remain the same
What in the big O for hash table?
In average case => O(1)
In worst case => O(n)
How to avoid collision?
To avoid collisions, you need
• A low load factor
• A good hash function
What is “ load factor”?
It’s measures how many empty slots remain in your hash table.
Load factor = No. of items in the hash table / total No. of slots
Having a load factor greater than 1 means you have more items than slots in your array.
What is resizing?
It’s when you add more slots to your hash table
resize when your load factor is greater than 0.7
What is the good and bad hash function?
The good hash function distributes values in the array evenly.
The bad hash function groups values together and produces a lot of collisions.
