Menu
I've recently learned a little bit about hash values, and therefore also heard of about the problem of hash collisions.
I therefore wondered: How does one deal with those?
E.g. Swift's Dictonary uses hash values with its keys. I assume that it looks up its values via the hash. So how would Swift's Dictionary then store values for different keys, that happen to have the same hash?
302
One method for resolving collisions looks into the hash table and tries to find another open slot to hold the item that caused the collision. A simple way to do this is to start at the original hash value position and then move in a sequential manner through the slots until we encounter the first slot that is empty.
In computer science, a hash collision or clash is when two pieces of data in a hash table share the same hash value. The hash value in this case is derived from a hash function which takes a data input and returns a fixed length of bits.
This situation is called a collision, where there is another key that will be mapped to an occupied slot. To solve this problem, we need a collision handling technique. And here are the ways to handle collisions: Separate chaining is a technique to point each cell in a hash table to a chaining node, or a linked list.
Chaining is a technique used for avoiding collisions in hash tables. A collision occurs when two keys are hashed to the same index in a hash table. Collisions are a problem because every slot in a hash table is supposed to store a single element.
Fundamentally, there are two major ways of handling hash collisions - separate chaining, when items with colliding hash codes are stored in a separate data structure, and open addressing, when colliding data is stored in another available bucket that was selected using some algorithm.
Both strategies have numerous sub-strategies, described in Wikipedia. The exact strategy used by a particular implementation is, not surprisingly, implementation-specific, so the authors can change it at any time for something more efficient without breaking the assumptions of their users.
A this point, the only way to find out how Swift handles collisions would be disassembling the library (that is, unless you work for Apple, and have access to the source code). Curious people did that to NSDictionary, and determined that it uses linear probing, the simplest variation of the open addressing technique.
89
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
