Skip to content

sanyathisside/Hashing

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

21 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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)].

  • 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






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. *

Releases

No releases published

Packages

No packages published

Languages