/**
 * 哈希函數(shù)，將 key 映射成 index
 * @param key 要轉(zhuǎn)換的 key
 * @param max 數(shù)組的長(zhǎng)度（最大的數(shù)值）
 * @returns
 */
function hashFunc(key: string, max: number): number {
  // 1. 計(jì)算 hashCode cats => 60337 （27為底的時(shí)候）
  let hashCode = 0;
  const length = key.length;
  for (let i = 0; i < length; i++) {
    // 霍納法則計(jì)算 hashCode
    hashCode = 31 * hashCode + key.charCodeAt(i);
  }
  // 2. 求出索引值
  const index = hashCode % max;
  return index;
}

class HashTable<T = any> {
  // 創(chuàng)建一個(gè)數(shù)組，用來存放鏈地址法中的鏈
  storage: [string, T][][] = [];
  // 定義數(shù)組的長(zhǎng)度
  private length: number = 7;
  // 記錄已經(jīng)存放元素的個(gè)數(shù)
  private count: number = 0;
}

put(key: string, value: T) {
  // 1.根據(jù)key 獲取數(shù)組中對(duì)應(yīng)的索引值
  const index = this.hashFunc(key, this.length);
  // 2. 取出索引值對(duì)應(yīng)位置的數(shù)組
  let bucket = this.storage[index];
  // 3. 判斷 bucket 是否有值
  if (!bucket) {
    bucket = [];
    this.storage[index] = bucket;
  }
  // 4. 確定已經(jīng)有一個(gè)數(shù)組了，但是數(shù)組中是否已經(jīng)存在 key 時(shí)不確定的
  let isUpdate = false;
  for (let i = 0; i < bucket.length; i++) {
    const tuple = bucket[i];
    const tupleKey = tuple[0];
    if (tupleKey === key) {
      // 修改/更新的操作
      tuple[1] = value;
      isUpdate = true;
    }
  }
  // 5. 如果上面的代碼沒有進(jìn)行覆蓋，那么在該位置進(jìn)行添加
  if (!isUpdate) {
    bucket.push([key, value]);
    this.count++
  }
}

const hashTable = new HashTable();
hashTable.put("aaa", 200);
hashTable.put("bbb", 300);
hashTable.put("ccc", 400);

  get(key: string): T | undefined {
    // 1. 根據(jù) key 獲取索引值 index
    const index = this.hashFunc(key, this.length);
    // 2. 獲取 bucket（桶）
    const bucket = this.storage[index];
    if (!bucket) return undefined;
    // 3. 對(duì) bucket 進(jìn)行遍歷
    for (let i = 0; i < bucket.length; i++) {
      const tuple = bucket[i];
      const tupleKey = tuple[0];
      const tupleValue = tuple[1];
      if (tupleKey === key) {
        return tupleValue;
      }
    }
    return undefined;
  }

  get(key: string): T | undefined {
    // 1. 根據(jù) key 獲取索引值 index
    const index = this.hashFunc(key, this.length);
    // 2. 獲取 bucket（桶）
    const bucket = this.storage[index];
    if (!bucket) return undefined;
    // 3. 對(duì) bucket 進(jìn)行遍歷
    for (let i = 0; i < bucket.length; i++) {
      const tuple = bucket[i];
      const tupleKey = tuple[0];
      const tupleValue = tuple[1];
      if (tupleKey === key) {
        return tupleValue;
      }
    }
    return undefined;
  }

  delete(key: string): T | undefined {
    // 1. 獲取索引值的位置
    const index = this.hashFunc(key, this.length);
    // 2. 獲取 bucket（桶）
    const bucket = this.storage[index];
    if (!bucket) return undefined;
    // 3. 對(duì) bucket 進(jìn)行遍歷
    for (let i = 0; i < bucket.length; i++) {
      const tuple = bucket[i];
      const tupleKey = tuple[0];
      const tupleValue = tuple[1];
      if (tupleKey === key) {
        bucket.splice(i, 1);
        this.count--;
        return tupleValue;
      }
    }
    return undefined;
  }

