JavaScript数据结构（六）散列表

1. 定义

HashTable、HashMap，是Dictionary类的一种散列表实现方式

散列算法：尽可能快地在数据结构中找到一个值

散列函数：给定一个键值，然后返回值在表中的地址

应用：

关系型数据库：创建新的表时，同时创建一个索引来更快地查询到记录的key

2. 具体操作

创建

class HaspTable {
    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++) {
        has += tableKey.charCodeAt(i);  //转换为ASII码值
    }
    return hash % 37;  //规避操作数超过数值变量最大表示范围的风险
}

hashCode(key) {
    return this.loseloeseHashCode(key);
}
复制代码

方法

• put(key,value)：向散列表增加一个新的项（也能更新散列表）

  put(key, value) {
      if(key != null && value ! null) {
          const position = this.hashCode(key);
          this.table[position] = new ValuePair(key, value);
          return true;
      }
      return false;
  }
  复制代码

• remove(key)：根据键值从散列表中移除值

  remove(key) {
      const hash = this.hashCode(key);
      const valuePair = this.table[hash];
      if(valuePair != null) {
          delete this.table[hash];
          return true;
      }
      return false;
  }
  复制代码

• get(key)：返回根据键值检索到的特定的值。

  get(key) {
      const valuePair = this.table[this.hashCode(key)];
      return valuePair == null ? undefined : valuePair.value;
  }
  复制代码

3. 使用

const hash = new HashTable();

hash.put('Gandalf', 'gandalf@email.com');
hash.put('John', 'johnsnow@email.com');
hash.put('Tyrion', 'tyrion@email.com');

console.log(hash.hashCode('Gandalf') + ' - Gandalf'); // 19 - Gandalf
console.log(hash.hashCode('John') + ' - John');  // 29 - John
console.log(hash.hashCode('Tyrion') + ' - Tyrion');  // 16 - Tyrion
console.log(hash.get('Gandalf')); // gandalf@email.com
console.log(hash.get('Loiane')); // undefined

hash.remove('Gandalf');
console.log(hash.get('Gandalf'));
复制代码

散列表和散列集合

类似

散列集合由一个集合构成，插入、移除或获取元素时，使用的是hashCode函数

不同之处： 不需要添加键值对，只插入值而没有键

4. 处理散列表的冲突

当键有相同的散列值时，不同的值在散列表中对应着相同的位置，后面添加的值会覆盖前面的，称为冲突。

处理冲突的几种方法： 分离链接、线性探查和双散列法

1. 分离链接

解决冲突的最简单的方法

分离链接法包括为散列表的每一个位置创建一个链表并将元素存储在里面

创建

class HashTableSeparateChaining {
    constructor(toStrFn = defaultString) {
        this.toStrFn = toStrFn;2
        this.table = {};
    }
}
复制代码

方法

• put(key,value)：向散列表增加一个新的项（也能更新散列表）

  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;
  }
  复制代码

• remove(key)：根据键值从散列表中移除值

  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;
  }
  复制代码

• get(key)：返回根据键值检索到的特定的值

  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;
  }
  复制代码

2. 线性探查

将元素直接存储到表中

当想向表中添加一个新元素的时候，如果索引为position的位置被占据，以此寻找position+1、position+2……直到有空的位置

删除键值对：

1. 软删除： 使用特殊的值（标记）来表示键值对被删除，并不是真的删除

   会降低散列表的效率，因为搜索键值会随时间变慢

   

2. 检验是否有必要将一个或多个元素移动到之前的位置。当搜索一个键的时候，这种方法可以避免找到一个空位置

   需要移动元素，挪动键值对

   

方法

• put(key,value)：向散列表增加一个新的项（也能更新散列表）

  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[position] != null) {  //如果位置被占了，就找下一位
                  index++;
              }
              this.table[index] = new ValuePair(key, value);
          }
          return true;
      }
      return false;
  }
  复制代码

• remove(key)：根据键值从散列表中移除值

  remove(key) {
      const position = this.hashCode(key);
      if (this.table[position] != null) {
          if (this.table[position].key === key) {
              delete this.table[position];
              this.varifyRemoveSideEffect(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++; 
      }
  }
  复制代码

• get(key)：返回根据键值检索到的特定的值

  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 undefined;
  }
  复制代码

5. ES2015Map类

const map = new Map();
map.set('Gandalf', 'gandalf@email.com');
map.set('John', 'johnsnow@email.com');
map.set('Tyrion', 'tyrion@email.com');
console.log(map.has('Gandalf')); // true console.log(map.size);
console.log(map.keys()); // 输出{"Gandalf", "John", "Tyrion"} 
console.log(map.values()); // 输出{"gandalf@email.com", "johnsnow@email.com", "tyrion@email.com"}
console.log(map.get('Tyrion')); // tyrion@email.com
map.delete('John');
复制代码

6. ES2105 WeakMap类和WeakSet类

除了Set和Map这两种新的数据结构，ES2015还增加了它们的弱化版本，WeakSet和WeakMap

区别：

• WeakSet或WeakMap类没有entries、keys和values等方法
• 只能用对象作为键

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

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

 const map = new WeakMap();
const ob1 = { name: 'Gandalf' }; 
const ob2 = { name: 'John' };
const ob3 = { name: 'Tyrion' };
map.set(ob1, 'gandalf@email.com');
map.set(ob2, 'johnsnow@email.com');
map.set(ob3, 'tyrion@email.com');
console.log(map.has(ob1)); 
console.log(map.get(ob3)); // tyrion@email.com {4} map.delete(ob2);
复制代码