Hashing is a technique that is used to uniquely identify a
specific object from a group of similar objects. Large keys are
converted into small keys by using hash functions. And these values
are then stored in a data structure called hash table. Distribute
entries (key/value pairs and converted key) uniformly across an
array. By using key you can access element O(1) time(time
Hashing implemented --> element converted into an integer by
using a hash function and quickly retrieved using hashed key
hash = hashfunc(key)
index = hash % array_size
Good hashing mechanism should have
Easy to compute
uniform distribution across the hash table
String str = "abcadcds";
//Time complexity of this approach is O(26*N) where N is the size of
//the string and there are 26 possible characters.
Collision resolution techniques -
open hashing /Separate chaining -
Most commonly used and usually implemented using linked lists
Two different elements have same hash value then store both the
elements in the same linked list.
The cost of a lookup is depends on distribution of the
Closed hashing/ Open addressing / Linear probing
Instead of in linked lists, all entry records are stored in the
New entry --> hash index of the hashed value is computed and
then the array is examined. If the slot at the hashed index is
unoccupied then the entry record is inserted in slot at the hashed
index else it proceeds in some probe sequence until it finds an
The probe sequence is the sequence that is followed while
traversing through entries. In different probe sequences, you can
have different intervals between successive entry slots or probes.
"Open Addressing" refers to the fact that the location or
address of the item is not determined by its hash value
Linear probing is when the interval between successive probes
is fixed to 1 (mostly)
Similar to linear probing. Difference is the interval between
successive probes or entry slots.
The interval between slots is computed by adding the successive
value of an arbitrary polynomial in the original hashed index.
Similar to linear probing and the only difference is the
interval between successive probes. Interval between probes is
computed by using two hash functions.
e.g. Database indexing, Caches(Speed up the access to data),
Object representation(Python, JS, Perl), Various algorithms,
Associative arrays(In memory tables)