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 λ>1 \lambda > 1 . However, the higher λ \lambda is the higher a chance of collision. λ>1 \lambda > 1 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)

results matching ""

    No results matching ""