哈希表

也称散列表，是一种特殊的字典实现。

简单来说，正常的字典是通过键访问值的，但是在哈希表中，键首先会被哈希转换为某个数组下标。然后通过这个下标获取元素。

js 引擎内部已经将 Map 及 Object 优化为哈希表了。

// 在实现哈希表前，需要先实现将键转换为哈希的方法
/**
 * 转换字符串函数
 * @param item key值
 */
export function defaultToString (item: any): string {
  // 对于 null undefined 的处理
  if (!item) return ''
  else if (typeof item === 'string' || item instanceof String) return `${item}`
  return item?.toString()
}

/**
 * 将数据转换为 hash 值 即 将字符串每个位的 utf-16 unicode 值相加后 对 37 取余
 * @param key key值
 * @returns hash 值
 */
export const loseHashCode = <K> (key: K): number => {
  if (typeof key === &#039;number&#039;) return key
  const tableKey: string = defaultToString(key)
  let hash: number = 0
  for (let i = 0; i < tableKey.length; i++) hash += tableKey.charCodeAt(i)
  return hash % 37
}
/**
 * 将数据转换为 hash 值 在 loseHashCode 的基础上改进
 * @param key key值
 * @returns 改进后的 hash 值
 */
export const djb2HashCode = <K> (key: K): number => {
  if (typeof key === &#039;number&#039;) return key
  const tableKey: string = defaultToString(key)
  let hash = 5381
  for (let i = 0; i < tableKey.length; i++) hash = hash * 33 + tableKey.charCodeAt(i)
  return hash % 1013
}

// 简单的哈希表展示
class HashMap<V>  {
  protected djb2HashCode: (key: number) => number = djb2HashCode

  hashCode (key: number): number {
    return this.djb2HashCode(key)
  }

  put (key: number, value: V): boolean {
    if (!key || !value) return false
    const position = this.hashCode(key)
    this.table.set(position, value)
    return true
  }

  get (key: number): V {
    return this.table.get(this.hashCode(key))!
  }

  remove (key: number): boolean {
    return this.table.delete(this.hashCode(key))
  }

  getTable (): Map<number, V> {
    return this.table
  }

  isEmpty (): boolean {
    return this.size() === 0
  }

  size (): number {
    return this.table.size
  }

  clear (): void {
    this.table.clear()
  }

  toString (): string {
    if (this.isEmpty()) return &#039;&#039;
    let objStrList: string[] = []
    for (const [hashCode, value] of this.table) objStrList.push(`${hashCode} => ${value}`)
    return objStrList.join(&#039;,&#039;)
  }
}