HashMap
Classes
- HashMapEntry
- HashMap ⇐
Map<K,V> Implements part of Map interface NOTE: as with any hash-based data structure, keys are assumed to be immutable. If you modified keys after inserting them into the map, it will cause the hash table to become invalid. You can fix this by forcing rehashing, but generally - try to avoid changing keys in the first place.
Constants
- DEFAULT_INITIAL_CAPACITY_POWER :
number - DEFAULT_INITIAL_CAPACITY :
number - DEFAULT_LOAD_FACTOR :
number - BIN_RESERVED_VALUE_EMPTY :
number Reserved value that we store in "bins" array to indicate an empty slot
- BIN_RESERVED_VALUE_DELETED :
number Reserved value that we store in "bins" array to indicate a deleted entry
- ENTRY_BASE :
number Real index offset into entry array
- RESERVED_HASH :
number Special hash value used to indicate "dead" entries If key hashes to this value - we will replace it
- RESERVED_HASH_SUBSTITUTE :
number Used as a replacement for reserved hash
- UNDEFINED_BIN_INDEX :
number
Functions
- generate_next_linear_congruential_index(index, mask)
Formula: Xn+1 = (a * Xn + c ) % m
According the Hull-Dobell theorem a generator "Xnext = (a*Xprev + c) mod m" is a full cycle generator if and only if o m and c are relatively prime o a-1 is divisible by all prime factors of m o a-1 is divisible by 4 if m is divisible by 4. For our case a is 5, c is 1, and m is a power of two.
HashMapEntry
Kind: global class
- HashMapEntry
- new HashMapEntry(key, value, hash)
- .key :
K - .value :
V - .hash :
number
new HashMapEntry(key, value, hash)
| Param | Type |
|---|---|
| key | K |
| value | V |
| hash | number |
hashMapEntry.key : K
Kind: instance property of HashMapEntry
hashMapEntry.value : V
Kind: instance property of HashMapEntry
hashMapEntry.hash : number
Kind: instance property of HashMapEntry
DEFAULT_INITIAL_CAPACITY_POWER : number
Kind: global constant
Read only: true
DEFAULT_INITIAL_CAPACITY : number
Kind: global constant
Read only: true
DEFAULT_LOAD_FACTOR : number
Kind: global constant
Read only: true
BIN_RESERVED_VALUE_EMPTY : number
Reserved value that we store in "bins" array to indicate an empty slot
Kind: global constant
BIN_RESERVED_VALUE_DELETED : number
Reserved value that we store in "bins" array to indicate a deleted entry
Kind: global constant
ENTRY_BASE : number
Real index offset into entry array
Kind: global constant
RESERVED_HASH : number
Special hash value used to indicate "dead" entries If key hashes to this value - we will replace it
Kind: global constant
RESERVED_HASH_SUBSTITUTE : number
Used as a replacement for reserved hash
Kind: global constant
UNDEFINED_BIN_INDEX : number
Kind: global constant
generate_next_linear_congruential_index(index, mask)
Formula: Xn+1 = (a * Xn + c ) % m
According the Hull-Dobell theorem a generator "Xnext = (a*Xprev + c) mod m" is a full cycle generator if and only if o m and c are relatively prime o a-1 is divisible by all prime factors of m o a-1 is divisible by 4 if m is divisible by 4. For our case a is 5, c is 1, and m is a power of two.
Kind: global function
See: https://en.wikipedia.org/wiki/Linear_congruential_generator
| Param | Description |
|---|---|
| index | |
| mask | used to execute division, this is a number equal to (2^K - 1) where 2^K is the size of the "bins" array |