得到质数

为啥？因为想让各个映射的数据分布更均匀，不扎堆！重复的也不会在一个index上重复一堆！

判断扩容的数据是否为质数，如果不是，那就强试：

  1.          getPrime(num) {
  2.         while (!this.isPrime(num)) {
  3.             num += 1;
  4.         }
  5.         return num;
  6.     }

然后逻辑放到扩容的那个步骤里，对this.limit赋值那里进行保底！

完整封装-链式地址法——用的链表

  2. const {DoublyLinkedList, DoublyList} = require("./linked-list");
  5. class Hash {
  6.     constructor(str, size) {
  7.         if (
  8.             typeof str !== "string" || typeof size !== "number" ||
  9.             str.trim().length === 0 || size <= 0 || size % 1 > 0
  10.         ) {
  11.             throw new Error("Hash class的初始化参数不合规范！");
  12.         }
  13.         this.str = str;
  14.         this.size = size;
  15.         this.getHashCode();
  16.     }
  18.     //计算hashCode，扩大映射的那个值
  19.     getHashCode() {
  20.         const {str, size} = this;
  21.         //需要字典：默认unicode
  22.         //需要性能，秦九韶算法：提取公因式，循环累乘：
  23.         let hashCode = 0;
  24.         for (let i = 0; i < str.length; i++) {
  25.             //幂运算的底数，最好是质数：套路论：37用的多。
  26.             hashCode = hashCode * 37 + str.charCodeAt(i);
  27.         }
  28.         this.hashCode = hashCode % size;
  29.     }
  30. }
  32. const hash1 = new Hash("abc", 7);
  33. const hash2 = new Hash("bcde", 7);
  34. const hash3 = new Hash("cab", 7);
  36. console.log(hash1, hash2, hash3);
  38. class HashTable {
  39.     constructor(size) {
  40.         this.table = [];
  41.         this.count = 0;  //存了多少个。
  42.         // 跟size对比，装载因子 >0.75，性能->扩容。
  43.         // 或<0.25时，内存大，count小，就减小数组的长度。自优化！
  44.         this.limit = size;  //table长度
  45.     }
  47.     //存储的数据是{kye,...data},key是唯一标识字段，可以得出index的根据，
  48.     // data,是要存入的数据
  49.     put(obj) {
  50.         if (!obj || typeof obj !== "object" || !obj.key) {
  51.             throw new Error("要存入的数据，必须要是个带有key字段属性的object!");
  52.         }
  53.         const i = new Hash(obj.key, this.limit).hashCode;
  54.         const current = this.table[i];
  55.         if (current) {
  56.             //这里很纠结的，首先，我解耦了要存的数据是个对象这种复杂类型，并且我没用数组
  57.             //链表存储时候，链表的查询方法indexOf那里，对比的是DoubleList里的data
  58.             //所以这里的对比就很真实对比了，要么对比简单数据的值，要么对比复杂对象的内存地址
  59.             //如果数据本身拷贝过，那就完了！而且data的值就是obj这个参数的值！
  60.             //这里就会限定死了如何匹配查找时，要传入的匹配参照就必须是原本的obj，而不是key
  61.             //当然，我确实需要扩展一下 DoubleLinkedList的indexOf方法，更健壮。
  62.             //当初封装的时候，我一直都有这方面的疑惑的，为啥不是凭借关键字段来匹配？
  63.             //后来觉得，没必要的，尽可能地简单字段。同时就算是复杂的数据的内存地址，那就全等于喽！
  64.             if (current.key === obj.key) {
  65.                 this.table[i] = obj;
  66.             } else if (current.key) {
  67.                 const doublyLinkedList = new DoublyLinkedList(
  68.                     new DoublyList(current));
  69.                 doublyLinkedList.append(obj);
  70.                 this.table[i] = doublyLinkedList;
  71.                 this.count += 1;
  72.                 this.largerResize();  //扩容
  73.             } else {
  74.                 const index = current.indexOf(obj.key, "key");
  75.                 if (index < 0) {
  76.                     current.append(obj);
  77.                     this.count += 1;
  78.                     this.largerResize(); //扩容
  79.                 } else {
  80.                     current.update(index, obj);
  81.                 }
  82.             }
  83.         } else {
  84.             this.table[i] = obj;
  85.             this.count += 1;
  86.             this.largerResize();  //扩容
  87.         }
  88.     }
  90.     get(key) {
  91.         const index = new Hash(key, this.limit).hashCode;
  92.         const current = this.table[index];
  93.         if (current === undefined || current === null) return null;
  94.         if (current.key) return current;
  95.         const ind = current.indexOf(key, "key");
  96.         if (ind < 0) return null;
  97.         return current.get(ind).data;
  98.     }
  100.     remove(key) {
  101.         const index = new Hash(key, this.limit).hashCode;
  102.         const current = this.table[index];
  103.         if (current === undefined || current === null) return null;
  104.         if (current.key) {
  105.             this.table[index] = null;
  106.             this.smallerResize();  //缩容
  107.             return current;
  108.         }
  109.         const ind = current.indexOf(key, "key");
  110.         if (ind < 0) return null;
  111.         this.count -= 1;
  112.         const val = current.removeAt(ind);
  113.         if (current.length === 0) {
  114.             this.table[index] = null;
  115.         }
  116.         this.smallerResize();  //缩容
  117.         return val;
  118.     }
  120.     largerResize() {
  121.         const test = this.count / this.limit;
  122.         if (test > 0.75) {
  123.             this.resize(this.limit * 2);
  124.         }
  125.     }
  127.     smallerResize() {
  128.         const test = this.count / this.limit;
  129.         if (test < 0.2 && this.limit > 20) {
  130.             this.resize(Math.floor(this.limit / 2));
  131.         }
  132.     }
  134.     resize(size) {
  135.         this.limit = this.getPrime(size);  //这里进行质数担保
  136.         const storage = this.table;
  137.         this.table = [];
  138.         this.count = 0;
  139.         storage.map(
  140.             val => {
  141.                 if (val) {
  142.                     if (val.key) {
  143.                         this.put(val);
  144.                         this.count++;
  145.                     } else if (!val.key) {
  146.                         let current = val.header;
  147.                         while (current) {
  148.                             this.put(current.data);
  149.                             this.count++;
  150.                         }
  151.                     }
  152.                 }
  153.             }
  154.         );
  155.     }
  157.     isPrime(num) {
  158.         let res = true, i = 2;
  159.         while (res && i <= Math.sqrt(num)) {
  160.             num % i === 0 && (res = false);
  161.         }
  162.         return res;
  163.     }
  165.     getPrime(num) {   //质数担保
  166.         while (!this.isPrime(num)) {
  167.             num += 1;
  168.         }
  169.         return num;
  170.     }
  172.     isEmpty() {
  173.         return this.count === 0;
  174.     }
  176.     get size() {
  177.         return this.count;
  178.     }
  179. }