哈希表

哈希表（hash table），又称散列表，它通过建立键 key 与值 value 之间的映射，实现高效的元素查询。具体而言，我们向哈希表中输入一个键 key ，则可以在 O(1) 时间内获取对应的值 value 。

如图 6-1 所示，给定 n 个学生，每个学生都有“姓名”和“学号”两项数据。假如我们希望实现“输入一个学号，返回对应的姓名”的查询功能

哈希表简单实现

除留余数法（Modulo Method）

• 哈希值通过将键除以哈希表的大小，然后取余数得到。

• 哈希函数形式：hash(key) = key % table_size

• 简单但容易产生冲突，尤其是在键的分布不均匀时。

class Pair {
        constructor(key, val) {
          this.key = key;
          this.val = val;
        }
      }
      class ArrayHashMap {
        buckets;
        len;
        constructor(len = 100) {
          this.buckets = new Array(len).fill(null);
          this.len = len;
        }
        hashFunc(key) {
          return key % this.len;
        }
        set(key, val) {
          this.buckets[this.hashFunc(key)] = new Pair(key, val);
        }
        get(key) {
          let index = this.hashFunc(key);
          let pair = this.buckets[index];
          if (pair === null) return null;
          return pair.val;
        }
        delect(key) {
          let index = this.hashFunc(key);
          let pair = this.buckets[index];
          if (pair === null) return null;
          this.buckets[index] = null;
          return pair.val;
        }
        keys() {
          let arr = [];
          for (let i = 0; i < this.buckets.length; i++) {
            if (this.buckets[i] !== null) {
              arr.push(this.buckets[i].key);
            }
          }
          return arr;
        }
        values() {
          let arr = [];
          for (let i = 0; i < this.buckets.length; i++) {
            if (this.buckets[i] !== null) {
              arr.push(this.buckets[i].val);
            }
          }
          return arr;
        }
        size() {
          return this.buckets.filter((item) => item !== null).length;
        }
        has(key) {
          let index = this.hashFunc(key);
          let pair = this.buckets[index];
          if (pair === null) return false;
          return true;
        }
        forEach(callback) {
          this.buckets.filter((item) => item !== null).forEach(callback);
        }
      }

动态实现

class Pair {
       constructor(key, val) {
         this.key = key;
         this.val = val;
       }
     }
     class HashMapChaining {
       size; // 键值对数量
       capacity; // 容量
       loadThres; // 触发扩容的负载因子阈值
       extendRatio; // 扩容倍数
       buckets; // 桶数组
       constructor() {
         this.size = 0;
         this.capacity = 4;
         this.loadThres = 2.0 / 3.0;
         this.extendRatio = 2;
         this.buckets = new Array(this.capacity).fill(null).map((x) => []);
       }
       hashFunc(key) {
         const stringKey = JSON.stringify(key);
         let hash = 0;
         for (let i = 0; i < stringKey.length; i++) {
           hash = (hash + stringKey.charCodeAt(i) * i) % this.capacity;
         }
         return hash;
       }
       loadFactor() {
         return this.size / this.capacity;
       }
       set(key, val) {
         if (this.loadFactor() > this.loadThres) {
           this.extend();
         }
         const index = this.hashFunc(key);
         const bucket = this.buckets[index];
         for (let pair of bucket) {
           if (pair.key === key) {
             pair.val = val;
             return;
           }
         }
         bucket.push(new Pair(key, val));
         this.size++;
       }
       get(key) {
         const index = this.hashFunc(key);
         const bucket = this.buckets[index];
         for (let pair of bucket) {
           if (pair.key === key) {
             return pair.val;
           }
         }
         return null;
       }
       extend() {
         const bucketsTmp = this.buckets;
         this.capacity *= this.extendRatio;
         this.buckets = new Array(this.capacity).fill(null).map(() => []);
         this.size = 0;
         for (let bucket of bucketsTmp) {
           for (const pair of bucket) {
             this.set(pair.key, pair.val);
           }
         }
       }
       delete(key) {
         const index = this.hashFunc(key);
         const bucket = this.buckets[index];
         for (let i = 0; i < bucket.length; i++) {
           if (bucket[i].key === key) {
             bucket.splice(i, 1);
             this.size--;
             break;
           }
         }
       }
       has(key) {
         return this.get(key) !== null;
       }
     }