趣味算法：JS实现红绳算法（匹配合适的另一半）

Peter谭金杰

发布于 2020-08-28 09:53:26

6660

发布于 2020-08-28 09:53:26

文章被收录于专栏：跨平台全栈俱乐部跨平台全栈俱乐部

分析这个数据的意义

城市：留下数据者的所在城市，但是现在车、马、书信都很快，所以这并不是我们用来界定男女是否匹配的依据，只能说是有特殊需求，例如不接受异地恋的这种就匹配，本次我们不考虑
数字：就算是幸运数字吧

如何让大家匹配上？（合理且随机）

用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对应的值：

目前我们的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

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

数据结构

编程算法

登录后参与评论

0 条评论

热度

趣味算法：JS实现红绳算法（匹配合适的另一半）

趣味算法：JS实现红绳算法（匹配合适的另一半）

分析这个数据的意义

如何让大家匹配上？（合理且随机）

正式开始

什么是`hashTable`

开始动手

说人话

数据结构准备完毕！开始做事

数据结构和基础算法准备完毕

目前我们的hashTable数据长这样

中奖规则设计

匹配爱情

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

趣味算法：JS实现红绳算法（匹配合适的另一半）

趣味算法：JS实现红绳算法（匹配合适的另一半）

分析这个数据的意义

如何让大家匹配上？（合理且随机）

正式开始

什么是hashTable

开始动手

说人话

数据结构准备完毕！开始做事

数据结构和基础算法准备完毕

目前我们的hashTable数据长这样

中奖规则设计

匹配爱情

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

什么是`hashTable`