HashMap

HashMap

A HashMap is composed of two things:

  • a hash function, and
  • a collection (typically an array) to store values

The hash function transforms the keys (e.g. length, width etc.) into a number which is used as an array index. The values are placed in a buckets array at the hashed index. A perfect hash function is one that assigns a unique array index for each unique key. It's not practical and memory wasteful to have a perfect hash function. This HashMap implements a cost-effective hash function instead.

What happens if two different keys map to the same index? Then we have a collision. In this case, the value at the index will be an array of values instead of a single value. Naturally, this reduces the search complexity from O(1) to O(n).

Collisions can be avoided by having a big bucket size. This HashMap implementation re-sizes itself when it is getting full. This avoids collision and keeps memory usage to a minimum.

This structure uses a buckets array where each bucket is a List.

Constructor

new HashMap(capacityopt, rehashThresholdopt)

Parameters:
Name Type Attributes Default Description
capacity number <optional>
19

initial size of the HashMap data array (preferably a prime number)

rehashThreshold number <optional>
0.75

a rehash is triggered when array reaches this occupancy threshold

Source:

Members

count

Returns the number of items in the hash map

Source:

keys

Returns an array of all keys. May or may not be in insertion order.

Source:

occupancyFactor

Returns a measure of how full the hash map is, i.e. the ratio between items on the map and the total size of the bucket.

Source:

Methods

add(key, value) → {HashMap}

Insert a key/value pair into the map. If the key is already present, replaces its value. Runtime: O(1), in case a rehash is needed O(n).

Returns the map instance to allow command chaining.

Parameters:
Name Type Description
key any
value any
Source:

delete(key)

Removes the specified key from the map. Runtime O(1). Return the value removed or null if the key wasn't found in the map.

Parameters:
Name Type Description
key any
Source:

get(key) → (nullable) {any}

Get the value for the given key. Runtime is usually O(1) but if there are collisions it could be O(n).

Returns null if no such key exists in the map.

Parameters:
Name Type Description
key any
Source:

has(key) → {boolean}

Returns a boolean indicating whether an element with the given key exists or not. Runtime: O(1)

Parameters:
Name Type Description
key any
Source:

(generator) values() → {Iterator}

Get value for each element in the map. Result in no particular order of the corresponding keys.

Source: