This paper is a great intro to cuckoo hash tables: http://www.ru.is/faculty/ulfar/CuckooHash.pdf http://www.ru.is/faculty/ulfar/CuckooHash.pdf Since you have m

This paper is a great intro to cuckoo hash tables: http://www.ru.is/faculty/ulfar/CuckooHash.pdf http://www.ru.is/faculty/ulfar/CuckooHash.pdf Since you have multiple hash functions in use at the same time you can simply increase the number of hash functions when you grow a table to include ones that also cover the new table space. You can then lazily hash keys with the new functions whenever they are cuckooed out of the current position, and perform lookup with all of them. If you keep track of how many elements are using each function, you can then start deprecating the old ones once all of their keys have been hashed with the new range.