Options
All
  • Public
  • Public/Protected
  • All
Menu

Class HashTable

Hash Table data structure

Hierarchy

  • HashTable

Index

Constructors

Properties

Methods

Constructors

constructor

  • new HashTable(tableSize?: number): HashTable

Properties

buckets

buckets: LinkedList[]
property

Array of buckets or slots

keys

keys: {}
property

A map of key -> index in the bucket for fast lookup

Type declaration

  • [x: string]: number

Methods

delete

  • delete(key: string): any

get

  • get(key: string): any

getKeys

  • getKeys(): string[]

has

  • has(key: string): boolean

hash

  • hash(key: string): number

  • POLYNOMIAL STRING HASHING key(string input) -> hash -> index

    hash(str) = [(str.charCodeAt(0) * P^(n-1)) + (str.charCodeAt(1) * P^(n-2)) + ... ] % M

    P => any prime number, roughly equal to the total no of characters used in the key * e.g. if the key only uses lower-case alphabets => prime number closer to 26 => 31

    M => usually the size of bucket list, because probability of two strings colliding must be inversely proportional to M

    n => length of the key

    Parameters

    • key: string

    Returns number

set