Data Structures and Algorithms
Primary version
Primary version
  • Data Structures and Algorithms
  • Algorithms Analysis
    • Measuring Resource Consumption
    • Growth Rates
    • Asymptotic Notation
    • Analysis of Linear Search
    • Analysis of Binary Search
    • How to do an analysis in 5 steps
  • Recursion
    • Writing a recursive function
    • How do recursive functions work?
    • Analysis of a Recursive Function
    • Drawbacks of Recursion and Caution
  • Lists
    • Implementation
    • Linked List
      • Concepts
      • Implementation - List and Nodes
      • Implementation - push_front(), pop_front()
      • Implementation - Iterators
      • Modification - Sentinel Nodes
  • Stacks and Queues
    • Stack Implementation
    • Queue Implementation
  • Table
    • A Simple Implementation
    • Hash Tables
      • Bucketing
      • Chaining
      • Linear Probing
  • Sorting
    • Simple Sorts
      • Bubble Sort
      • Insertion Sort
      • Selection Sort
    • Merge Sort
    • Quick Sort
    • Heap and Heap Sort
      • Priority Queues using Binary Heaps
      • Heapify and Heap Sort
  • Trees
    • Binary Trees
    • Binary Search Trees
    • BST Implemenation
    • Iterative Methods
    • Recursive Methods
  • AVL Trees
  • Red Black Trees
  • 2-3 Trees
  • Graphs
  • Introduction to Computational Theory
  • Appendix: Markdown
  • Appendix: Mathematics Review
Powered by GitBook
On this page
  1. Table
  2. Hash Tables

Bucketing

Bucketing makes the hash table a 2D array instead of a single dimensional array. Every entry in the array is big enough to hold N items (N is not amount of data. Just a constant).

Problems:

  • Lots of wasted space.

  • If N is exceeded, another strategy will need to be used

  • Not good for memory based implementations but doable if buckets are disk-based)

For bucketing it is alright to have λ>1. However, the higher λ is the higher a chance of collision. λ>1 guarantees there will be at least 1 collision (pigeon hole principle). That will increase both the run time and the possibility of running out of buckets.

For a hash table of N locations and X buckets at each location:

  • Successful Search - O(X) worst case

  • Unsuccessful Search - O(X) worst case

  • Insertion - O(X) - assuming success, bucketing does not have good way to handle non-successful insertions.

  • Deletion - O(X)

  • Storage: O(N * X)

PreviousHash TablesNextChaining

Last updated 6 years ago