Open Addressing
Open addressing is a method used in hash tables to resolve collisions, which occur when two keys hash to the same index. Instead of using a separate data structure for collisions, open addressing finds the next available slot within the same array. This is done through probing, where the algorithm checks subsequent indices until an empty slot is found.
There are various probing techniques, such as linear probing, quadratic probing, and double hashing. Each method has its own way of determining the next index to check. Open addressing can lead to better cache performance and memory usage compared to separate chaining, another collision resolution technique.