Definition: A dictionary implemented with two hash tables, T1 and T2, and two different hash functions, h1 and h2. Each key, k, is either in T1[h1(k)] or T2[h2(k)]. A new key, k, is stored in T1[h1(k)]. If that location is already occupied by another key, l, the other key is moved to T2[h2(l)]. Keys are moved back and forth until a key moves to an empty location or a limit is reached. If the limit is reached, new hash functions are chosen, and the tables are rehashed. For tables that are a bit less than half full and with carefully chosen universal hashing functions, performance is good. A key is deleted by removing it from a table.
Read full article from cuckoo hashing
No comments:
Post a Comment