hash.js

export function hashFn(string, limit = 7) {
  const PRIME = 31
  let hashCode = 0
  for (let item of string) {
    hashCode = PRIME * hashCode + item.charCodeAt()
  }
  return hashCode % limit
}
export function isPrime(number) {
  if (number <= 1) return false
  let temp = Math.ceil(Math.sqrt(number))
  for (let i = 2; i < temp; i++) {
    if (number % i === 0) {
      return false
    }
  }
  return true
}

export class HashTable {
  constructor() {
    this.storage = []
    this.count = 0 //存储当前存放元素的个数
    this.limit = 7 // 哈希表的长度
    // 填充因子（已有个数/总个数
    this.loadFactor = 0.75
    this.minLoadFactor = 0.25
  }
  //根据number获取最临近的质数
  getPrime(number) {
    while (!isPrime(number)) {
      number++
    }
    return number
  }
  // 往hash 里面添加数据(假设是一个三位数组)
  // 首先找到应该添加到的一维的下表，然后找到二位数组的地方，最后在添加
  put(key, value) {
    let index = this.storage[this.hashFn(key)] //1、根据 key 获取要映射到 storage 里面的 index（通过哈希函数获取）
    let bucket = this.storage[index] // 2、根据 index 取出对应的 bucket
    if (bucket === undefined) { //3、判断是否存在 bucket
      bucket = []
      this.storage[index] = bucket
    }
    // 4、判断是插入数据操作还是修改数据操作
    for (let i = 0; i < bucket.length; i++) {
      let tuple = bucket[i]
      if (tuple[0] === key) { // 如果 key 相等，则修改数据
        tuple[1] === value // 修改完 tuple 里数据，return 终止，不再往下执行。
        return
      }
    }
    // 5、bucket 新增数据
    this.bucket.push([key, value])
    this.count++
    // 判断哈希表是否要扩容，若装填因子 > 0.75，则扩容
    if (this.count / this.limit > this.loadFactor) {
      this.resize(this.getPrime(this.limit * 2))
    }
  }

  // 根据 get(key) 获取 value
  get(key) {
    let index = this.storage[this.hashFn(key)] //1、根据 key 获取要映射到 storage 里面的 index（通过哈希函数获取）
    let bucket = this.storage[index] // 2、根据 index 取出对应的 bucket
    if (bucket === undefined) { //3、判断是否存在 bucket
      return null
    }
    // 4、判断是插入数据操作还是修改数据操作
    for (let i = 0; i < bucket.length; i++) {
      let tuple = bucket[i]
      if (tuple[0] === key) { // 如果 key 相等，则修改数据
        return tuple[1]
      }
    }
    return null
  }

  // remove(key) 删除指定 key 的数据
  remove(key) {
    let index = this.storage[this.hashFn(key)] //1、根据 key 获取要映射到 storage 里面的 index（通过哈希函数获取）
    let bucket = this.storage[index] // 2、根据 index 取出对应的 bucket
    if (bucket === undefined) { //3、判断是否存在 bucket
      return null
    }
    // 4、判断是插入数据操作还是修改数据操作
    for (let i = 0; i < bucket.length; i++) {
      let tuple = bucket[i]
      if (tuple[0] === key) { // 如果 key 相等，则修改数据
        bucket.splice(i, 1)
        this.count--;
        // 根据装填因子的大小，判断是否要进行哈希表压缩
        if (this.limit > 7 && this.count / this.limit < this.minLoadFactor) {
          this.resize(this.getPrime(Math.floor(this.limit / 2)));
        }
        return tuple
      }
    }
    return null
  }
  isEmpty() {
    return this.count === 0
  }
  size() {
    return this.count
  }
  // 重新调整哈希表大小，扩容或压缩
  resize(newLimit) {
    const oldStorage = this.storage
    this.storage = []
    this.count = 0
    this.limit = newLimit
    // 3、遍历 oldStorage，取出所有数据，重新 put 到 this.storage
    for (let bucket of oldStorage) {
      if (bucket) {
        for (const b of bucket) {
          this.put(b[0], b[1])
        }
      }
    }
  }
}