Dynamic space efficient hashing (Q1999966)

The paper focuses on a new type of hashing, called Dynamic Space Efficient Cuckoo Table (DySECT), that proposes an approach to counterbalance the inhomogeneity in suitable table sizes with the flexibility of the bucket cuckoo hashing. Following of overview of existing methods and their limitations, the authors describe in detail the \(\alpha\)-space-efficient hash tables, the principles behind cuckoo hashing and the adaptations of known methods, i.e., the fast table migration and approaches based on multi-tables and in-place migration. The implementation details and an extensive analysis of possible loads are also discussed. The paper concludes with performance experiments such as the influence of the fill ratio on static and dynamic table size and the impact of parameters such as the word count. The analysis is thorough and provides broad arguments to support the claims that the proposed method is up to twice better than the next best solution.