Time evaluation of lookups with Robin Hood Hashing and Linear Probing

Abstract: Hash tables are used to store data in a way that is quickly retrieved from an array using the identifier of the data. When inserting data into a hash table it will sometimes attempt to place the data on a position in the array where there already exists data which means these collisions need to be handled. This has lead to the creation of many different types of hash tables that handle the collisions differently. Linear Probing and Robin Hood hash tables are two different types of Open Addressing hash tables that handle collisions by placing the data elsewhere in the array. This paper evaluates the time it takes to search for data in these two types of hash tables when the array is nearly full. The results show that the Robin Hood hash table is an improvement over the Linear Probing hash table when the array is roughly 90% or more full and not all of the searches are on data that exist in the array.