Hash Table
Hash Collision
Even though the two data values are different, they are converted to the same thing through the process of hashing.
Closed Hash Table
-
Close hashing = Linear Probing, Open Addressing
-
Collisions are dealt with by searching for another empty buckets within the hash table array itself
-
At most one key per bucket
Inserting
int hashFunc(29) = int hashFunc(79), so when we insert 79, the bucket is already in use. Thus, bucket = (bucket+1) % NUM_BACK = 0, so 79 goes to bucket number 0.
Deleting
After deleting 65 from bucket 5, when we search for 15, the function aborts the search as soon as it finds bucket 5 is empty!!
- Only use closed/linear probing hash tables when you don't want to delete items!
Open Hashing
-
Instead of storing values directly in the array, each array bucket points to a linked list of values
-
unlimited values!
-
A key is always stored in the bucket it's hashed to. Collisions are dealt with using separate data structures on a per-bucket basis
-
Arbitrary number of keys per bucket
Hash Table Efficiency
