Fast Mergeable Integer Maps

Finite maps are ubiquitous in many applications, but perhaps nowhere more so than in compilers and other language processors. In these applications, three operations on finite maps dominate all others: looking up the value associated with a key, inserting a new binding, and merging two finite maps. Most implementations of finite maps in functional languages are based on balanced binary search trees, which perform well on the first two, but poorly on the third. We describe an implementation of finite maps with integer keys that performs well in practice on all three operations. This data structure is not new---indeed, it is thirty years old this year---but it deserves to be more widely known. 1 Introduction Finite maps are the workhorse data structure in every compiler. Imperative implementations typically use hash tables, whereas functional implementations typically use balanced binary search trees. Both are good at lookups and insertions, which---not coincidentally---are the two mos..