Options
All
  • Public
  • Public/Protected
  • All
Menu

Module 5. Hash Table

A hash-table is basically a key-value lookup data structure, a hash map. A combination of features from Array and LinkedList data structures. Array like constant complexity and LinkedList like flexibility It uses a hash function to compute an index into an array of buckets to put or get the data from.

lookup - key(input) -> hashCode -> index

Problem Statement (Collision)
  • The size of the array is fixed, where as number of potential hashCodes is virtually infinite
  • Multiple keys can produce single hashCode
  • And multiple hashCodes can map to a single index of the array of buckets

Collision Handling
  • The buckets will not store a single data entity, but rather it'll be a linkedList
  • The LinkedList will have all the data items whose keys mapped to the same index of the bucket
  • The data entities will consist of key as well as value as properties

  • when multiple keys map to the same index, we go that index and search for the key in the linked list

Hash Table

Hash collision resolved by chaining.

Hash Collision

Files: HashTable | Test

YouTube

Classes