趣味算法：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）由于每次都是线性递增，容易导致堆聚，即存入哈希表的记录在表中都连成一片，后续发生冲突的可能性会越大。

  • （二）分离链接

    • 使用单链表存储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

写在最后

  • 本文目的：送书，七夕节祝大家快乐。给大家牵线，本文源码：https://github.com/JinJieTan/Peter-/blob/master/index.html

  • 我是Peter谭老师，你如果我写的趣味学算法系列不错，可以点个赞和在看，支持下。以后会有更多趣味学习的文章,欢迎关注我们公众号：【前端巅峰】

以上是 趣味算法：JS实现红绳算法（匹配合适的另一半） 的全部内容， 来源链接： utcz.com/a/40537.html

回到顶部