18.1 Representing Sets as Lists
18.1.1 Representation Choices
18.1.2 Time Complexity
18.1.3 Choosing Between Representations
18.1.4 Other Operations
18.2 Making Sets Grow on Trees
18.2.1 Using Binary Trees
18.2.2 Checking the Complexity
18.2.3 A Fine Balance: Tree Surgery
18.2.3.1 Left-Left Case
18.2.3.2 Left-Right Case
18.2.3.3 Any Other Cases?
18.3 Union-Find
18.3.1 Implementing with State
18.3.2 Optimizations
18.3.3 Analysis
18.4 Hashes, Sets, and Key-Values
18.4.1 A Hash Function for Strings
18.4.2 Sets from Hashing
18.4.3 Arrays
18.4.4 Sets from Hashing and Arrays
18.4.5 Collisions
18.4.6 Resolving Collisions
18.4.7 Complexity
18.4.8 Bloom Filters
18.4.9 Generalizing from Sets to Key-Values
18.5 Equality, Ordering, and Hashing
18.5.1 Converting Values to Ordered Values
18.5.2 Hashing in Practice
18.5.3 Equality and Ordering
18.6 Sets as a Case Study
18.6.1 Nature of the Data
18.6.2 Nature of the Operations
18.6.3 Nature of the Guarantee