Mappings and Hash Tables

Chapter 15: Mapping and Hash Tables

• Objectives include understanding mapping vocabulary, listing basic operations of mapping ADTs, explaining hashing, listing hash function requirements, explaining key immutability, and implementing mapping ADTs.

Search Algorithms

• Linear search has a time complexity of O(n).
• Binary search has a time complexity of O(log n).
• Hashing can achieve search operations in O(1) time.

Dictionaries

• Python dictionaries store elements with keys of any hashable types and values of any types.
• Dictionaries store unordered collections of unique values within key-value pairs.
• Keys in dictionaries must be unique.
• Dictionaries are mutable, enabling adding, modifying, and removing key-value pairs after creation.

Mapping

• A mapping is an association between two sets of things, specifically associating a value to a key.
• These associated pairs are referred to as key-value pairs.
• Keys within a mapping must be unique.

Concept of Hashing

• Information to be retrieved is stored in a hash table, which is visualized as an array of "m" locations termed buckets.
• A hash function is a mapping between a key and a bucket.
• The time required to store and retrieve data is proportional to hash function computation time.

Mapping ADT (Abstract Data Type)

• Required operations:
  • put(key, value): Adds a key-value pair.
  • get(key): Returns the value, raising a KeyError if the key is absent.
• Optional operations:
  • del(key): Removes a key-value pair.
  • len(): Returns the number of keys.
  • keys(): Returns a set of keys.
  • values(): Returns a set of values.
  • items(): Returns a set of key-value pairs.

Direct Addressing

• Idea: If we know exactly where a key should be, keys can be directly used as indices.
• This approach assigns a unique index to each key.
• Problem: Potentially too much wasted space

Hash Functions and Tables

• Instead of directly using the key as an index, hash functions map the entire key space into a smaller set of keys to use just the right sized array.
• A hash function (f) converts a key to an index; for example, h(x) = x % Table_size.
• Modify hash function.

Hash Collision

• This occurs when two different keys have the same hash value.
• Mathematically, h(k1) = h(k2) when k1 ≠ k2.

Collision Handling Schemes

• Collision occurs when different elements are mapped to the same cell.
• Collision resolution methods incluse separate chaining and open addressing.
• Open addressing involves linear probing, quadratic probing, and double hashing.

Separate Chaining (Open Hashing)

• Keys are stored in the same slot using a list, a linked list or by some other data structure .

Open Addressing (Closed Hashing)

• Open addressing is a collision resolution strategy where collisions are resolved by storing the colliding key in a different location when the natural choice is full.
• The methods are:
  • Linear Probing: Search the table for the closest following free location and insert the new key there.
  • Quadratic Probing: When collision occurs, probe for i²'th bucket in ith iteration.
  • Double Hashing: Use a secondary hash function algorithm to find the next free available slot where it is very unlikely that for some key, h(key) equals g(key).

Rehashing

• Dictionaries support O(1) for put and get, regardless of n
• Achieved when:
  • bucket = hash(key) % m, where keys are split into m buckets used with ~m items.
• If n gets too big/small, Rehash is used:
  • Create a list with p buckets
  • Rehash every key: bucket = hash(key) % p
  • Cost: O(n), Average cost: O(1); Lazy Update!
• Rehashing is prompted by load factor.

Load Factor

• Load Factor (α) is the Ratio of the number of entries in the table to table size.
• If n is the total number of (key, value) pairs stored in the table and c is the capacity of the table (i.e., array), where α = n/c
• This decides when to increase the HashMap capacity to maintain the get() and put() operation complexity of 0(1).

Python's hash() Function

• Uses only one parameter: the object whose hash value is to be returned.
• Only immutable objects can be hashed.
• Hashable objects: bool, int, long, float, string, tuple, etc.
• Non-hashable objects incluse lists, sets, and dictionaries.

Implementing the Mapping ADT

• Involves using ListMapping and HashMapping classes.