最新公告
  • 欢迎您光临起源地模板网，本站秉承服务宗旨 履行“站长”责任，销售只是起点 服务永无止境！立即加入钻石VIP
    • 10年
    专注帝国cms二次开发
    升级SVIP
    站长资源平台
    当前位置：站长学院 > 综合教程 > TypeScript数据结构与算法：散列表

    TypeScript数据结构与算法：散列表

    正文概述 掘金(林景宜)   2021-04-18   555

    上一篇《TypeScript 数据结构与算法：字典》实现了 Typescript 中字典的数据结构与算法，本篇继续实现散列表。

    散列表（Hash Map，也叫哈希表 ）是一种特殊的字典实现。在一个普通的字典中，通过键直接来获取值。但是在散列表中，可以通过哈希函数先将键映射为一个内存地址，所以存储的结构由键 -> 值 变为了 键 -> 地址 -> 值。所以在查询时，可以通过键映射后的地址快速取值，避免了耗费性能的迭代查值过程。

    TypeScript数据结构与算法：散列表

    散列表有一些在计算机科学中应用的例子。因为它是字典的一种实现，所以可以用来对数据库进行索引。当我们在关系型数据库（如 MySQL、Microsoft SQL Server、Oracle，等等）中创建一个新的表时，同时创建一个索引可以更快地查询到记录的 key。在这种情况下，散列表可以用来保存键和对表中记录的引用。

    数据结构

    哈希函数

    因为转换出来的 hashCode 是一个内存地址，所以这个哈希函数的设计最好能满足下面三个原则：

    1. 哈希值是一个相对比较短的非负整数；
    2. 相同的键计算储的哈希值必需相同；
    3. 不同的键计算出来的哈希值应该不同；

    toStrFn 辅助方法

    由于键有可能是各种数据类型，所以第一步首先要把键映射为统一的 String 数据类型：

    /**
 * @description: 将item转换为字符串
 */
export function defaultToString(item: any): string {
  // 对于 null undefined和字符串的处理
  if (item === null) {
    return 'NULL';
  } else if (item === undefined) {
    return 'UNDEFINED';
  } else if (typeof item === 'string' || item instanceof String) {
    return `${item}`;
  }
  // 其他情况时调用数据结构自带的 toString 方法
  return item.toString();
}

    loselose 函数

    先从一个简单的哈希函数 loselose 开始，其实算法就是将字符串各个位上的 UTF-16 Unicode 值加起来，然后对 37 取余即为哈希值：

    const loseloseHashCode = (key: K): number => {
  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;
};

    djb2 函数

    可以发现，上述的 loselose 哈希算法有一个很重大缺点，就是不同的源字符串导致出现相同哈希值的概率很高，比如 Jonathan、Jamie、Sue 和 Aethelwulf 会有相同的哈希值 5。

    所以改进一下算法，将 hash 初始值设置 5381，每次迭代时将 hash 乘 33 再累加，最后对 1013 取余，使得出现重复哈希值得概率大幅度降低。

    const djb2HashCode = (key: K): number => {
  if (typeof key === 'number') {
    return key;
  }
  const tableKey = this.toStrFn(key);
  let hash = 5381;
  for (let i = 0; i < tableKey.length; i++) {
    hash = hash * 33 + tableKey.charCodeAt(i);
  }
  return hash % 1013;
};

    散列表

    有了计算哈希值的算法，接下来就可以实现散列表的数据结构：

    import { defaultToString } from '../util';

export default class HashTable<K, V> {
  protected table: Map<number, V>;

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

  /**
   * @description: 哈希函数
   */
  private djb2HashCode(key: K): number {
    if (typeof key === 'number') {
      return key;
    }
    const tableKey = this.toStrFn(key);
    let hash = 5381;
    for (let i = 0; i < tableKey.length; i++) {
      hash = hash * 33 + tableKey.charCodeAt(i);
    }
    return hash % 1013;
  }

  /**
   * @description: 计算键的哈希值
   */
  hashCode(key: K): number {
    return this.djb2HashCode(key);
  }

  /**
   * @description: 更新散列表
   */
  put(key: K, value: V): boolean {
    if (key != null && value != null) {
      const position = this.hashCode(key);
      this.table.set(position, value);
      return true;
    }
    return false;
  }

  /**
   * @description: 根据键获取值
   */
  get(key: K): V {
    return this.table.get(this.hashCode(key));
  }

  /**
   * @description: 根据键移除值
   */
  remove(key: K): boolean {
    return this.table.delete(this.hashCode(key));
  }

  /**
   * @description: 返回内部table
   */
  getTable(): Map<number, V> {
    return this.table;
  }

  /**
   * @description: 返回是否为空散列表
   */
  isEmpty(): boolean {
    return this.size() === 0;
  }

  /**
   * @description: 散列表的大小
   */
  size(): number {
    return this.table.size;
  }

  /**
   * @description: 清空散列表
   */
  clear() {
    this.table.clear();
  }

