Research work · 2022
Hash Tables
G A Vijayalakshmi Pai
Abstract
Hash tables are ideal data structures for dictionaries. This chapter introduces the concept of hashing and hash functions. The choice of the hash function plays a significant role in the structure and performance of the hash table. In the case of linear open addressing, the solution of accommodating synonyms in the closest empty slot may contribute to a deterioration in performance. While increasing the number of slots to minimize overflows may lead to wastage of memory, containing the number of slots to the bare minimum may lead to severe overflows hampering the performance of the hash table. The chapter discusses the application of hash tables in the fields of compiler design, relational database query processing and file organization. A linked implementation of a hash table is known as chaining. In this all the synonyms are chained to their respective buckets as a singly linked list.