The Joys of Hashing: Hash Table Programming with C

© Thomas Mailund 2019

Thomas MailundThe Joys of Hashinghttps://doi.org/10.1007/978-1-4842-4066-3_3

3. Collision Resolution, Load Factor, and Performance

Thomas Mailund¹ 

(1)

Aarhus N, Denmark

 

Collisions are inevitable when using a hash table, at least if you want the table size, and thus the initialization time for the table, to be linear in the number of keys you put into it. Therefore, you need a way to deal with collisions so you can still insert keys if the bin you map it to is already occupied. There are two classical approaches to collision resolution: chaining (where you use linked lists to store colliding keys) and open addressing (where you find alternative empty slots to store values in when keys collide).

You can download the complete code ...