Hash tables are a data structure that maps its contents to particular keys. To achieve this mapping, programmers use hash functions to transform data of the stored elements into identifiable keys, referred to as buckets. Ideally, a hash function transforms each possible input value to a unique key, allowing for exceptionally quick data storage and retrieval that does not depend on the hash table’s size (Tutorialspoint.com, n. d.). However, sometimes a hash function can assign the same key to multiple distinct objects; this event is called a collision. There are two ways of resolving collisions: chaining and linear probing. In chaining, each bucket is assigned with an additional data structure. Buckets for chaining are commonly implemented using linked lists to store elements that share a key. In linear probing, each bucket can only store one element, and the algorithm tries to place new element in the first available bucket in case of a collision.
Hash tables allow data to be stored and retrieved quickly. However, the hash function itself takes some time to execute. Therefore, in situations where one does not need to search for specific items often, hash tables are not the optimal solution. Moreover, though common hash functions exist, they do not necessarily create unique or rarely-repeating keys for the data with which they work. Thus, the data structure can require additional time to develop a custom hash function suited for the type of data meant to be stored. The choice between chaining and linear probing depends on how often one expects the hash function to create collisions and how much the amount of data will fluctuate. Chaining generally handles overflow well due to individual linked lists’ ability to expand and shrink as necessary. Linear probing, conversely, has a limited maximum size, thus limiting the maximum amount of memory the structure will take.
Reference
Tutorialspoint.com (n. d.). Data Structure and Algorithms – Hash Table.