Extendible hashing is a mechanism that allows two-level access to an arbitrary number of records using a hash function. The scheme is dynamic, allowing the hash table to grow and shrink as records are inserted and deleted.

This paper presents algorithms for allowing concurrent operations on extendible hash tables to occur safely. Algorithms are presented for search, insertion, modification, and deletion. Page modification is permitted concurrently with directory contraction and expansion. The algorithm uses the verification scheme of optimistic concurrency control and an additional “soft” lock. It is based on a two-phase locking policy and uses transaction rollback and blocking to resolve conflicts among concurrent transactions. It is both deadlock-free and non-preemptive.

Simulations demonstrate the method’s utility and its advantage over previous methods presented by the author and others. The paper is highly readable and presents a useful technique that might be used to implement practical, efficient dynamic record management systems.