LKRhash is a hashtable that scales to multiple processors and to millions of items. LKRhash was invented at Microsoft in 1997 by Per-Åke (Paul) Larson of Microsoft Research and Murali Krishnan and George Reilly of Internet In­for­ma­tion Services. LKRhash has been used in many Microsoft products. The techniques that give LKRhash its per­for­mance include linear hashing, cache-friendly data structures, and fine-grained locking.

• Northwest C++ Users’ Group talk, June 2012. Speaker Deck Slides.
• Un­pub­lished paper submitted to Software: Practice & Experience (Oct 1999).
• US 6,578,131 patent. Associated PDF contains some of the SP&E paper.

If Microsoft had had 20% time, LKRhash would have been my main 20% project. I put a lot of effort into making it a polished, well-tuned library that was used in multiple products across the company. I even ported the C++ code to kernel mode, though it never ended up in a production driver, as far as I know. Several years ago, after I left Microsoft, I attempted to get it open-sourced. However, despite some help on the inside, we were never able to surmount the legal barriers.