明天主题

为什么要创造红绳算法？

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

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

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

剖析这个数据的意义

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

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

  • 用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 - Surmonhash.put('Jhon', 'Jhonsnow@email.com') // 29 - Jhonhash.put('Tyrion', 'Tyrion@email.com') // 16 - Tyrion console.log(hash.get('Surmon')); // surmon.me@email.comconsole.log(hash.get('Loiane')); // undefinedconsole.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 2list.insert(0, 'hello')list.insert(1, 'world')console.log(list.toString()) // hello world 1 2list.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谭老师，你如果我写的趣味学算法系列不错，能够点个赞和在看，反对下。当前会有更多趣味学习的文章,欢送关注咱们公众号：【前端巅峰】