🍁
Data Structures and Algorithms
  • Introduction
  • Introduction to Algorithms Analysis
    • Growth Rates
    • Big-O, Little-o, Theta, Omega
    • Analysis of Linear Search
    • Analysis of Binary Search
  • Recursion
    • The runtime stack
    • How to Write a Recursive Function
      • Example: the Factorial Function
    • Drawbacks of Recursion and Caution
  • Lists
    • Implementation
    • Linked List
      • Nodes
      • Iterator
      • Template Singly Linked List
      • Doubly Linked List
      • Circular Linked List
  • Stacks
    • Stack Operations
    • Stack Implementations
    • Stack Applications
  • Queue
    • Queue Operations
    • Queue Implementations
    • Queue Applications
  • Tables
    • Simple Table
    • Hash Table
      • Bucketing
      • Chaining
      • Linear Probing
      • Quadratic Probing and Double Hashing
  • Sorting
    • Simple Sorts
      • Bubble Sort
      • Insertion Sort
      • Selection Sort
    • Merge Sort
      • Merge Sort Implementation
    • Quick Sort
    • Heap Sort
      • Binary heap
      • Binary heap basics
      • Insertion into a binary heap
      • Delete from a binary heap
      • Implementation
      • Sorting
  • Introduction to Trees, Binary Search Trees
    • Definitions
    • Tree Implementations
    • Binary Trees
    • Binary Search Trees
      • Insertion
      • Removal
      • Traversals
  • AVL Trees
    • Height Balance
    • Insertion
    • Why it works
  • Red Black Trees
    • Insertion Example
  • 2-3 Trees
  • Graphs
    • Representation
  • Complexity Theory
  • Appendix: Mathematics Review
Powered by GitBook
On this page

Was this helpful?

  1. Tables
  2. Hash Table

Bucketing

PreviousHash TableNextChaining

Last updated 5 years ago

Was this helpful?

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\lambda > 1λ>1. However, the higher λ\lambdaλ is the higher a chance of collision. λ>1\lambda > 1λ>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)