Skip to index filter Skip to main content
CISC 187 textbook home CISC 187 TextbookCISC 187 Textbook
  • on GitHub
Search the documentation
CISC 187 Textbook
  • on GitHub
  • Change appearance
    • Change appearance
    • Light
    • Dark
    • Automatic
  Index
Index

Legal and foreword

  • Copyright Notice
  • GNU Free Documentation License
  • Foreword
  • Preface
  • C and C++ concepts
    • Hello, world!
    • Types
    • Random numbers
    • Code comments
    • What you don't need to know (yet)
    • Self Check
  • Mathematical Background
    • Sets and Relations
    • Selected functions
    • Modulus operator
    • Permutations
    • Logarithms
    • Summations
    • Estimation
    • Pseudocode conventions and definitions
  • Algorithm Analysis
    • Problems, Algorithms, and Programs
    • Comparing Algorithms
    • Best, worst, and average cases
    • Asymptotic Analysis and Upper Bounds
    • Lower Bounds
    • Theta Notation
  • 1. Development tools
    • 1.1. Git setup
    • 1.2. Tutorial: Using Git
    • 1.3. Building software
    • 1.4. Compiling code on your local computer
    • 1.5. Introducing Gnu/Linux
    • 1.6. Introducing the vim editor
    • 1.7. Command-line compiling
    • 1.8. Debugging
  • 2. String and Vector
    • 2.1. Using string and vector
    • 2.2. String abstractions in C
    • 2.3. Working with C strings
    • 2.4. The string class
    • 2.5. Analysis of String Operators
    • 2.6. The vector class
    • 2.7. Analysis of Vector Operators
  • 3. Introduction to functions
    • 3.1. Introduction to functions
    • 3.2. Passing parameters
    • 3.3. The main function
    • 3.4. Scope
    • 3.5. Namespaces
    • 3.6. Keyword: const
    • 3.7. Keyword: auto
    • 3.8. Error handling
    • 3.9. Exception handling
    • 3.10. Static functions and variables
  • 4. Function overloads and templates
    • 4.1. Function overloads
    • 4.2. Operator overloads
    • 4.3. Function templates
    • 4.4. Concepts overview
    • 4.5. Trailing return types
    • 4.6. General function writing guidelines
  • 5. Pointers
    • 5.1. Pointers
    • 5.2. Using pointers
    • 5.3. Comparison with references
    • 5.4. Pointers and arrays
    • 5.5. Pointers to pointers
    • 5.6. Other pointer characteristics
    • 5.7. Free store pointers
    • 5.8. Pointer debugging
    • 5.9. Pointers to functions
    • 5.10. Lambda expressions
    • 5.11. The std::function template
  • 6. Recursion
    • 6.1. What is Recursion?
    • 6.2. Properties of recursive functions
    • 6.3. Example: Converting an Integer to a String
    • 6.4. The Binary Tree ADT
  • 7. Sorting
    • 7.1. Bubble sort
    • 7.2. Selection sort
    • 7.3. Insertion sort
    • 7.4. Costs of Exchange Sorting
    • 7.5. Shell sort
    • 7.6. Merge sort
    • 7.7. Quick sort
    • 7.8. Heap sort
    • 7.9. Radix sort
    • 7.10. Summary of sorting algorithms
  • 8. Introduction to classes
    • 8.1. Classes
    • 8.2. Constructors
    • 8.3. Pointers to objects
    • 8.4. 'this' pointer
    • 8.5. Interfaces and implementation
    • 8.6. const member functions
    • 8.7. Abstraction
    • 8.8. Enumerated types
  • 9. Class constructors and overloads
    • 9.1. Constructors
    • 9.2. Static members
    • 9.3. Operator overloads
    • 9.4. Friend vs non-friend functions
  • 10. Class design
    • 10.1. Object-oriented concepts
    • 10.2. Unified modeling language
    • 10.3. Composition
    • 10.4. Inheritance
    • 10.5. Abstract base classes
    • 10.6. Design patterns
    • 10.7. Strategy pattern
    • 10.8. Chain of Responsibility pattern
  • 11. Class templates and std::array
    • 11.1. Class templates
    • 11.2. Overloading operator[]
    • 11.3. Container classes
    • 11.4. Standard Template Library Containers
    • 11.5. The std::array class
  • 12. Memory management and std::vector
    • 12.1. The std::vector class
    • 12.2. Copying objects
    • 12.3. Lvalues, rvalues, and references
    • 12.4. Moving memory
    • 12.5. Allocators
    • 12.6. constexpr classes
    • 12.7. Immutable classes
  • 13. Stacks and Queues
    • 13.1. The Adapter pattern
    • 13.2. The stack class
    • 13.3. The queue class
    • 13.4. The deque class
  • 14. Linked lists
    • 14.1. The list class
    • 14.2. Analysis of list operators
    • 14.3. std::forward_list
    • 14.4. Iterable Types
    • 14.5. Iterator pattern
    • 14.6. Basic iterator operations
    • 14.7. Using iterators
  • 15. Trees and associative data structures
    • 15.1. Tree ADT concepts
    • 15.2. Binary Search Trees
    • 15.3. Binary Search Tree iterators
    • 15.4. Heaps and Priority queues
    • 15.5. The set class
    • 15.6. The map class
  • 16. Hash Tables
    • 16.1. Hashing concepts
    • 16.2. Hash functions
    • 16.3. Resolving collisions
    • 16.4. Open hashing
    • 16.5. Analysis of separate chaining
    • 16.6. Open addressing (closed hashing)
    • 16.7. Analysis of hash tables
  • 17. Algorithms
    • 17.1. Background
    • 17.2. Basic Model
    • 17.3. Refactoring to Algorithms
  • Frequently asked questions (FAQ)
    • Why not use an IDE?
    • What language should I learn?
    • Should I learn C first?
    • What other good C++ resources are out there?
    • What if I need help in this class right now?
    • What major should I pick?
    • Do I need to know math?
  • ASCII Character Set
  1. Start
  2. 16. Hash Tables

16. Hash TablesΒΆ

This section focuses on alternatives to tree-like associative data structures -- hash tables.

  • 16.1. Hashing concepts
  • 16.2. Hash functions
    • 16.2.1. Integer hashes
    • 16.2.2. String hashes
    • 16.2.3. Hashing user-defined types
  • 16.3. Resolving collisions
  • 16.4. Open hashing
  • 16.5. Analysis of separate chaining
  • 16.6. Open addressing (closed hashing)
    • 16.6.1. Analysis of open addressing
  • 16.7. Analysis of hash tables
  On this page
  • 16. Hash Tables
  • Previous 15.6. The map class
  • Next 16.1. Hashing concepts
CISC 187 Textbook
  • 2017-2026 Dave Parillo
Built with Sphinx 9.1.0 and Nefertiti 0.9.9