Question

In 2021, Bender et al. proved that an optimal tradeoff curve for these data structures involves an exponential reduction in the number of wasted bits for each insertion. Ronald Rivest showed that the efficiency of partial-match retrieval algorithms based on these data structures is approximately equal to tree-search algorithms. David Karger introduced a method for resizing these data structures in which only a number of items equal to the (*) load (-5[1])factor must be swapped. (10[2])A scheme named for cuckoos (10[1])that implements many of these data structures has worst-case constant lookup time. (10[1])Python’s built-in dict type implements this data structure. (-5[1])Linear probing can be used to resolve collisions in these data structures. For 10 points, name these data structures that implement a one-way mapping to store key-value pairs. (10[1])■END■ (0[1])

ANSWER: hash tables [accept dictionaries until “dict” is read; accept hash maps]
<KJ, Other Science>
= Average correct buzz position

Back to tossups

Buzzes

PlayerTeamOpponentBuzz PositionValue
James WangOttawa AbsolomabsolomabsolomToronto B69-5
Mattias EhatammWaterloo AspidistraCarleton A7310
Benjamin ChapmanToronto AToronto Metropolitan A7310
Rayton LinWaterloo ClozeWaterloo Basic7810
Asha BasuMcGill AToronto Disband the Club 2k249010
Franklin WuToronto Chestnut Rice and KamehamehaMcMaster ApocolocyntosisBidii98-5
Parth JagtapToronto BOttawa Absolomabsolomabsolom12610
Yusuf BaigMcMaster ApocolocyntosisBidiiToronto Chestnut Rice and Kamehameha1270