  /**
   * @description: 替代默认的toString
   */
  toString(): string {
    if (this.isEmpty()) {
      return '';
    }
    let objStringList = [];
    for (const [hashCode, value] of this.table) {
      objStringList.push(`{${hashCode} => ${value}}`);
    }
    return objStringList.join(',');
  }
}

    这里的散列表实现的其实并不完整，因为即使将 loselose 算法改为使用了 DJB 算法，或者说即使现在非常著名的 MD5、SHA、CRC 哈希算法，也没办法避免这用哈希冲突。原因就是由多映射到少，必然会出现冲突。导致新添加的键值对如果重复时会覆盖之前添加的值，所以这里需要对算法进行改进。

    分离链接散列表

    分离链接法（Separate Chaining Hash Table）是对散列表数据结构的改进，为散列表的每一个 hashcode 创建一个链表，并将键值对存储在链表中，它是解决冲突的最简单的方法。

    TypeScript数据结构与算法：散列表

    下面是分离链接散列表的实现（不能仅存储值，需要存储整个键值对）：

    import { defaultToString } from '../util';
import LinkedList from './linked-list';

export default class HashTableSeparateChaining<K, V> {
  protected table: Map<number, LinkedList<{ key: K; value: V }>>;

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

  /**
   * @description: 哈希函数
   */
  private loseloseHashCode(key: K): number {
    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;
  }

  /**
   * @description: 哈希函数封装
   */
  hashCode(key: K): number {
    return this.loseloseHashCode(key);
  }

  /**
   * @description: 更新散列表
   */
  put(key: K, value: V): boolean {
    if (key != null && value != null) {
      const position = this.hashCode(key);

      // 当该hashcode不存在时，先创建一个链表
      if (this.table.get(position) == null) {
        this.table.set(position, new LinkedList<{ key: K; value: V }>());
      }
      // 再给链表push值
      this.table.get(position).push({ key, value });
      return true;
    }
    return false;
  }

  /**
   * @description: 根据键获取值
   */
  get(key: K): V {
    const position = this.hashCode(key);
    const linkedList = this.table.get(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;
  }

  /**
   * @description: 根据键移除值
   */
  remove(key: K): boolean {
    const position = this.hashCode(key);
    const linkedList = this.table.get(position);
    if (linkedList != null && !linkedList.isEmpty()) {
      let current = linkedList.getHead();
      while (current != null) {
        if (current.element.key === key) {
          linkedList.remove(current.element);
          // 关键的一点，当链表为空以后，需要在tabel中删除掉hashcode
          if (linkedList.isEmpty()) {
            this.table.delete(position);
          }
          return true;
        }
        current = current.next;
      }
    }
    return false;
  }

  /**
   * @description: 返回是否为空散列表
   */
  isEmpty(): boolean {
    return this.size() === 0;
  }

  /**
   * @description: 散列表的大小
   */
  size(): number {
    let count = 0;
    // 迭代每个链表，累计求和
    for (const [hashCode, linkedList] of this.table) {
      count += linkedList.size();
    }
    return count;
  }

  /**
   * @description: 清空散列表
   */
  clear() {
    this.table.clear();
  }

  /**
   * @description: 返回内部table
   */
  getTable() {
    return this.table;
  }

  /**
   * @description: 替代默认的toString
   */
  toString(): string {
    if (this.isEmpty()) {
      return '';
    }

    let objStringList = [];
    for (const [hashCode, linkedList] of this.table) {
      let node = linkedList.getHead();
      while (node) {
        objStringList.push(`{${node.element.key} => ${node.element.value}}`);
        node = node.next;
      }
    }
    return objStringList.join(',');
  }
}

    线性探查散列表

    另一种解决冲突的方法是线性探查（Linear Probing Hash Table）。之所以称作线性，是因为它处理冲突的方法是将键值对直接存储到表中，而不是像分离链接一样存储在单独的数据结构中。

    当想向表中添加一个新键值对的时候，如果索引为 hashCode 的位置已经被占据了，就尝试 hashCode + 1 的位置。如果 hashCode + 1 的位置也被占据了，就尝试 hashCode + 2 的位置，以此类推，直到在散列表中找到一个空闲的位置。

    TypeScript数据结构与算法：散列表

    在删除的时候，需要检查是否有必要将后面的键值对向前挪动移动，避免出现空位置。下图展现了这个过程：

    TypeScript数据结构与算法：散列表

    下面是线性探查散列表的实现：

    import { defaultToString } from '../util';

export default class HashTableLinearProbing<K, V> {
  protected table: Map<number, { key: K; value: V }>;

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

  /**
   * @description: 哈希函数
   */
  private loseloseHashCode(key: K): number {
    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;
  }

  /**
   * @description: 哈希函数封装
   */
  hashCode(key: K): number {
    return this.loseloseHashCode(key);
  }

