关于javascript:趣味算法JS实现红绳算法匹配合适的另一半

因为我在朋友圈发动了一个流动

那么看看大家都留言了些什么数据呢？

意味着，两个要害数据：城市 + 数字(特殊字符)

城市：留下数据者的所在城市，然而当初车、马、书信都很快，所以这并不是咱们用来界定男女是否匹配的根据，只能说是有非凡需要，例如不承受异地恋的这种就匹配，本次咱们不思考
数字：就算是侥幸数字吧

用HashTable（也叫HashMap）的数据结构存储大家的信息
对于可能呈现抵触的 hash 值，应用 拆散链接 或者 线性探测 解决抵触
于小姐姐稀缺，小哥哥太多, 于是本次不辨别性别 ( 泪奔)

什么是`hashTable`

散列表（Hash table，也叫哈希表），是依据关键码值 (Key value) 而间接进行拜访的数据结构。也就是说，它通过把关键码值映射到表中一个地位来拜访记录，以放慢查找的速度。这个映射函数叫做散列函数，寄存记录的数组叫做散列表。
给定表 M，存在函数 f(key)，对任意给定的关键字值 key，代入函数后若能失去蕴含该关键字的记录在表中的地址，则称表 M 为哈希 (Hash）表，函数 f(key) 为哈希(Hash) 函数。

实现 HashTable，编写散列函数 loseloseHashCode

class HashTable {constructor() {this.table = []; // 数组模式存储
  }
 
 // 散列运算函数，可自定义
 // 此处时最常见的散列函数‘lose lose’static loseloseHashCode(key) {
      let hash = 0;
      for (var i = 0; i < key.length; i++) {hash += key.charCodeAt(i);
      }
      // 对 hash 取余，这是为了失去一个比拟小的 hash 值，// 然而这里取余的对象又不能太大，要留神
      return hash % 37;
  }
 
  // 批改和减少元素
  put(key, value) {const position = HashTable.loseloseHashCode(key);
    console.log(`${position} - ${key}`);
    this.table[position] = value;
  }
 
  get(key) {return this.table[HashTable.loseloseHashCode(key)];
  }
 
  remove(key) {this.table[HashTable.loseloseHashCode(key)] = undefined;
  }
}
 
const hash = new HashTable();
hash.put('Surmon', 'surmon.me@email.com') // 15 - Surmon
hash.put('Jhon', 'Jhonsnow@email.com') // 29 - Jhon
hash.put('Tyrion', 'Tyrion@email.com') // 16 - Tyrion
 
console.log(hash.get('Surmon')); // surmon.me@email.com
console.log(hash.get('Loiane')); // undefined
console.log(hash)

留神：散列函数实现有很多种，此处并非最优。

JS外面实现哈希表，用的是数组模式。通过 key 计算出 hash 作为下标，将 value 作为下标对应在数组中的值。
问题来了：如果没有下标的那一项，当然是 undefined, 然而如果 key 值计算后失去的hash 值反复了，那怎么办？会被笼罩掉。咱们不容许呈现这个问题. 因为咱们要把所有人的信息都存进去，明天介绍两种办法：
- 拆散链接
- 线性探测

（一）线性探测法
- 线性探测法是最简略的解决抵触的办法。
- （1）插入元素：插入元素时，如果发生冲突，算法将从该槽位向后遍历哈希表，直到找到表中的下一个空槽，并将该值放入到空槽当中。
- （2）查找元素：查找元素时，首先散列值所指向的槽，如果没有找到匹配，则持续从该槽向后遍历哈希表，直到：1）找到相应的元素；2）找到一个空槽（批示查找的元素不存在）；3）整个哈希表都遍历结束（批示该元素不存在并且哈希表已满,JS数组能够动静拓展长度，这个问题不存在）
- 线性探测法存在的毛病：
- （1）解决溢出须要另编程序。个别能够设立一个溢出表，用来寄存上述哈希表中放不下的记录。此溢出表最简略的构造是程序表，查找办法可用程序查找；
- （2）删除工作很简单。因为一旦对某一个元素删除后，该地位呈现空槽，后续查找到该空槽时会认为该元素不存在。须要一种办法对删除元素进行标记；
- （3）因为每次都是线性递增，容易导致堆聚，即存入哈希表的记录在表中都连成一片，后续发生冲突的可能性会越大。

简略来说：就是首次发现这个下标被存储占用了（阐明反复了）就会把下标自增 1，而后持续查找空的下标用于存储信息

（二）拆散链接
- 应用单链表存储 hash 对应的信息，如果插入时候发现反复了，就把这个最新的信息增加到链表头部，这样一个 HASH 就能够对应一个单链表存储信息，这个链表能够有限扩容，防止了反复

用 JS 实现单链表

