Hashing/Hashtable

• Purpose: To support insertion, deletion and search in average-case constant time.
• Assumption: Order of elements is irrelevant.
• Hash function: Hash["string key"] ==> Integer value.
• Key Components:
  • Hash Function.
  • Hash Table.
  • Collision Handling Scheme.

---

Hash Table

• Hash table is an array of fixed size(table size).
• The elements of the array are indexed by a key, which is mapped to an array index( 0 to tablesize-1).

---

Operations:

• Insertion: T[h(key)]= value;
• Deletion: T[h(key)] = NULL;
• Search: return T[h(key)];

---

Collision

• Collision can't be avoided but it's chance can be reduced using a good hash function.
• A good hash function should has the properties:
  • Reduced chance of collision- Distribute keys uniformly over table.
  • Should be fast to compute.

Collison Handling Schemes:

• Open Chaining- Separate Chaining
• Closed Hashing- Open Addressing
  • Linear Probing
  • Quadratic Probing
• Double Hashing

Separate chaining:

• Implemented using Linked list.
• Key k is stored in list at T[h(k)].

---

Implementation of Hashmap

• Class implementation.
• Insertion.
• Print.
• Rehashing.
• Searching.

---

Rehashing and Load Factor

• Rehashing: Increase the table size as number of elements increases.
  • Load Factor > Threshold.
  • Create a table of 2x size.
  • Shift elemets.
  • Delete old table.
• Load factor= Current size/Table size

---

Maps STL

Multimap STL

Maps STL Example: Vertical Order Print

Unordered Map STL

Unordered Map Example: Phonebook

---

Check if there is subarray with sum zero

---

Length of longest subarray with sum zero

---

Longest subarray with sum K

---

Longest consecutive subsequence

---

Minimum Window Substring

Given a string and a pattern, find minimum window in the string such that it contains all the elements of the pattern.

---

Right angled triangles count

Given Cartesian co-ordinate, find how many right angled triangles are there such that the perpendicular and base is parallet to x or y axis. *