Hash bucket

The collection of records assigned to one bucket index by a hash function. In separate chaining, an array slot refers to this collection, which may be empty.

For $m>0$ hash buckets, number them $0,\dots ,m-1$ and write ${\ell }_j$ for the number of records in hash bucket $j$. Each record belongs to exactly one hash bucket, soAn empty hash bucket contributes zero to this sum but still contributes one to the denominator $m$. The hash table load factor therefore measures records per allocated hash bucket, not records per nonempty hash bucket. A hash bucket is a destination selected by the bucket-index hash function; with separate chaining, its records need not occupy consecutive positions in computer memory.

For the twelve-record concentrated placement in load factor of a hash table, one hash bucket contains twelve records and seven hash buckets are empty. Averaging only over nonempty hash buckets gives $12$, whereas the hash table load factor is $12/8=1.5$. This difference matters when deciding how much array capacity to allocate. For $n>0$, the largest hash bucket satisfies $\lceil n/m\rceil \le {\max }_j{\ell }_j\le n$; the lower bound follows because at least one entry cannot be below the arithmetic mean. Neither inequality says that an actual hash function achieves a balanced placement.