Class Hashmap<T>

Hashmap class

Currently supports collision resolution by chaining, hashing by modulo and string keys

Todo

Add load-factor based rehashing

Todo

Add hashing by multiplication option

Type Parameters

T

The type of the values in the hashmap.

Hierarchy

Hashmap

Constructors

constructor

new Hashmap<T>(config: HashmapConfig<T>): Hashmap<T>
Type Parameters
- T
Parameters
- config: HashmapConfig<T>
  
  See HashmapConfig.
Returns Hashmap<T>
- Defined in data_structures/hashmap/Hashmap.ts:443

Properties

`Private` #dynamic_rehashing_enabled

#dynamic_rehashing_enabled: boolean = false

Whether or not to use dynamic rehashing.

`Private` #hash_function

#hash_function: ((key: string) => number)

Type declaration

- (key: string): number
- The hash function used
  
  User can specify their own, else defaults to _default_hash_function
  
  The hash digest returned by this function is combined with the number of buckets to get the corresponding bucket index for the entry
  Parameters
  - key: string
  Returns number

`Private` #hashing_method

#hashing_method: "MODULO" | "MULTIPLICATION"

The hashing method to use.

`Private` #max_load_factor

#max_load_factor: null | number

Maximum load factor for dynamic rehashing.

This value is compared with the new load factor after insert/delete operations to determine whether or not to decrease the # of buckets.

`Private` #min_load_factor

#min_load_factor: null | number

Minimum load factor for dynamic rehashing.

This value is compared with the new load factor after insert/delete operations to determine whether or not to increase the # of buckets.

`Private` #multiplication_factor

#multiplication_factor: null | number = null

Multiplication factor for hashing by multiplication (if used.)

`Private` #stop_rehash_loop

#stop_rehash_loop: boolean = true

When this is true, insert and delete operations will not check for dynamic rehashing. This is done to prevent a rehash causing another rehash.

buckets

buckets: (null | LinkedList<[string, T]>)[] = []

The buckets of the hashmap

This is an array of LinkedLists of entries which represented as a tuples of [string, T]

When an entry is inserted, it will become the head of the corresponding LL

When all entries in an LL bucket are removed, the corresponding entry in the array becomes null; see delete

elements

elements: number = 0

The number of entries present in the hashmap

Used to calculate load factor

keys

keys: string[] = []

The keys used in the hashmap

rehashes

rehashes: number = 0

Number of times the hashmap was dynamically rehashed (i.e. the number of buckets changed.)

Accessors

length

get length(): number
Returns number
- Defined in data_structures/hashmap/Hashmap.ts:286

load_factor

get load_factor(): number
Computed property for the load factor of the hashmap.

Target value for optimal performance is around 0.60 - 0.75

Returns
The load factor

Returns number
- Defined in data_structures/hashmap/Hashmap.ts:282

valid_elements_range

get valid_elements_range(): null | [number, number]
Returns
a tuple [min, max] of two integers, representing the inclusive range of allowed number of elements/entries before dynamic rehashing. If an insertion or deletion operation would cause the number of elements to fall outside of this range, the number of buckets will be adjusted before the insertion/deletion.

Returns
null if dynamic rehashing is not enabled.

Returns null | [number, number]
- Defined in data_structures/hashmap/Hashmap.ts:383

Methods

`Private` _default_hash_function

_default_hash_function(key: Key): number
Private
Default hash function used when user does not specify their own

Based on Java's hashCode

Returns
The hash digest of key
Parameters
- key: Key
Returns number
- Defined in data_structures/hashmap/Hashmap.ts:172

`Private` _dynamic_rehash_if_needed

_dynamic_rehash_if_needed(): boolean
Rehashes the hash table if the load factor falls outside the min/max bounds.

Returns
true if rehashed, false otherwise

Throws
When dynamic hashing is not enabled.

Returns boolean
- Defined in data_structures/hashmap/Hashmap.ts:219

`Private` _get_bucket_index

_get_bucket_index(key: Key): number
Private
Passes hash digest of key through modulo operation to get bucket index.

Returns
The index of the corresponding bucket in this.buckets
Parameters
- key: Key
  
  The key
Returns number
- Defined in data_structures/hashmap/Hashmap.ts:193

`Private` _hash_by_modulo

_hash_by_modulo(digest: number, buckets: number): number
Parameters
- digest: number
- buckets: number
Returns number
- Defined in data_structures/hashmap/Hashmap.ts:204

`Private` _hash_by_multiplication

_hash_by_multiplication(digest: number, buckets: number): number
Parameters
- digest: number
- buckets: number
Returns number
- Defined in data_structures/hashmap/Hashmap.ts:208

access

access(key: Key): T
Accesses the hashmap to get the value with the corresponding key

Throws
NONEXISTANT_KEY

Returns
The corresponding value
Parameters
- key: Key
Returns T
- Defined in data_structures/hashmap/Hashmap.ts:358

delete

delete(key: Key): void
Removes the entry with the specified key. This is an in-place operation.

If the result of this operation would lead to an empty LL the LL will become null

Throws
NONEXISTANT_KEY
Parameters
- key: Key
Returns void
- Defined in data_structures/hashmap/Hashmap.ts:298

insert

insert(value: T, key: Key): void
Inserts the entry into the hashmap

Todo
check for pre-existence
Parameters
- value: T
- key: Key
Returns void
- Defined in data_structures/hashmap/Hashmap.ts:401

rehash

rehash(desired: number, on_buckets?: boolean): void
Resizes the number of buckets of the hashmap and rehashes pre-existing elements to the new buckets.
Parameters
- desired: number
  
  The desired new value for the parameter.
- on_buckets: boolean = false
  
  Whether to rehash based on load factor or number of buckets. If true, desired will be interpreted as the new number of buckets. If false, desired will be interpreted as the new desired load factor. false by default.
  
  When on_buckets is false, the new number of buckets is set to ceil(entries / desired).
Returns void
- Defined in data_structures/hashmap/Hashmap.ts:248

Class Hashmap<T>

Todo

Todo

Type Parameters

T

Hierarchy

Index

Constructors

Properties

Accessors

Methods

Constructors

constructor

Type Parameters

T

Parameters

config: HashmapConfig<T>

Returns Hashmap<T>

Properties

Private #dynamic_rehashing_enabled

Private #hash_function

Type declaration

Parameters

key: string

Returns number

Private #hashing_method

Private #max_load_factor

Private #min_load_factor

Private #multiplication_factor

Private #stop_rehash_loop

buckets

elements

keys

rehashes

Accessors

length

Returns number

load_factor

Returns

Returns number

valid_elements_range

Returns

Returns

Returns null | [number, number]

Methods

Private _default_hash_function

Returns

Parameters

key: Key

Returns number

Private _dynamic_rehash_if_needed

Returns

Throws

Returns boolean

Private _get_bucket_index

Returns

Parameters

key: Key

Returns number

Private _hash_by_modulo

Parameters

digest: number

buckets: number

Returns number

Private _hash_by_multiplication

Parameters

digest: number

buckets: number

Returns number

access

Throws

Returns

Parameters

key: Key

Returns T

delete

Throws

Parameters

key: Key

Returns void

`Private` #dynamic_rehashing_enabled

`Private` #hash_function

`Private` #hashing_method

`Private` #max_load_factor

`Private` #min_load_factor

`Private` #multiplication_factor

`Private` #stop_rehash_loop

`Private` _default_hash_function

`Private` _dynamic_rehash_if_needed

`Private` _get_bucket_index

`Private` _hash_by_modulo

`Private` _hash_by_multiplication