good hashing algo with
- Lookup: O(1) worst-case. Each key can only reside in one of two possible positions (determined by two hash functions), so checking both takes constant time.
- Insertion: O(1) amortized. A new key is inserted into one of its two positions. If the position is occupied, the existing key is evicted and reinserted into its alternate position, potentially triggering a chain of displacements. While a single insertion could lead to many relocations in rare cases, the amortized time over many insertions is constant, assuming a good hash function and load factor below 0.5.
- Deletion: O(1) worst-case. Similar to lookup, deletion checks the two possible positions and removes the key if found.
tiktok uses this in their recommendation system monolith