关于javascript:javascript-数据结构系列-六-哈希表

明天持续数据结构系列 哈希表 hash-table,看一代码实现
构造函数如下

  /**   * @param {number} hashTableSize   */  constructor(hashTableSize = defaultHashTableSize) {    // Create hash table of certain size and fill each bucket with empty linked list.    this.buckets = Array(hashTableSize).fill(null).map(() => new LinkedList());    // Just to keep track of all actual keys in a fast way.    this.keys = {};  }

hash 办法

  /**   * Converts key string to hash number.   *   * @param {string} key   * @return {number}   */  hash(key) {    // For simplicity reasons we will just use character codes sum of all characters of the key    // to calculate the hash.    //    // But you may also use more sophisticated approaches like polynomial string hash to reduce the    // number of collisions:    //    // hash = charCodeAt(0) * PRIME^(n-1) + charCodeAt(1) * PRIME^(n-2) + ... + charCodeAt(n-1)    //    // where charCodeAt(i) is the i-th character code of the key, n is the length of the key and    // PRIME is just any prime number like 31.    const hash = Array.from(key).reduce(      (hashAccumulator, keySymbol) => (hashAccumulator + keySymbol.charCodeAt(0)),      0,    );    // Reduce hash number so it would fit hash table size.    return hash % this.buckets.length;  }

set 办法

  /**   * @param {string} key   * @param {*} value   */  set(key, value) {    const keyHash = this.hash(key);    this.keys[key] = keyHash;    const bucketLinkedList = this.buckets[keyHash];    const node = bucketLinkedList.find({ callback: (nodeValue) => nodeValue.key === key });    if (!node) {      // Insert new node.      bucketLinkedList.append({ key, value });    } else {      // Update value of existing node.      node.value.value = value;    }  }

delete 办法

  /**   * @param {string} key   * @return {*}   */  delete(key) {    const keyHash = this.hash(key);    delete this.keys[key];    const bucketLinkedList = this.buckets[keyHash];    const node = bucketLinkedList.find({ callback: (nodeValue) => nodeValue.key === key });    if (node) {      return bucketLinkedList.delete(node.value);    }    return null;  }

get 办法

  /**   * @param {string} key   * @return {*}   */  get(key) {    const bucketLinkedList = this.buckets[this.hash(key)];    const node = bucketLinkedList.find({ callback: (nodeValue) => nodeValue.key === key });    return node ? node.value.value : undefined;  }

has 办法

  /**   * @param {string} key   * @return {boolean}   */  has(key) {    return Object.hasOwnProperty.call(this.keys, key);  }

getKeys 办法

  /**   * @return {string[]}   */  getKeys() {    return Object.keys(this.keys);  }

至此，曾经实现了一个简略hash-table!!!