Data Structure and Algorithm Design

Sections

• Hashing

• Map and Set ADTs

• Hash Table

Hashing

Outline

• Overview

• Hash functions

• Applications

Overview

Use our Hash Table Collision & Load Factor Lab to compare separate chaining and linear probing, then watch the table resize.

• Broad definition: Hashing is a process of mapping keys of a certain type to data of another type.

• Other definition: Hashing is a process of mapping data of arbitrary size to data of fixed size. (not always true)

• Hash function

  • The core of hashing

• Representation: <start type> -> <destination type>

  • <start type>: The type of data to be hashed, sometimes called key type

  • <destination type>: The type of data after hashing, sometimes called hash value type or hash code type

  • E.g. int -> int, int -> string, string -> int, string -> string

Hashing Glossary

Hash Function

A function that maps a variable sized value to a fixed sized value.

Key (hashing)

The input value to the hash function.

Value (hashing)

A.k.a hash value, hash code or simply hash. The output of the hash function.

Key space / Domain (hashing)

The set of all possible keys.

Value space / Range (hashing)

The set of all possible values.

Collision (hashing)

Multiple distinct keys maps to a same output value.

Hash Function

• The function that performs the mapping

• Required properties

  • deterministic

  • uniform distribution

    • hash function that maps all possible input values (keys) with roughly equal probability to each possible output value (hash code)

    • ensures minimal collision

    • hard to guarantee and prove

• Other properties (application specific)

  • variable length key to fixed length hash value

  • constant time computation \(\Theta(1)\)

  • squeeze a large domain to a smaller range

  • chance of collision

  • asymmetric

Design of Hash Functions

• Integer keys

• String keys

  • Handle variable length

  • All characters are involved

  • Uniform distribution

• Asymmetric hash functions

  • Hard to reverse

  • Cryptographic hash functions

  • E.g. MD5, SHA-1, SHA-2, SHA-3

Applications

• Hash table data structure

  • Hash Map (Map ADT, dictionary, key-value store)

  • Hash Set (Set ADT)

• Fingerprinting

  • Short summary of a large data set

  • Checksum

  • Password management

• Cryptography

• Advanced data structures

  • Bloom filter

  • Cuckoo filter

  • Merkle tree (e.g. BitCoin)

Map and Set ADTs

Try map and set operations in our ADT Explorer.

• Overview

• Behaviors

Overview

• A map ADT is a collection of key-value pairs, where each key is unique and is used to retrieve the corresponding value.

• A set ADT is a collection of unique elements, with no specific order.

• Characteristics

  • Homogeneous

  • Keys in map are unique

  • Elements in set are unique

  • Finite

  • Dynamic size

• Applications

  • Database indexing (map)

  • Caching (map)

  • Key-value storage (map)

  • Membership testing (set)

  • Removing duplicates from a collection (set)

Behaviors

Hash Table in C++

Outline

• Overview

• Hash function for hash table

• Collision resolution

• Applications

Overview

Use our Hash Table Collision & Load Factor Lab to step through collision resolution and rehashing.

A hash table is a data structure that maps keys to values for highly efficient lookup. The key-value pairs are stored in “buckets” and the hash table maps keys to buckets using a hash function.

• Requirements

  • Keys are unique (no duplicate keys)

  • Keys are immutable

• Properties

  • Fast lookup, insert, and delete \(\Theta(1)\)

  • Unordered

  • Redundant storage to reduce collision and ensure performance

Hash Function For Hash Table

• \(h(key)\) a special type of hash function used by hash table

• Maps a key of an arbitrary type to an integer in a certain range \(0, 1, 2, \ldots, size - 1\), where \(size\) is the size of the hash table

• The value obtained by applying the hash function to a key is called the hash value of the key. It is used as an index of the bucket.

• Modulo arithmetic

• Considerations

  • Deterministic

  • Fast to compute

  • Uniform distribution

• Collision

  • More than one keys map to the same index

Hash Table Applications

• Hash Map (key-value pairs, implementation of map ADT)

• Hash Set (unique elements, implementation of set ADT)

• Caching (map)

• Database indexing (map)

• Symbol table in compilers (map)

• Counting unique elements (set)

• Membership testing (set)

• Deduping a collection (set)

Chaining (Collision Resolution)

• Each bucket can store a variable number of key-value pairs

  • \(\Theta(nk)\) space complexity

    • where \(n\) is the number of buckets

    • \(k\) is the average number of key-value pairs in each bucket

    • Theatrically unlimited space for each bucket

    • \(k\) should be ideally a small constant

  • \(\Theta(k)\) time complexity for lookup, insert, and delete

• Solve collision by chaining the key-value pairs together in one bucket when collision happens

Implementation of Chaining Hash Table

• Array of Buckets (the hash table)

  • Fixed length

  • Local array

  • Dynamic array

  • Vector

• Bucket

  • Variable length

  • Stores key-value pairs

  • Mostly empty

  • Linked list

  • Vector

Chaining Hash Table in C++

• vector<vector<pair<keyType, valueType>>> hashTable

  Vector of vectors of pair objects.

• vector<LinkedListNode<keyType, valueType> *> hashTable

  Vector of pointers to linked list.

• LinkedListNode<keyType, valueType> ** hashTable

  One dimensional dynamic array of pointers to a linked list.

  template <typename keyType, typename valueType>
  struct LikedListNode {
    keyType key;
    valueType value;
    LinkedListNode * next;
    LinkedListNode * prev;
  };

Open Addressing (Collision Resolution)

• Each bucket stores at most one key-value pair

  • \(\Theta(n)\) space complexity

    • Can store at most \(n\) key-value pairs

  • \(\Theta(k)\) time complexity for lookup, insert, and delete

    • \(k\) is the average number of probing steps

    • \(k\) should be ideally a small constant

• Solve collision by finding another available bucket using a “probing sequence”

Implementation of Open Addressing Hash Table

• Array of Buckets (the hash table)

  • Fixed length

  • Local array

  • Dynamic array

  • Vector

• Bucket

  • Stores a key-value pair

  • Stores empty status and deletion status to indicate whether probing should continue.

    • Empty since start

    • Empty after deletion

• Performance degradation caused by frequent delete

  • More “tombstone” buckets accumulate

  • Need rehashing to reset the hash table

Open Addressing Hash Table in C++

• Bucket<keyType, valueType> * hashTable

  One dimensional dynamic array of bucket objects.

• vector<Bucket<keyType, valueType>> hashTable

  Vector of bucket objects.

  template <typename keyType, typename valueType>
  struct Bucket {
    keyType key;
    valueType value;
    bool isEmpty = true;
    bool isDeleted = false;
  };

Probing in Open Addressing

• Find another available bucket to store the value when a collision occurs

• Probing sequence: the sequence of the buckets to check when collision happens

• You will never probe buckets more than \(size\) times

• Linear probing:

  \((h1(key) + C_{1} * i) \% size, i = 0, 1, 2, 3 \dots size - 1\)

• quadratic probing:

  \((h1(key) + C_{1} * i^2) \% size, i = 0, 1, 2, 3 \dots size - 1\)

• double hashing probing:

  \((h1(key) + C_{1} * i * h2(key)) \% size, i = 0, 1, 2, 3 \dots size - 1\)