Is the capacity of a hash table a constant value?

Question

In this paper, page 4, it is said:

"...there is always a constant expected number of elements that map to the same slot"

---

Assume we have a set $S$ of $n$ values, and we want to insert them into a hash table. Let's fix some parameters: let $d$ be the hash table's bin/slot capacity, i.e. the bin will get more than $d$ elements only with a negligible probability. Then, we set the hash table length, $h$.

Question 1: is it correct that the capacity of each bin is constant?

---

Moreover, assume we want to perform an operation on only one bin of the hash table.

Question 2: Is it correct to say the complexity of the operation is constant? because it performs the operation on a constant elements of the set $S$?

---

Update: Please note that the updated is inserted after the answer is given by provided by @D.W.

I am using a simple static hash table. Assume that the number of elements $n$ is known in advance. Also, for some reasons we want a bin capacity be $d$ with a high probability (e.g. $2^{40}$). Moreover, we use the equation in theorem 1, in here to calculate the number of bins (or hash table length) required. Furthermore, we want to perform a polynomial factorization, whose complexity is $O(d^{2})$, in one bin.

---

Answer 1

There are rare cases where the number of entries in a hashtable is fixed. There are some more cases where the number of entries in one particular situation is known, and the right number of slots can be allocated before you start filling the hash table.

But typical implementations start with a small number of slots, and if enough items are added so the expected number of collisions becomes too large, more slots are allocated and all items rearranged in the new slots.

Usually the implementation tries to keep the percentage of used slots in some range, say (just an example) between 45% and 70%, compromising between efficiency and used space. So as you add items and use more than 70% of slots are used, the implementer would increase the number of slots so that now 45% are used, and more items can be added. An implementer might also shrink the table if items are removed and say less than 30% of slots are used, but in practice hash tables tend to grow.

Answer 2

If I understood you correctly, your real need is a way to limit slot capacity with a high probability (BTW, probabilities cannot reach more than 100% == 2⁰; what you mean is probably 1 - 2^-40).

You can reach this goal with modified hash table handling procedure:

• Cuckoo hashing uses fixed-size slots with slower but still O(1) on average insert procedure, while allowing to reach load factor arbitrarily close to 100% by using larger slots
• Robin Hood hashing grows up the table when any hash chain becomes larger than prescribed value, but this event has very low probability (alternatively, you can just drop extra elements in such low-probable situation)
• Extensible hashing extends any approach by growing just the required parts of the hash table
• Perfect hash functions and Dynamic perfect hashing

Answer 3

I wonder if you've omitted some relevant context. If you insert $n$ items and ensure that the capacity of the hash table is $2n$, then the expected number of elements that map into any particular slot is constant ($1/2$).

The capacity of a bin depends on what kind of hashtable you're using, so it's not answerable without further context.

An operation that performs only a constant number of steps of computation, has constant complexity. So, you can count the number of steps of computation that are performed and you should be able to tell. If the expected number of elements in a slot is a constant, and if that operation takes a constant operations per element, then the expected complexity of that operation is a constant. (The worst case might be higher, as the worst-case number of elements per bin might be higher.)