第八章 散列表

自我测试

本篇文章的测试用例及调试方法见前言

说明

散列算法的作用是尽可能快地在数据结构中找到一个值。在之前的章节中，你已经知道如果要在数据结构中获得一个值（使用get方法），需要遍历整个数据结构来找到它。如果使用散列函数，就知道值的具体位置，因此能够快速检索到该值。散列函数的作用是给定一个键值，然后返回值在表中的地址。
举个例子，我们继续使用在前一节中使用的电子邮件地址簿。我们将要使用最常见的散列函数——“lose lose”散列函数，方法是简单地将每个键值中的每个字母的ASCII值相加。

简单图解

一个字典基本方法

• hashCode : 获取一个hashCode
• put(key,value) : 向字典中添加新元素。
• remove(key) : 如果某个键值存在于这个字典中，则返回true，反之则返回false。
• get(key) :通过键值查找特定的数值并返回。
• clear() : 移除字典中的所有元素
• size() : 返回字典的元素个数
• isEmpty: 字典是空的
• getTable: 返回字典中的数据

散列冲突

当使用散列算法的时候难免会出现计算出来的hashCode相同的时候,这个就叫散列冲突

解决散列冲突

• 分离链接

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

• 线性探查

另一种解决冲突的方法是线性探查。当想向表中某个位置加入一个新元素的时候，如果索引为index的位置已经被占据了，就尝试index+1的位置。如果index+1的位置也被占据了，就尝试index+2的位置，以此类推。

公共部分

