Hash
A hash function takes data (like a string, or a file’s contents) and outputs a hash, a fixed-size string or number.
For example, here’s the MD5 hash (MD5 is a common hash function) for a file simply containing “cake”:
DF7CE038E2FA96EDF39206F898DF134D
And here’s the hash for the same file after it was edited to be “cakes”:
0E9091167610558FDAE6F69BD6716771
Hash Table
Other names:
hash, hash map, map, unordered map, dictionary
A hash table organizes data so you can quickly look up values for a given key.
Strengths:
Fast lookups. Lookups take O(1)O(1) time on average.
Flexible keys. Most data types can be used for keys, as long as they're hashable.
Weaknesses:
Slow worst-case lookups. Lookups take O(n)O(n) time in the worst case.
Unordered. Keys aren't stored in a special order. If you're looking for the smallest key, the largest key, or all the keys in a range, you'll need to look through every key to find it.
Single-directional lookups. While you can look up the value for a given key in O(1)O(1) time, looking up the keys for a given value requires looping through the whole dataset—O(n)O(n) time.
Not cache-friendly. Many hash table implementations use linked lists, which don't put data next to each other in memory.
Hash maps are built on arrays
Arrays are pretty similar to hash maps already. Arrays let you quickly look up the value for a given "key" . . . except the keys are called "indices," and we don't get to pick them—they're always sequential integers (0, 1, 2, 3, etc).
Think of a hash map as a "hack" on top of an array to let us use flexible keys instead of being stuck with sequential integer "indices."
All we need is a function to convert a key into an array index (an integer). That function is called a hashing function.
Hash collisions
What if two keys hash to the same index in our array?
This is called a hash collision.
When hash table operations cost O(n)O(n) time
Hash collisions
Dynamic array resizing
Sets
A set is like a hash map except it only stores keys, without values.
Sets often come up when we're tracking groups of items—nodes we've visited in a graph, characters we've seen in a string, or colors used by neighboring nodes. Usually, we're interested in whether something is in a set or not.
Thanks for reading <3
Hope you got good idea of hash and hashmap
Top comments (0)