Cache-tries: concurrent lock-free hash tries with constant-time operations

Abstract

Concurrent non-blocking hash tries have good cache locality, and horizontally scalable operations. However, operations on most existing concurrent hash tries run in O(log n) time.