While it is important that you understand in theory and principal that how a HashMap works, its easier to understand it with the help of an implementation, which in this case is Java. They keep it updating for Time and Space complexity.
- Hash Map has a complexity of O(1) for both get and put in the best case, but get operation can worsen to O(n) in worst case.
- Hash Maps works on hashing principles. There is a bucket with an address which is a number.
- Hash code is a number that represents a bucket where 1 or more than 1 entries (key-value pairs) will be inserted. With in a bucket values are stored as Entry objects which contain both key and value.
- HashMap uses the hashCode() method (also in Object class but can be overridden) to calculate a hash value. Hash value is calculated using the Key object. This hash value is used to find the correct bucket where Entry object will be stored.
- Hashing collision occurs when more than one Key has the same hash code, in that case, a linked list is used to store multiple items in the same bucket. Entry objects are stored as a linked-list with in a same bucket.
- HashMap uses the equals() method to find the correct Key whose value is to be retrieved in case of get() and to find if that key already exists or not in case of put().
- The worst case scenario occurs where there are so many collisions that a Linked-List keeps growing, and it takes O(n) time to look for an item.
- In Java 8 hash elements use balanced trees instead of linked lists after a certain threshold is reached while storing values. This improves the worst case performance from O(n) to O(log n).
Comments
Post a Comment