哈希表

HashTable

• hash-table/HashTable.js

import LinkedList from '../linked-list/LinkedList.js';

// The bigger the hash table size the less collisions you'll get.
const defaultHashTableSize = 32;

export default class HashTable {
  constructor(hashTableSize = defaultHashTableSize) {
    // fill each bucket with empty linked list.
    this.buckets = Array(hashTableSize).fill(null).map(() => new LinkedList());
    this.keys = {};
  }

  /**
   * Converts key string to hash number.
   * 
   * @param {string} key 
   * @returns  {number}
   */
  hash(key) {
    /* A simple hash function */ 
    const hash = Array.from(key).reduce((accumulator, ch) => (accumulator + ch.charCodeAt(0)), 0);
    return hash % this.buckets.length;
  }

  /**
   * @param {string} key 
   * @param {*} value 
   */
  set(key, value) {
    const hashKey = this.hash(key);
    this.keys[key] = hashKey;

    const bucketLinkedList = this.buckets[hashKey];
    const node = bucketLinkedList.find({ callback: nodeVal => nodeVal.key === key });

    if (!node) {
      // Insert new node.
      bucketLinkedList.append({ key, value});
    } else {
      // Update value of existing node.
      node.value.value = value;
    }
  }

  /**
   * @param {string} key 
   * @returns {*}
   */
  delete(key) {
    const hashKey = this.hash(key);
    delete this.keys[key];

    const bucketLinkedList = this.buckets[hashKey];
    const node = bucketLinkedList.find({ callback: nodeVal => nodeVal.key === key });

    if (node) {
      // node.value 是引用类型
      return bucketLinkedList.delete(node.value);
    }

    return null;
  }

  get(key) {
    const bucketLinkedList = this.buckets[this.hash(key)];
    const node = bucketLinkedList.find({ callback: nodeVal => nodeVal.key === key });

    return node ? node.value.value  : undefined;
  }

  has(key) {
    return Object.hasOwnProperty.call(this.keys, key);
  }

  getKeys() {
    return Object.keys(this.keys);
  }

  /**
   * Gets the list of all the stored values in the hash table.
   *
   * @return {*[]}
   */
  getValues() {
    return this.buckets.reduce((values, bucket) => {
      const bucketValues = bucket.toArray()
        .map((linkedListNode) => linkedListNode.value.value);
      return values.concat(bucketValues);
    }, [])
  }
}