  /**
   * @description: 更新散列表
   */
  put(key: K, value: V): boolean {
    if (key != null && value != null) {
      const position = this.hashCode(key);

      if (this.table.get(position) == null) {
        // 当hashcode位置为空时，可以直接添加
        this.table.set(position, { key, value });
      } else {
        // 否则需要迭代查找最近的空位置再添加
        let index = position + 1;
        while (this.table.get(index) != null) {
          index++;
        }
        this.table.set(index, { key, value });
      }
      return true;
    }
    return false;
  }

  /**
   * @description: 根据键获取值
   */
  get(key: K): V {
    const position = this.hashCode(key);

    if (this.table.get(position) != null) {
      // 如果查到的hashcode位置就是要查的key，则直接返回
      if (this.table.get(position).key === key) {
        return this.table.get(position).value;
      }
      // 否则需要迭代着向下查找
      let index = position + 1;
      while (
        this.table.get(index) != null &&
        this.table.get(index).key !== key
      ) {
        index++;
      }
      if (this.table.get(index) != null && this.table.get(index).key === key) {
        return this.table.get(position).value;
      }
    }
    // 最后也没查到，就返回undefined
    return undefined;
  }

  /**
   * @description: 根据键移除值
   */
  remove(key: K): boolean {
    const position = this.hashCode(key);

    if (this.table.get(position) != null) {
      // 同理，如果hashcode对应位置就是要查的key，则直接删除
      if (this.table.get(position).key === key) {
        this.table.delete(position);
        // 删除后处理副作用
        this.verifyRemoveSideEffect(key, position);
        return true;
      }
      // 同理，如果hashcode对应的位置不是要查的key，就迭代查到
      let index = position + 1;
      while (
        this.table.get(index) != null &&
        this.table.get(index).key !== key
      ) {
        index++;
      }
      if (this.table.get(index) != null && this.table.get(index).key === key) {
        this.table.delete(index);
        // 同样在删除后处理副作用
        this.verifyRemoveSideEffect(key, index);
        return true;
      }
    }
    return false;
  }

  /**
   * @description: 处理移除键值对后的副作用
   */
  private verifyRemoveSideEffect(key: K, removedPosition: number) {
    const hash = this.hashCode(key);
    let index = removedPosition + 1;
    // 迭代着处理后面的每一个键值对
    while (this.table.get(index) != null) {
      const posHash = this.hashCode(this.table.get(index).key);
      // 挨个向前挪动，关键点在于，hashcode值比较小的键值对尽量先向前补位
      // 详细的说：如果当前元素的 hash 值小于或等于原始的 hash 值
      // 或者当前元素的 hash 值小于或等于 removedPosition（也就是上一个被移除 key 的 hash 值），
      // 表示我们需要将当前元素移动至 removedPosition 的位置
      if (posHash <= hash || posHash <= removedPosition) {
        this.table.set(removedPosition, this.table.get(index));
        this.table.delete(index);
        removedPosition = index;
      }
      index++;
    }
  }

  /**
   * @description: 返回是否为空散列表
   */
  isEmpty(): boolean {
    return this.size() === 0;
  }

  /**
   * @description: 散列表的大小
   */
  size(): number {
    return this.table.size;
  }

  /**
   * @description: 清空散列表
   */
  clear() {
    this.table.clear();
  }

  /**
   * @description: 返回内部table
   */
  getTable(): Map<number, { key: K; value: V }> {
    return this.table;
  }

  /**
   * @description: 替代默认的toString
   */
  toString(): string {
    if (this.isEmpty()) {
      return '';
    }

    let objStringList = [];
    for (const [hashCode, { key, value }] of this.table) {
      objStringList.push(`{${key} => ${value}}`);
    }
    return objStringList.join(',');
  }
}

    下一篇来分析树。

    前端记事本，不定期更新，欢迎关注！

    • 微信公众号： 林景宜的记事本
    • 博客：林景宜的记事本
    • 掘金专栏：林景宜的记事本
    • 知乎专栏： 林景宜的记事本
    • Github: MageeLin

    起源地下载网 » TypeScript数据结构与算法：散列表

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用？
    本站所有资源版权均属于原作者所有，这里所提供资源均只能用于参考学习用，请勿直接商用。若由于商用引起版权纠纷，一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了？
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量，若小于网盘提示的容量则是这个原因。这是浏览器下载的bug，建议用百度网盘软件或迅雷下载。若排除这种情况，可在对应资源底部留言，或 联络我们.。
    找不到素材资源介绍文章里的示例图片？
    对于PPT，KEY，Mockups，APP，网页模版等类型的素材，文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买，且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况，但部分素材会在素材包内有一份字体下载链接清单。
    模板不会安装或需要功能定制以及二次开发？
    请QQ联系我们
    掘金(林景宜)

    掘金(林景宜) SVIP

    分享到：

    相关推荐

    发表评论

    还没有评论，快来抢沙发吧！

    如需帝国cms功能定制以及二次开发请联系我们

    联系作者

    请选择支付方式

    ×
    迅虎支付宝
    迅虎微信
    支付宝当面付
    余额支付
    ×
    微信扫码支付 0 元