Hash Table

• Quick summary: unordered collection that maps keys to values using hashing.
• Also known as: hash, hash map, map, unordered map, dictionary, associative array.
• Important facts:
  • Stores data as key-value pairs.
  • Can be seen as an evolution of arrays that removes the limitation of sequential numerical indices and allows using flexible keys instead.
  • For any given non-numeric key, hashing helps get a numeric index to look up in the underlying array.
  • If hashing two or more keys returns the same value, this is called a hash collision. To mitigate this, instead of storing actual values, the underlying array may hold references to linked lists that, in turn, contain all values with the same hash.
  • A set is a variation of a hash table that stores keys but not values.
• Pros:
  • Keys can be of many data types. The only requirement is that these data types are hashable.
  • Average search, insertion and deletion are O(1).
• Cons:
  • Worst-case lookups are O(n).
  • No ordering means looking up minimum and maximum values is expensive.
  • Looking up the value for a given key can be done in constant time, but looking up the keys for a given value is O(n).
• Notable uses:
  • Caching.
  • Database partitioning.
• Time complexity (worst case):
  • Access: O(n)
  • Search: O(n)
  • Insertion: O(n)
  • Deletion: O(n)
• See also:
  • Interview Problems: Hash Maps

xxxxxxxxxx

console.log(dict.get("james"));

class Hashmap {

  constructor() {

    this._storage = [];

  }

​

  hashStr(str) {

    let finalHash = 0;

    for (let i = 0; i < str.length; i++) {

      const charCode = str.charCodeAt(i);

      finalHash += charCode;

    }

    return finalHash;

  }

​

  set(key, val) {

    let idx = this.hashStr(key);

​

    if (!this._storage[idx]) {

      this._storage[idx] = [];

    }

​

    this._storage[idx].push([key, val]);

  }

​

  get(key) {

    let idx = this.hashStr(key);

​

    if (!this._storage[idx]) {

      return undefined;