哈希表

定义

在计算机科学中，一个**哈希表(hash table或hash map)**是一种实现关联数据(associative array)的抽象数据类型，该结构可以将键映射到值。

哈希表使用哈希函数/散列函数来计算一个值在数组或桶(buckets)中或槽(slots)中对应的索引，可使用该索引找到所需的值。

理想情况下，散列函数将为每个键分配一个唯一的桶(bucket)，但是大多数哈希表设计采用不完美的散列函数，这可能会导致"哈希冲突(hash collision)"，也就是散列函数为多个键(key)生成了相同的索引，这种碰撞必须以某种方式进行处理。

代码实现

HashTable

import LinkedList from 'LinkedList';

const defaultHashTableSize = 32;

export default class HashTable {
  constructor(hashTableSize = defaultHashTableSize) {
    this.buckets = Array(hashTableSize).fill(null).map(() => new LinkedList());
    
    this.keys = {};
  }
  
  hash(key) {
    const hash = Array.from(key).reduce(
    	(hashAccumulator, keySymbol) => (hashAccumulator + keySymbol.charCodeAt(0)),
    );
    
    return hash % this.buckets.length;
  }
  
  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) {
      bucketLinkedList.append({ key, value });
    } else {
      node.value.value = value;
    }
  }
  
  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(key) {
    const bucketLinkedList = this.buckets[this.hash(key)];
    const node = bucketLinkedList.find({ callback: (nodeValue) => nodeValue.key === key });
    
    return node ? node.value.value : undefined;
  }
  
  has(key) {
    return Object.hasOwnProperty.call(this.keys, key);
  }
  
  getKeys() {
    return Object.keys(this.keys);
  }
  
  getValues() {
    return this.buckets.reduce((values, bucket) => {
      const bucketValues = bucket.toArray()
      	.map((linkedListNode) => linkedListNode.value.value);
      return values.concat(bucketValues);
    }, []);
  }
}