function defaultToString(item: any): string {
  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<K, V> {
  key: K;
  value: V;

  constructor(key: K, value: V) {
    this.key = key;
    this.value = value;
  }

  toString() {
    return `[#${this.key}: ${this.value}]`;
  }
}

分离链接

import LinkedList from "./linked-list";
export default class HashMapByLinkList<K, V> {
  table: any;
  count: number;
  toStrFn: any;

  constructor(defaultToStr: any = defaultToString) {
    this.count = 0;
    this.table = {};
    this.toStrFn = defaultToStr;
  }

  private loseloseHashCode(key: K) {
    if (typeof key === 'number') {
      return key;
    }
    const tableKey = this.toStrFn(key);
    let hash = 0;
    for (let i = 0; i < tableKey.length; i++) {
      hash += tableKey.charCodeAt(i);
    }
    return hash % 37;
  }

  /**
   * 生成hashCode
   */
  hashCode(key: K) {
    return this.loseloseHashCode(key)
  }

  //插入一个元素
  put(key: K, value: V) {
    //如果没有key,或者没有值,就没办法插入
    if (key == null || value == null) {
      return false
    }
    //获取hash位置
    let position = this.hashCode(key);
    //如果这个位置没有链表,添加一个链表
    if (!this.table[position]) {
      this.table[position] = new LinkedList();
    }
    //将值添加到链表中
    this.table[position].push(new ValuePair(key, value));
    //维护数字
    this.count++;
    //返回插入成功
    return true;
  }

  get(key: K) {
    //获取位置信息
    let hashCode = this.hashCode(key);
    //获取该位置的链表
    let linkList = this.table[hashCode];
    //如果这个位置有链表,并且链表有值
    if (linkList && !linkList.isEmpty()) {
      //获取head指针
      let current = linkList.getHead();
      while (current) {
        //判断这个节点上元素的key是否和传入的key相同
        if (current.element.key === key) {
          return current.element.value;
        }
        //如果不相等,就遍历下一个节点
        current = current.next;
      }
    }
    //如果没有找到,就返回undefined
    return undefined;
  }

  remove(key: K) {
    //获取这个key的hashCode
    let position = this.hashCode(key);
    //获取该位置下的链表
    let linkList = this.table[position];
    if (linkList && !linkList.isEmpty()) {
      //需找key值在哪个位置
      let current = linkList.getHead();
      while (current) {
        if (current.element.key === key) {
          //删除元素
          linkList.remove(current.element);
          //如果链表空了,就删除该元素
          if (linkList.isEmpty()) {
            delete this.table[position];
          }
          //删除数量减一
          this.count--;
          return true;
        }
        current = current.next;
      }
    }
    return false;
  }

  isEmpty() {
    return this.count === 0
  }

  size() {
    return this.count;
  }

  clear() {
    this.table = {};
    this.count = 0;
  }

  getTable() {
    return this.table;
  }

  toString() {
    if (this.isEmpty()) {
      return '';
    }
    const keys = Object.keys(this.table);
    let objString = `{${keys[0]} => ${this.table[keys[0]].toString()}}`;
    for (let i = 1; i < keys.length; i++) {
      objString = `${objString},{${keys[i]} => ${this.table[
        keys[i]
        ].toString()}}`;
    }
    return objString;
  }
}

线性探查

export default class HashMap<K, V> {
  table: any;
  toStrFn: any;
  count: number;

  constructor(toStrFn = defaultToString) {
    this.toStrFn = toStrFn;
    this.table = {};
    this.count = 0;
  }

  private loseloseHashCode(key: K) {
    if (typeof key === 'number') {
      return key;
    }
    const tableKey = this.toStrFn(key);
    let hash = 0;
    for (let i = 0; i < tableKey.length; i++) {
      hash += tableKey.charCodeAt(i);
    }
    return hash % 37;
  }

  hashCode(key: K) {
    return this.loseloseHashCode(key);
  }

  /**
   * 注意key,value必传,还要注意使用key做判断条件判断可能会有问题,0
   * @param key
   * @param value
   */
  put(key: K, value: V) {
    if (key != null && value != null) {
      // 获取key经过计算后在什么位置
      let position = this.hashCode(key);
      let data = new ValuePair(key, value);
      // 如果position位置无值
      if (this.table[position] == null) {
        this.table[position] = data;
      }
      // 如果key的位置有值
      else {
        //当前位置有值,所以先自增一个
        position++;
        //如果这个位置有值就继续,无值就停止
        while (this.table[position] != null) {
          position++;
        }
        //循环结束将找到一个新的位置,这个时候将值赋值上去,完成插入
        this.table[position] = data;
      }
      this.count++;
      return true;
    }
    return false;
  }

  remove(key: K): boolean {
    // 获取key经过计算后在什么位置
    let position = this.hashCode(key);
    //如果这个位置没有值,则返回false
    if (this.table[position] == null) {
      return false;
    }
    //如果这个位置的值的key等于传入的key,那么就删除,并返回true
    if (this.table[position].key === key) {
      delete this.table[position];
      //重排数据
      this.rearrangeData(key, position);
      this.count--;
      return true;
    }
    //这个位置有值,但是key不是我要找的,所以需要继续向下查找
    else {
      //因为position位置已经不对,所以这里+1
      position++;
      //记录一下这个位置,到时需要重排数据
      //当这个位置有值,但是值的key不等于传入的key就继续循环
      while (this.table[position] != null && this.table[position].key !== key) {
        position++;
      }
      //判断出来的位置是不是有值,有值就删除
      if (this.table[position] != null) {
        delete this.table[position];
        //重排数据
        this.rearrangeData(key, position);
        this.count--;
        return true;
      }
      //没有找到,就返回false
      return false;
    }
  }

  get(key: K) {
    let position = this.hashCode(key);
    if (this.table[position] == null) {
      return undefined;
    }
    if (this.table[position].key === key) {
      return this.table[position].value;
    } else {
      position++;
      while (this.table[position] != null && this.table[position].key !== key) {
        position++;
      }
      if (this.table[position] != null) {
        return this.table[position].value;
      }
    }
    return undefined;
  }

  /**
   * 从index位置重排后面的数据
   * @param index
   * 这个方法存在一个致命的错误,当元素删除了,但是又没有填充到这个删除的位置,
   * 会导致下一次找到这个值的时候,发现没有值
   private rearrangeData(index: any) {
    //获取下一个元素
    let current = this.table[++index];
    let keyIndex = this.hashCode(current.key);
    //如果下一个元素有值,并且该位置的值算出来的key值 >= index - 1,则将该值移动到前一个位置去
    while (current != null && keyIndex <= index - 1) {
      this.table[index - 1] = this.table[index];
      index++;
      current = this.table[index]
      keyIndex = this.hashCode(current.key);
    }
  }*/

  /**
   * 移动删除的元素
   * @param key       通过key计算起始位置
   * @param position  删除的位置
   */
  private rearrangeData(key: any, position: any) {
    //起始位置
    let startPosition = this.hashCode(key)
    let index = position + 1;
    //从删除位置的下一个位置开始迭代散列表,直到找到一个空位置,
    while (this.table[index] != null) {
      //获取下一个位置的position应该是多少
      let posHash = this.hashCode(this.table[index].key)
      //如果下一个位置的position <= 起始位置   或者下一个位置的position <= 删除位置
      if (posHash <= startPosition || posHash <= position) {
        // 将删除位置的值填到删除位置
        this.table[position] = this.table[index];
        //删除下一个位置
        delete this.table[index];
        //将新的位置转移到符合条件的位置上
        position = index;
      }
      index++;
    }
  }

  isEmpty() {
    return this.size() === 0;
  }

  size() {
    return this.count;
  }

  clear() {
    this.table = {};
    this.count = 0;
  }

  getTable() {
    return this.table;
  }

  toString() {
    if (this.isEmpty()) {
      return '';
    }
    const keys = Object.keys(this.table);
    let objString = `{${keys[0]} => ${this.table[keys[0]].toString()}}`;
    for (let i = 1; i < keys.length; i++) {
      objString = `${objString},{${keys[i]} => ${this.table[
        keys[i]
        ].toString()}}`;
    }
    return objString;
  }
}

书中代码

分离链接

export default class HashTableSeparateChaining<K, V> {
  protected table: { [key: string]: LinkedList<ValuePair<K, V>> };

  constructor(protected toStrFn: (key: K) => string = defaultToString) {
    this.table = {};
  }

  private loseloseHashCode(key: K) {
    if (typeof key === 'number') {
      return key;
    }
    const tableKey = this.toStrFn(key);
    let hash = 0;
    for (let i = 0; i < tableKey.length; i++) {
      hash += tableKey.charCodeAt(i);
    }
    return hash % 37;
  }

  hashCode(key: K) {
    return this.loseloseHashCode(key);
  }

  put(key: K, value: V) {
    if (key != null && value != null) {
      const position = this.hashCode(key);

      if (this.table[position] == null) {
        this.table[position] = new LinkedList<ValuePair<K, V>>();
      }
      this.table[position].push(new ValuePair(key, value));
      return true;
    }
    return false;
  }

  get(key: K) {
    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: K) {
    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;
  }

  isEmpty() {
    return this.size() === 0;
  }

  size() {
    let count = 0;
    Object.values(this.table).forEach(linkedList => count += linkedList.size());
    return count;
  }

  clear() {
    this.table = {};
  }

  getTable() {
    return this.table;
  }

  toString() {
    if (this.isEmpty()) {
      return '';
    }
    const keys = Object.keys(this.table);
    let objString = `{${keys[0]} => ${this.table[keys[0]].toString()}}`;
    for (let i = 1; i < keys.length; i++) {
      objString = `${objString},{${keys[i]} => ${this.table[
        keys[i]
      ].toString()}}`;
    }
    return objString;
  }
}

线性探查

直接删除版

export default class HashTableLinearProbing<K, V> {
  protected table: { [key: string]: ValuePair<K, V> };

  constructor(protected toStrFn: (key: K) => string = defaultToString) {
    this.table = {};
  }

  private loseloseHashCode(key: K) {
    if (typeof key === 'number') {
      return key;
    }
    const tableKey = this.toStrFn(key);
    let hash = 0;
    for (let i = 0; i < tableKey.length; i++) {
      hash += tableKey.charCodeAt(i);
    }
    return hash % 37;
  }

  hashCode(key: K) {
    return this.loseloseHashCode(key);
  }

  put(key: K, value: V) {
    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: K) {
    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;
  }

  remove(key: K) {
    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;
  }

  private verifyRemoveSideEffect(key: K, removedPosition: number) {
    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++;
    }
  }

  isEmpty() {
    return this.size() === 0;
  }

  size() {
    return Object.keys(this.table).length;
  }

  clear() {
    this.table = {};
  }

  getTable() {
    return this.table;
  }

  toString() {
    if (this.isEmpty()) {
      return '';
    }
    const keys = Object.keys(this.table);
    let objString = `{${keys[0]} => ${this.table[keys[0]].toString()}}`;
    for (let i = 1; i < keys.length; i++) {
      objString = `${objString},{${keys[i]} => ${this.table[
        keys[i]
      ].toString()}}`;
    }
    return objString;
  }
}