const hashTable = new HashTable();
hashTable.put("aaa", 200);
hashTable.put("bbb", 300);
hashTable.put("ccc", 400);
hashTable.delete('aaa')
console.log(hashTable.get("aaa")); // undefined
console.log(hashTable.get("bbb")); // 300
console.log(hashTable.get("ccc")); // 400

private resize(newLength) {
  // 設(shè)置新的長(zhǎng)度
  this.length = newLength;
  // 獲取原來所有的數(shù)據(jù)，并且重新放入到新的容量數(shù)組中
  // 1. 對(duì)數(shù)據(jù)進(jìn)行的初始化操作
  const oldStorage = this.storage;
  this.storage = [];
  this.count = 0;
  // 2. 獲取原來數(shù)據(jù)，放入新的數(shù)組中
  oldStorage.forEach((bucket) => {
    if (!bucket) return;
    for (let i = 0; i < bucket.length; i++) {
      const tuple = bucket[i];
      this.put(tuple[0], tuple[1]);
    }
  });
}

  put(key: string, value: T) {
    // 1.根據(jù)key 獲取數(shù)組中對(duì)應(yīng)的索引值
    const index = this.hashFunc(key, this.length);
    console.log({ index });
    // 2. 取出索引值對(duì)應(yīng)位置的數(shù)組
    let bucket = this.storage[index];
    // 3. 判斷 bucket 是否有值
    if (!bucket) {
      bucket = [];
      this.storage[index] = bucket;
    }
    // 4. 確定已經(jīng)有一個(gè)數(shù)組了，但是數(shù)組中是否已經(jīng)存在 key 時(shí)不確定的
    let isUpdate = false;
    for (let i = 0; i < bucket.length; i++) {
      const tuple = bucket[i];
      const tupleKey = tuple[0];
      if (tupleKey === key) {
        // 修改/更新的操作
        tuple[1] = value;
        isUpdate = true;
      }
    }
    // 5. 如果上面的代碼沒有進(jìn)行覆蓋，那么在該位置進(jìn)行添加
    if (!isUpdate) {
      bucket.push([key, value]);
      this.count++;
+     // 發(fā)現(xiàn) loadFactor 比例已經(jīng)大于 0.75，那么就直接擴(kuò)容
+     const loadFactor = this.count / this.length;
+     if (loadFactor > 0.75) {
+       this.resize(this.length * 2);
+     }
    }
  }

  delete(key: string): T | undefined {
    // 1. 獲取索引值的位置
    const index = this.hashFunc(key, this.length);
    // 2. 獲取 bucket（桶）
    const bucket = this.storage[index];
    if (!bucket) return undefined;
    // 3. 對(duì) bucket 進(jìn)行遍歷
    for (let i = 0; i < bucket.length; i++) {
      const tuple = bucket[i];
      const tupleKey = tuple[0];
      const tupleValue = tuple[1];
      if (tupleKey === key) {
        bucket.splice(i, 1);
        this.count--;
+       // 發(fā)現(xiàn) loadFactor 比例已經(jīng)小于 0.75，那么就直接縮容
+       const loadFactor = this.count / this.length;
+       if (loadFactor < 0.25 && this.length > 7) {
+         this.resize(Math.floor(this.length / 2));
+       }
        return tupleValue;
      }
    }
    return undefined;
  }

const hashTable = new HashTable();
hashTable.put("aaa", 200);
hashTable.put("bbb", 300);
hashTable.put("ccc", 400);
hashTable.put("ddd", 500);
hashTable.put("eee", 600);
console.log(hashTable.storage.length); // 7
hashTable.put("fff", 600);
console.log(hashTable.storage.length); // 14
hashTable.delete("fff");
hashTable.delete("eee");
console.log(hashTable.storage.length); // 14
hashTable.delete("ddd");
console.log(hashTable.storage.length); // 7