Bucketing
Bucketing makes the hash table a 2D array instead of a single dimensional array. Every entry in the array is big enough to hold N items (N is not amount of data. Just a constant).
Problems:
- Lots of wasted space.
- If N is exceeded, another strategy will need to be used
- Not good for memory based implementations but doable if buckets are disk-based)
For bucketing it is alright to have . However, the higher is the higher a chance of collision. guarantees there will be at least 1 collision (pigeon hole principle). That will increase both the run time and the possibility of running out of buckets.
For a hash table of N locations and X buckets at each location:
- Successful Search - O(X) worst case
- Unsuccessful Search - O(X) worst case
- Insertion - O(X) - assuming success, bucketing does not have good way to handle non-successful insertions.
- Deletion - O(X)
- Storage: O(N * X)