伪删除版

export default class HashTableLinearProbingLazy<K, V> {
  protected table: { [key: string]: ValuePairLazy<K, V> };

  constructor(protected toStrFn: (key: K) => string = defaultToString) {
    this.table = {};
  }

  private loseloseHashCode(key: K) {
    if (typeof key === 'number') {
      return key;
    }
    const tableKey = this.toStrFn(key);
    let hash = 0;
    for (let i = 0; i < tableKey.length; i++) {
      hash += tableKey.charCodeAt(i);
    }
    return hash % 37;
  }

  hashCode(key: K) {
    return this.loseloseHashCode(key);
  }

  put(key: K, value: V) {
    if (key != null && value != null) {
      const position = this.hashCode(key);

      if (
        this.table[position] == null ||
        (this.table[position] != null && this.table[position].isDeleted)
      ) {
        this.table[position] = new ValuePairLazy(key, value);
      } else {
        let index = position + 1;
        while (this.table[index] != null && !this.table[position].isDeleted) {
          index++;
        }
        this.table[index] = new ValuePairLazy(key, value);
      }
      return true;
    }
    return false;
  }

  get(key: K) {
    const position = this.hashCode(key);

    if (this.table[position] != null) {
      if (this.table[position].key === key && !this.table[position].isDeleted) {
        return this.table[position].value;
      }
      let index = position + 1;
      while (
        this.table[index] != null &&
        (this.table[index].key !== key || this.table[index].isDeleted)
      ) {
        if (this.table[index].key === key && this.table[index].isDeleted) {
          return undefined;
        }
        index++;
      }
      if (
        this.table[index] != null &&
        this.table[index].key === key &&
        !this.table[index].isDeleted
      ) {
        return this.table[position].value;
      }
    }
    return undefined;
  }

