Hash Tables
A Hash Table stores Key-Value Pairs, determining the index for each pair by calculating the hash code of the Key and applying modulo operation with the table's size (Key % size of the table).
However, this process can lead to collisions, where multiple pairs end up with the same index. In Hash Tables, collisions are managed by storing the colliding pairs in the same index using a linked list structure, forming what is referred to as a bucket.
- Best Case: O(1)
- Worst Case: O(n)
Minimizing collisions is crucial for optimal performance. Increasing the size of the table reduces collisions but increases space complexity. It's essential to strike a balance between space usage and collision minimization.
The hash code of the Key determines its index in the table. For Keys initialized as integers, the hash code equals the Key itself. For other types, Java provides a hashCode() method for every Java object.