JavaScript 数据结构与算法 之 字典和散列表

字典和散列表

字典

在字典中，存储的是[键，值]对，其中键名是用来查询特定元素的。字典和集合很相似，集合以[值，值]的形式存储元素，字典则是以[键，值]的形式来存储元素。字典也称作映射、 符号表或关联数组。

function defaultToString(item) {
  if (item === null) {
    return 'NULL';
  } else if (item === undefined) {
    return 'UNDEFINED';
  } else if (typeof item === 'string' || item instanceof String) {
    return `${item}`;
  }
  return item.toString();
}
class ValuePair {
  constructor(key, value) {
    this.key = key;
    this.value = value;
  }
  toString() {
    return `[#${this.key}: ${this.value}]`;
  }
}
class Dictionary {
  constructor(toStrFn = defaultToString) {
    this.toStrFn = toStrFn;
    this.table = {};
  }
  hasKey(key) {
    return this.table[this.toStrFn(key)] != null;
  }
  set(key, value) {
    if (key != null && value != null) {
      const tableKey = this.toStrFn(key);
      this.table[tableKey] = new ValuePair(key, value);
      return true;
    }
    return false;
  }
  get(key) {
    const valuePair = this.table[this.toStrFn(key)];
    return valuePair == null ? undefined : valuePair.value;
  }
  remove(key) {
    if (this.hasKey(key)) {
      delete this.table[this.toStrFn(key)];
      return true;
    }
    return false;
  }
  keyValues() {
    return Object.values(this.table);
  }
  keys() {
    return this.keyValues().map(valuePair => valuePair.key);
  }
  values() {
    return this.keyValues().map(valuePair => valuePair.value);
  }
  forEach(callbackFn) {
    const valuePairs = this.keyValues();
    for (let i = 0; i < valuePairs.length; i++) {
      const result = callbackFn(valuePairs[i].key, valuePairs[i].value);
      if (result === false) {
        break;
      }
    }
  }
  size() {
    return Object.keys(this.table).length;
  }
  isEmpty() {
    return this.size() === 0;
  }
  clear() {
    this.table = {};
  }
  toString() {
    if (this.isEmpty()) {
      return '';
    }
    const valuePairs = this.keyValues();
    let objString = `${valuePairs[0].toString()}`;
    for (let i = 1; i < valuePairs.length; i++) {
      objString = `${objString}, ${valuePairs[i].toString()}`;
    }
    return objString;
  }
}

散列表

HashTable 类，也叫 HashMap 类，它是 Dictionary 类的一种散列表实现方式。散列算法的作用是尽可能快地在数据结构中找到一个值。使用散列函数，能知道值的具体位置，因此能够快速检索到该值。散列函数的作用是给定一个键值，然后返回值在表中的地址。

class HashTable {
  constructor(toStrFn = defaultToString) {
    this.toStrFn = toStrFn;
    this.table = {};
  }
  loseloseHashCode(key) {
    if (typeof key === "number") {
      return key;
    }
    const tableKey = this.toStrFn(key);
    let hash = 0;
    for (let i = 0; i < tableKey.length; i++) {
      hash += tableKey.charAt(i);
    }
    return hash % 37;
  }
  hashCode(key) {
    return this.loseloseHashCode(key);
  }
  put(key, value) {
    if (key != null && value != null) {
      const position = this.hashCode(key);
      this.table[position] = new ValuePair(key, value);
      return true;
    }
    return false;
  }
  get(key) {
    const valuePair = this.table[this.hashCode(key)];
    return valuePair == null ? undefined : valuePair.value;
  }
  remove(key) {
    const hash = this.hashCode(key);
    const valuePair = this.table[hash];
    if (valuePair != null) {
      delete this.table[hash];
      return true;
    }
    return false;
  }
}

