hash函数

  1. //哈希
  3. class Hash {
  4.     constructor(str, size) {
  5.         if (
  6.             typeof str !== "string" || typeof size !== "number" ||
  7.             str.trim().length === 0 || size <= 0 || size % 1 > 0
  8.         ) {
  9.             throw new Error("Hash class的初始化参数不合规范！");
  10.         }
  11.         this.str = str;
  12.         this.size = size;
  13.         this.getHashCode();
  14.     }
  16.     //计算hashCode，扩大映射的那个值
  17.     getHashCode() {
  18.         const {str, size} = this;
  19.         //需要字典：默认unicode
  20.         //需要性能，秦九韶算法：提取公因式，循环累乘：
  21.         let hashCode = 0;
  22.         for (let i =0;i<str.length;i++){
  23.             //幂运算的底数，最好是质数：套路论：37用的多。
  24.           //这里有个疑问：str的空格，我到底要不要删掉？我没删，主动权给用户了！
  25.             hashCode = hashCode * 37 + str.charCodeAt(i);
  26.         }
  27.         this.hashCode = hashCode % size;
  28.     }
  29. }
  31. const hash1 = new Hash("abc", 101);
  32. const hash2 = new Hash("bcd ", 101);
  33. const hash3 = new Hash("cba", 101);
  35. console.log(hash1, hash2, hash3);

哈希表的添加和修改

  1. class HashTable {
  2.     constructor(size) {
  3.         this.table = [];
  4.         this.count = 0;  //存了多少个。
  5.         // 跟size对比，装载因子 >0.75，性能->扩容。
  6.         // 或<0.25时，内存大，count小，就减小数组的长度。自优化！
  7.         this.limit = size;  //table长度
  8.     }
  10.     //存储的数据是{kye,...data},key是唯一标识字段，可以得出index的根据，
  11.     // data,是要存入的数据
  12.     put(obj) {
  13.         if (!obj || typeof obj !== "object" || !obj.key) {
  14.             throw new Error("要存入的数据，必须要是个带有key字段属性的object!");
  15.         }
  16.         const i = new Hash(obj.key, this.limit).hashCode;
  17.         const current = this.table[i];
  18.         if (current) {
  19.           //这里很纠结的，首先，我解耦了要存的数据是个对象这种复杂类型，并且我没用数组
  20.             //链表存储时候，链表的查询方法indexOf那里，对比的是DoubleList里的data
  21.             //所以这里的对比就很真实对比了，要么对比简单数据的值，要么对比复杂对象的内存地址
  22.             //如果数据本身拷贝过，那就完了！而且data的值就是obj这个参数的值！
  23.             //这里就会限定死了如何匹配查找时，要传入的匹配参照就必须是原本的obj，而不是key
  24.             //当然，我确实需要扩展一下 LinkedList的indexOf方法，更健壮。
  25.             //当初封装的时候，我一直都有这方面的疑惑的，为啥不是凭借关键字段来匹配？
  26.             //后来觉得，没必要的，尽可能地简单字段。同时就算是复杂的数据的内存地址，那就全等于喽！
  28.             if (current.key === obj.key) {  //有key，就不是doublelinedlist class
  29.               //相等代表，修改操作！
  30.                 this.table[i] = obj;
  31.             } else if (current.key) {  //不相等，说明重复了！新建链表！
  32.                 const doublyLinkedList = new DoublyLinkedList(
  33.                     new DoublyList(current));
  34.                 doublyLinkedList.append(obj);
  35.                 this.table[i] = doublyLinkedList;
  36.                 this.count += 1;
  37.             } else {  //没有key，说明是链表了
  38.               //说的就是这里：匹配的是key！ 我改了indexOf的方法！为了更好用！
  39.                 const index = current.indexOf(obj.key, "key");
  40.                 if (index < 0) {
  41.                     current.append(obj);
  42.                     this.count += 1;
  43.                 } else {
  44.                     current.update(index, obj);
  45.                 }
  46.             }
  47.         } else {
  48.           //常规添加：
  49.             this.table[i] = obj;
  50.             this.count += 1;
  51.         }
  52.     }
  53. }
  55. const hash_table = new HashTable(7)
  57. hash_table.put(
  58.     {
  59.         key:'abc',name:'liuliu',age:24
  60.     }
  61. )
  62. hash_table.put(
  63.     {
  64.         key:'abc',name:'liuliu',age:22
  65.     }
  66. )
  67. console.log(hash_table.table,hash_table.count);
  69. setTimeout(
  70.     ()=>{
  71.         hash_table.put(
  72.             {
  73.                 key:'bcde',name:'liuliu',age:23
  74.             }
  75.         )
  76.         console.log('tt',hash_table.table,hash_table.count);
  77.     }
  78. )

通过key拿到数据：

  1.  get(key) {
  2.         const index = new Hash(key, this.limit).hashCode;
  3.         const current = this.table[index];
  4.         if (!current) return null;
  5.         if (current.key) return current;
  6.         const ind = current.indexOf(key, "key");  //linkedlist class扩展后的indexOf方法
  7.         if (ind < 0) return null;
  8.         return current.get(ind).data;
  9.     }

删除：

  1. remove(key) {
  2.         const index = new Hash(key, this.limit).hashCode;
  3.         const current = this.table[index];
  4.         if (current === undefined || current === null) return null;
  5.         if (current.key) {
  6.             this.table[index] = null;
  7.             return current;
  8.         };
  9.   //这里就是doubleLinkedList的实例了：
  10.         const ind = current.indexOf(key, "key");
  11.         if (ind < 0) return null;
  12.         this.count -= 1;
  13.         return current.removeAt(ind);
  14.   //到了这里，我突然就觉得indexOf方法的效率低了,indexOf不应该只是返回index，还要返回当前的list。如此
  15.   通过indexOf拿到的index,或者list节点，在removeAt上就太容易了！不需要通过index再 遍历确定list节点了。
  16.     }