Kollisionauflösung

Kollisionauflösung refers to the techniques used in computer science, particularly in data structures and algorithms, to handle situations where two different keys map to the same location or index in a hash table. This event is called a collision. When a collision occurs, the new data cannot be simply placed in the already occupied slot. Therefore, a strategy is needed to store and retrieve this new data without overwriting existing information or losing the new item.

There are two main categories of collision resolution techniques: open addressing and separate chaining. Open addressing methods, also known as closed hashing, store all elements directly within the hash table itself. When a collision occurs, the algorithm probes for an alternative slot within the table. Common probing strategies include linear probing, quadratic probing, and double hashing. Linear probing checks consecutive slots, quadratic probing checks slots at increasing quadratic distances, and double hashing uses a secondary hash function to determine the step size for probing.

Separate chaining, also known as open hashing, handles collisions by storing elements that hash to the same index in a separate data structure, such as a linked list or a tree, associated with that index. Each slot in the hash table then points to the head of this secondary data structure. When a collision occurs, the new element is added to the linked list (or other structure) at that index. This approach can lead to longer search times if the chains become very long, but it is generally simpler to implement and can handle a load factor greater than one. The choice of collision resolution strategy can significantly impact the performance of hash table operations, such as insertion, deletion, and search.