• 散列冲突处理方法

  • 分离链接

  分离链接法包括为散列表的每一个位置创建一个链表并将元素存储在里面。是解决冲突的最简单的方法，但是在 HashTable 实例之外还需要额外的存储空间。

  class HashTableSeparateChaining {
    constructor(toStrFn = defaultToString) {
      this.toStrFn = toStrFn;
      this.table = {};
    }
    put(key, value) {
      if (key != null && value != null) {
        const position = this.hashCode(key);
        if (this.table[position] != null) {
          this.table[position] = new LinkedList();
        }
        this.table[position].push(new ValuePair(key, value));
        return true;
      }
      return false;
    }
    get(key) {
      const position = this.hashCode(key);
      const linkedList = this.table[position];
      if (linkedList != null && !linkedList.isEmpty()) {
        let current = linkedList.getHead();
        while (current != null) {
          if (current.element.key === key) {
            return current.element.value;
          }
          current = current.next;
        }
      }
      return undefined;
    }
    remove(key) {
      const position = this.hashCode(key);
      const linkedList = this.table[position];
      if (linkedList != null && !linkedList.isEmpty()) {
        let current = linkedList.getHead();
        while (current != null) {
          if (current.element.key === key) {
            linkedList.remove(current.element);
            if (linkedList.isEmpty()) {
              delete this.table[position];
            }
            return true;
          }
          current = current.next;
        }
      }
      return false;
    }
  }

  • 线性探查

  将元素直接存储到表中，而不是在单独的数据结构中。当想向表中某个位置添加一个新元素的时候，如果索引为 position 的位置已经被占据了，就尝试 position+1 的位置。以此类推，直到在散列表中找到一个空闲的位置。

  put(key, value) {
    if (key != null && value != null) {
      const position = this.hashCode(key);
      if (this.table[position] == null) {
        this.table[position] = new ValuePair(key, value);
      } else {
        let index = position + 1;
        while (this.table[index] != null) {
          index++;
        }
        this.table[index] = new ValuePair(key, value);
      }
      return true;
    }
    return false;
  }
  get(key) {
    const position = this.hashCode(key);
    if (this.table[position] != null) {
      if (this.table[position].key === key) {
        return this.table[position].value;
      }
      let index = position + 1;
      while (this.table[index] != null && this.table[index].key != key) {
        index++;
      }
      if (this.table[index] != null && this.table[index].key === key) {
        // return this.table[position].value; ???
        return this.table[index].value;
      }
    }
    return undefined;
  }
  remove(key) {
    const position = this.hashCode(key);
    if (this.table[position] != null) {
      if (this.table[position].key === key) {
        delete this.table[position];
        this.verifyRemoveSideEffect(key, position);
        return true;
      }
      let index = position + 1;
      while (this.table[index] != null && this.table[index].key !== key ) {
        index++;
      }
      if (this.table[index] != null && this.table[index].key === key) {
        delete this.table[index];
        this.verifyRemoveSideEffect(key, index);
        return true;
      }
    }
    return false;
  }
  verifyRemoveSideEffect(key, removedPosition) {
    const hash = this.hashCode(key);
    let index = removedPosition + 1;
    while (this.table[index] != null) {
      const posHash = this.hashCode(this.table[index].key);
      if (posHash <= hash || posHash <= removedPosition) {
        this.table[removedPosition] = this.table[index];
        delete this.table[index];
        removedPosition = index;
      }
      index++;
    }
  }

  • 双散列法

ES2015 Map 类

const map = new Map();
map.set('Gandalf', 'gandalf@email.com');
map.set('John', 'john@email.com');
map.set('Tyrion', 'tyrion@email.com');

console.log(map.has('Gandalf')); // true
console.log(map.size); // 3
console.log(map.keys()); // {"Gandalf", "John", "Tyrion"}
console.log(map.values()); // { "gandalf@email.com", "john@email.com", "tyrion@email.com"}
console.log(map.get('Gandalf')); // "gandalf@email.com" 
map.delete('Gandalf');

ES2015 WeakMap 和 WeakSet

Map 和 Set 的弱化版本，区别是WeakSet或WeakMap没有entries、keys 和 values 等方法，只能用对象作为键。

创建和使用这两个类主要是为了性能，WeakSet 和 WeakMap 是弱化的（用对象作为键），没有强引用的键，这使得JS的垃圾回收器可以从中清除整个入口。

必须用键才可以取出值。这些类没有 entries、 keys 和 values 等迭代器方法，因此，除非你知道键，否则没有办法取出值。可以使用 WeakMap 类封装 ES2015 类的私有属性。

const map = new WeakMap();
const ob1 = { name: 'Gandalf' }; // {1}
const ob2 = { name: 'John' };
const ob3 = { name: 'Tyrion' };
map.set(ob1, 'gandalf@email.com'); // {2}
map.set(ob2, 'johnsnow@email.com');
map.set(ob3, 'tyrion@email.com');
console.log(map.has(ob1)); // true {3}
console.log(map.get(ob3)); // tyrion@email.com {4}
map.delete(ob2); // {5}