The team built their hash table in two parts. They had a primary data structure, in which the items are stored without any wasted bits at all, and a secondary data structure, which helps a query request find the item it\u2019s looking for. While the group did not invent the notion of a secondary data structure, they did make a crucial discovery that made their hyperefficient hash table possible: The structure\u2019s overall memory efficiency depends on how the primary structure arranges its stored items.<\/p>\n

The basic idea is that every item in the primary structure has preferred storage locations \u2014 a best location, a second-best one, a third best and so on. If an item is in its best spot, the number 1 is affixed to it, and that number is stored in the secondary data structure. In response to a query, the secondary structure provides just the number 1, which spells out the item\u2019s exact location in the primary structure.<\/p>\n

If the item is in its 100th-best spot, the secondary data structure attaches the number 100. And because the system uses binary, it represents the number 100 as 1100100. It takes more memory, of course, to store the number 1100100 than 1 \u2014 the number assigned to an item when it\u2019s in the best spot. Differences like that become significant if you\u2019re storing, say, a million items.<\/p>\n

So the team realized that if you continually shift items in the primary data structure into their more preferred locations, you could significantly reduce the memory consumed by the secondary structure without having to increase query times.<\/p>\n

\u201cBefore this work, no one had realized you could further compress the data structure by moving information around,\u201d Pagh said. \u201cThat was the big insight of the Bender paper.\u201d<\/p>\n

The authors showed that their invention established a new upper bound for the most efficient hash tables, meaning that it was the best data structure yet devised in terms of both time and space efficiency. But the possibility remained that someone else might do even better.<\/p>\n