8.14

17 Several Variations on Sets🔗

    17.1 Representing Sets as Lists

      17.1.1 Representation Choices

      17.1.2 Time Complexity

      17.1.3 Choosing Between Representations

      17.1.4 Other Operations

    17.2 Making Sets Grow on Trees

      17.2.1 Using Binary Trees

      17.2.2 Checking the Complexity

      17.2.3 A Fine Balance: Tree Surgery

        17.2.3.1 Left-Left Case

        17.2.3.2 Left-Right Case

        17.2.3.3 Any Other Cases?

    17.3 Union-Find

      17.3.1 Implementing with State

      17.3.2 Optimizations

      17.3.3 Analysis

    17.4 Hashes, Sets, and Key-Values

      17.4.1 A Hash Function for Strings

      17.4.2 Sets from Hashing

      17.4.3 Arrays

      17.4.4 Sets from Hashing and Arrays

      17.4.5 Collisions

      17.4.6 Resolving Collisions

      17.4.7 Complexity

      17.4.8 Bloom Filters

      17.4.9 Generalizing from Sets to Key-Values

    17.5 Equality, Ordering, and Hashing

      17.5.1 Converting Values to Ordered Values

      17.5.2 Hashing in Practice

      17.5.3 Equality and Ordering

    17.6 Sets as a Case Study

      17.6.1 Nature of the Data

      17.6.2 Nature of the Operations

      17.6.3 Nature of the Guarantee