# Leapfrog Probing DevFeed: [Leapfrog Probing]() Original publisher: [Read original article]() Author: Jeff Preshing Published: 2016-03-14T20:24:00Z Content type: article Language: en Sources: [Jeff Preshing]() Topics: [Data structures](), [Caching]() Tags: [alternatives](), [benchmarks](), [data](), [linear](), [search](), [strategy](), [structure]() ## AI overview The article explains hash tables and compares collision-resolution strategies, focusing on open addressing, linear probing, and a new strategy called Leapfrog Probing. ## Source excerpt A hash table is a data structure that stores a set of items, each of which maps a specific key to a specific value. There are many ways to implement a hash table, but they all have one thing in common: buckets. Every hash table maintains an array of buckets somewhere, and each item belongs to exactly one bucket. To determine the bucket for a given item, you typically hash the item's key, then compute its modulus - that is, the remainder when divided by the number of buckets. For a hash table with 16 buckets, the modulus is given by the final hexadecimal digit of the hash. Inevitably, several items will end up belonging to same bucket. For simplicity, let's suppose the hash function is invertible, so that we only need to store hashed keys. A well-known strategy is to store the bucket contents in a linked list: This strategy is known as separate chaining. Separate chaining tends to be relatively slow on modern CPUs, since it requires a lot of pointer lookups. I'm more fond of open addressing, which stores all the items in the array itself: In open addressing, each cell in the array still represents a single bucket, but can actually store an item belonging to any bucket. Open addressing is more cache-friendly than separate chaining. If an item is not found in its ideal cell, it's often nearby. The drawback is that as the array becomes full, you may need to search a lot of cells before finding a particular item, depending on the probing strategy. For example, consider linear probing, the simplest probing strategy. Suppose we want to insert the item (13, "orange") into the above table, and the hash of 13 is 0x95bb7d92. Ideally, we'd store this item at index 2, the last hexadecimal digit of the hash, but that cell is already taken. Under linear probing, we find the next free cell by searching linearly, starting at the item's ideal index, and store the item there instead: As you can see, the item (13, "orange") ended up quite far from its ideal cell. Not great for lookups.