乐趣区

关于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,然而有很多条这种数据
  • 咱们匹配用户,不依据它的城市和侥幸数组具体数值匹配,因为 金钱乱了年纪,大棚乱了四季
  • 批改 hashTableput办法. 做避免反复解决,咱们这里应用拆散链接的办法,配合单链表~
  // 批改和减少元素
  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 对应的值:

目前咱们的 hashTable 数据长这样

  • 每个 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 谭老师,你如果我写的趣味学算法系列不错,能够点个赞和在看,反对下。当前会有更多趣味学习的文章, 欢送关注咱们公众号:【 前端巅峰
退出移动版