Internal Working of Hashmap
● What is Hashmap?
● What is Hash Function?
● What is Hash Table?
● How to insert data into Hash Table?
● How to fetch data from Hash Table?
● Complexities
What Is HashMap ?
● HashMap is combination of two words i.e. Hash+Map. We calculate
hash to store a mapping (key-> value).
● No duplicate keys inside one hashmap.
● In case of duplicate keys, older value gets overridden.
● Does not maintain any order i.e. unordered data.
● Key and value can be of any type (Integer, String, custom class
etc.)
● DataTypes are specified using wrapper classes for primitive data
types.
● Eg: HashMap<Integer, String> hmap = new HashMap<>();
(1, “student1”), (2,”student2”) etc.
What is Hash function?
● Map Larger values to smaller values.
○ h(2192345) = 7,
○ h(“alphaNumeric”) = 3
○ h({“jsonKey” : “jsonValue”}) = 2
This smaller value can be in any format but in java it returns an Integer.
● Hash Function should provide results in O(1) that means there should be some
direct formula without for loop.
○ In case of String it can go till length ie O(n) where n is length.
● Should uniformly distribute the generated keys into hash Table.
What is Hash function?
● If a function is returning some value for some key, It will always return the
same value.
○ Eg h(213456) = 7 then h(213456) will never come 6 or any other number
except 7.
● Same hash Value can be returned for different key.
○ Eg h(87654567) can also be 7. Collision
What is a Hash Table?
● It’s an Array of Node.
Class Node{
K key,
V value,
int hash,
Node next,
● HashTable: Node[] hashTable = new Node[8];
How to insert data into hashTable?
Let’s Try to understand it with help of Example.
● Keys = [24, 16, 12, 12, 17, 18, 10, 9]
● Hash Function -> h(keys) = key % 7
How to insert data into hashTable?
How to fetch data from hashtable?
Complexities
Complexities:
O(1 + length of chain)
Because on the same index we have more than 1 value.
At a certain length, we convert the linked List to self
balancing tree after java 8.