> For the complete documentation index, see [llms.txt](https://catherine-leung.gitbook.io/data-strutures-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://catherine-leung.gitbook.io/data-strutures-and-algorithms/table/hash-tables/bucketing.md).

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