Chaining (“Open Hashing”)
Hashing with Chaining is the simplest Collision-resolution strategy: Each slot stores a bucket containing 0 or more KVPs.
- Buckets can be implemented with any dictionary implementation, but the simplest is to use unsorted linked lists
So what is the difference between buckets and slots?
The terminology of buckets is really only used in Open Hashing. Each slot in the hash table can store multiple buckets, which are simply entries. In Closed Hashing, since each slot simply stores one number, we are then concerned with the probing sequence.
This method is called collision resolution by chaining.
The hash function used commonly here is super simple: . Closed Hashing uses more advanced hash functions.
We need to use the Uniform Hashing Assumption.