  remove(key: K) {
    const position = this.hashCode(key);

    if (this.table[position] != null) {
      if (this.table[position].key === key && !this.table[position].isDeleted) {
        this.table[position].isDeleted = true;
        return true;
      }
      let index = position + 1;
      while (
        this.table[index] != null &&
        (this.table[index].key !== key || this.table[index].isDeleted)
      ) {
        index++;
      }
      if (
        this.table[index] != null &&
        this.table[index].key === key &&
        !this.table[index].isDeleted
      ) {
        this.table[index].isDeleted = true;
        return true;
      }
    }
    return false;
  }

  isEmpty() {
    return this.size() === 0;
  }

  size() {
    let count = 0;
    Object.values(this.table).forEach(valuePair => {
      count += valuePair.isDeleted === true ? 0 : 1;
    });
    return count;
  }

  clear() {
    this.table = {};
  }

  getTable() {
    return this.table;
  }

  toString() {
    if (this.isEmpty()) {
      return '';
    }
    const keys = Object.keys(this.table);
    let objString = `{${keys[0]} => ${this.table[keys[0]].toString()}}`;
    for (let i = 1; i < keys.length; i++) {
      objString = `${objString},{${keys[i]} => ${this.table[
        keys[i]
      ].toString()}}`;
    }
    return objString;
  }
}

leetcode对应训练