function LinkedList() {

  // Node 辅助类，示意要退出列表的项，element 是行将增加到列表的值，next 是指向列表中下一个节点项的指针
  let Node = function (element) {
      this.element = element
      this.next = null
  }

  let length = 0
  let head = null

  // 向链表尾部追加元素
  this.append = function (element) {let node = new Node(element)
      let current
      if (head === null) { // 列表中第一个节点
          head = node
      } else {
          current = head
          while (current.next) {current = current.next // 找到最初一项，是 null}
          current.next = node // 给最初一项赋值
      }
      length++ // 更新列表的长度
  }

  // 从链表中移除指定地位元素
  this.removeAt = function (position) {if (position > -1 && position < length) { // 值没有越界
          let current = head
          let previous, index = 0
          if (position === 0) { //  移除第一项
              head = current.next
          } else {while (index++ < position) {
                  previous = current
                  current = current.next
              }
              previous.next = current.next // 将 previous 与 current 的下一项连接起来，跳过 current，从而移除
          }
          length-- // 更新列表的长度
          return current.element
      } else {return null}
  }

  // 在链表任意地位插入一个元素
  this.insert = function (position, element) {if (position >= 0 && position <= length) { // 查看越界值
          let node = new Node(element),
              current = head,
              previous,
              index = 0
          if (position === 0) { // 在第一个地位增加
              node.next = current
              head = node
          } else {while (index++ < position) {
                  previous = current
                  current = current.next
              }
              node.next = current // 在 previous 与 current 的下一项之间插入 node
              previous.next = node
          }
          length++
          return true
      } else {return false}
  }

  // 把链表内的值转换成一个字符串
  this.toString = function () {
      let current = head,
          string = ''
      while (current) {
          string += current.element + ' '
          current = current.next
      }
      return string
  }

  // 在链表中查找元素并返回索引值
  this.indexOf = function (element) {
      let current = head,
          index = 0
      while (current) {if (element === current.element) {return index}
          index++
          current = current.next
      }
      return -1
  }

  // 从链表中移除指定元素
  this.remove = function (element) {let index = this.indexOf(element)
      return this.removeAt(index)
  }

  this.isEmpty = function () {return length === 0}

  this.size = function () {return length}

  this.getHead = function () {return head}
}
let list = new LinkedList()
list.append(1)
list.append(2)
console.log(list.toString()) // 1 2
list.insert(0, 'hello')
list.insert(1, 'world')
console.log(list.toString()) // hello world 1 2
list.remove(1)
list.remove(2)
console.log(list.toString()) // hello world

收集用户数据，用户数据示例为：深圳，18，然而有很多条这种数据
咱们匹配用户，不依据它的城市和侥幸数组具体数值匹配，因为 金钱乱了年纪，大棚乱了四季
批改 hashTable 的put办法. 做避免反复解决，咱们这里应用拆散链接的办法，配合单链表~

  // 批改和减少元素
  put(key, value) {const position = HashTable.loseloseHashCode(key);
      console.log(`${position} - ${key}`);
      // 如果存在就间接在链表头部
      if (this.table[position]) {console.log(this.table[position].toString(), 1);
          this.table[position].insert(0, value);
      } else {
          // 否则新建一个单链表, 作为这个 hashTable 中 key 对应的 value
          const list = new LinkedList();
          list.append(value);
          console.log(list.toString(), 2);
          this.table[position] = list;
      }
  }

测试应用：

const hash = new HashTable();
hash.put('深圳', 69);
hash.put('深圳', 96);
console.log(hash.get('深圳').getHead(), 33);

合乎预期，用链表存储了所有雷同 key 的值

如何匹配？
先把所有数据录入到一个数组中

把所有数据塞入 hashTable

arr.forEach(item => {hash.put(Object.keys(item)[0], item[Object.keys(item)[0]]);
    });
    console.log(hash.get('深圳').getHead(),hash.get('深圳').size());

打印后果，深圳一共有 18 集体，还好咱们做了拆散链接保留了这些反复的 hash 对应的值：

每个 hash 即数组下标对应一个链表（如果有）/undefined(如果没有)

明天是七夕，于是我取出每个 hash 对应链表的第 7 个地位人进去匹配

       getGoodLuck = function(num) {const data = [];
            hash.table.forEach((list, index) => {
                let count = 0;
                let item = list.getHead();
                for (let i = 0; i < list.size(); i++) {
                    count++;
                    count === num && data.push({item, index});
                    item = item.next;
                }
            });
            return data;
        };
        console.log(getGoodLuck(7));

打印后果：

此时咱们再次打印 hashTable 中的散列函数，查看对应的 index 是什么城市

  // 批改和减少元素
            put(key, value) {const position = HashTable.loseloseHashCode(key);
                console.log(key, '------', position);
                // 如果存在就间接在链表头部
                if (this.table[position]) {this.table[position].insert(0, value);
                } else {
                    // 否则新建一个单链表, 作为这个 hashTable 中 key 对应的 value
                    const list = new LinkedList();
                    list.append(value);
                    this.table[position] = list;
                }
            }

最终发现：
- 杭州 —— 2
- 深圳 —— 0
- 北京 —— 8
- 广州 —— 10
- 上海 —— 12
意味着中奖名单是：
- 深圳 – 88
- 杭州 – 66
- 北京 – 9
- 广州 – 51
- 上海 – 22

选中每个 hash 对应的链表第 6 个和第 9 个，配对。

  console.log(getGoodLuck(6), 6);
  console.log(getGoodLuck(9), 9);

那么由两个数组前三个两两配对
- 深圳 97 配对深圳 66
- 天津 16 配对北京 66
- 北京 17 配对广州 23

本文目标：送书，七夕节祝大家高兴。给大家牵线，本文源码：https://github.com/JinJieTan/Peter-/blob/master/index.html
我是 Peter 谭老师，你如果我写的趣味学算法系列不错，能够点个赞和在看，反对下。当前会有更多趣味学习的文章, 欢送关注咱们公众号：【 前端巅峰】

关于javascript:趣味算法JS实现红绳算法匹配合适的另一半

明天主题

为什么要创造红绳算法？

剖析这个数据的意义

如何让大家匹配上？（正当且随机）

正式开始

什么是`hashTable`

开始入手

说人话

数据结构筹备结束！开始做事

数据结构和根底算法筹备结束

目前咱们的 hashTable 数据长这样

中奖规定设计

匹配恋情

写在最初

明天主题

为什么要创造红绳算法？

剖析这个数据的意义

如何让大家匹配上？（正当且随机）

正式开始

什么是hashTable

开始入手

说人话

数据结构筹备结束！开始做事

数据结构和根底算法筹备结束

目前咱们的 hashTable 数据长这样

中奖规定设计

匹配恋情

写在最初

什么是`hashTable`