Skip to main content

David LiuAbout 11 min

雁过留痕

小组如何分工合作的？

Redis Zset 结构/原理？

skiplist 跳表结构（一段八股）

跳表（Skip List）是一种有序数据结构，它通过在链表中添加多级索引来提高查找效率。跳表的原理如下：

  1. 基本结构：跳表由多个层级组成，每个层级都是一个有序的链表。最底层是原始链表，每个节点包含一个元素和指向下一个节点的指针。每个层级的链表都是原始链表的子集。

  2. 索引层级：除了原始链表外，跳表还包含多个索引层级。每个索引层级都是原始链表的一个子集，其中的节点包含指向下一个层级的指针。每个节点的指针可以跳过多个节点，从而实现快速的查找。

  3. 查找操作：跳表的查找操作从最顶层的索引层级开始，逐层向下查找。在每个层级中，从当前节点开始，比较目标元素与当前节点的值。如果目标元素小于当前节点的值，则向下一层级继续查找；如果目标元素大于等于当前节点的值，则继续在当前层级中向右查找。直到找到目标元素或者无法继续向下查找为止。

  4. 插入操作：插入操作首先进行查找，找到插入位置后，将新节点插入到对应的层级中，并更新相应的指针。为了保持跳表的平衡性，插入操作时会随机决定是否在更高层级添加索引节点。

  5. 删除操作：删除操作首先进行查找，找到目标节点后，将其从每个层级的链表中移除，并更新相应的指针。

跳表的优点是在有序链表的基础上，通过多级索引提高了查找效率，平均查找时间复杂度为O(log n)。相比于平衡二叉树等其他数据结构，跳表的实现相对简单，并且支持高效的插入和删除操作。

跳表相比于红黑树的优点：

  1. 实现简单：跳表的实现相对于红黑树来说更加简单。红黑树是一种复杂的自平衡二叉搜索树，需要维护节点的颜色和旋转操作等复杂的逻辑。而跳表的实现相对简单，只需要通过添加多级索引来提高查找效率。

  2. 空间效率：跳表相对于红黑树在空间效率上更加优越。红黑树需要为每个节点额外存储颜色信息，而跳表只需要存储节点的值和指针信息。跳表的索引层级可以通过调整层数来平衡空间占用和查询效率。

  3. 查询效率：在某些情况下，跳表的查询效率可以与红黑树相媲美甚至更好。虽然红黑树的查询时间复杂度为O(log n)，但是跳表的平均查询时间复杂度也为O(log n)。而且跳表的查询操作不需要进行旋转等复杂的操作，因此在实际应用中可能更快。

  4. 可扩展性：跳表相对于红黑树更容易扩展。在跳表中，可以通过调整索引层级的数量来平衡查询效率和空间占用。而红黑树的平衡性需要通过旋转等操作来维护，扩展性相对较差。

需要注意的是，红黑树在某些操作上仍然具有优势，例如插入和删除操作的平均时间复杂度为O(log n)，而跳表的插入和删除操作可能需要更新多个层级的指针。因此，在具体应用场景中，需要根据实际需求和数据特点来选择合适的数据结构。

为什么用 Zset

  • 首先Zset可以保证唯一性，一个用户只能点赞一个帖子一次，防止出现刷赞的情况
  • 其次Zset可以保证有序性，我们用点赞时间作为score值，那么

Zset 怎么用的

  1. 每个post的id加上业务前缀组成key存储一个zset，记录每个点赞的用户id和点赞的时间。
  2. score值如何选取的：点赞时间作为score，
    1. 这样可以自动按照时间排序，展示有序的点赞列表
    2. 可以高效的统计一个时间段内点赞的数量，绘制对应的分析图谱，比如按周统计点赞量，只需要利用zset的范围查询，可以在logn级别内找到这个范围来进行统计。

BitMap 原理

Redis的BitMap是一种位图数据结构，用于对大量的二进制位进行高效的操作和存储。它基于字符串类型，每个字符串可以存储2^32个位（即512MB）。

BitMap的原理如下：

  1. 存储结构：BitMap使用字符串来存储位图数据。每个二进制位被存储为一个字符，可以是0或1。字符串的长度由位图的大小决定。

  2. 位操作：BitMap支持对位进行操作，包括设置位、清除位、获取位的值等。通过对字符串进行位操作，可以高效地进行位图的增删改查操作。

  3. 内存优化：BitMap使用了紧凑的存储方式，每个二进制位只占用一个比特位。相比于使用布尔数组等其他数据结构，BitMap可以节省大量的内存空间。

  4. 位运算：BitMap支持位运算操作，如与（AND）、或（OR）、异或（XOR）等。这些位运算操作可以对多个位图进行逻辑运算，得到新的位图结果。

为什么用 BitMap

Redis的BitMap是一种高效的位图数据结构，可以在二值状态场景下进行位级别的操作和存储。它在内存占用和性能方面都具有优势，适用于需要对大量二进制位进行操作的场景。

BitMap 在实际应用中适合记录二值状态的数据，比如是否登录、是否签到。

  • 统计在线用户：可以使用 BitMap 记录用户的在线状态，每个用户对应一个位，位值为1表示在线，位值为0表示离线。通过位操作可以高效地统计在线用户数量。

  • 布隆过滤器：可以使用 BitMap 实现布隆过滤器，用于判断一个元素是否存在于一个集合中。每个元素对应一个位，通过多次哈希函数计算位的位置，并将对应位设置为1。判断元素是否存在时，检查对应位的值即可。

  • 计数器：可以使用 BitMap 实现计数器功能，每个位对应一个计数值。通过位操作可以对计数器进行增减操作，实现高效的计数功能。

BitMap 怎么用的

  1. 每个用户每个月作为key单独存储一个BitMap，这样31位2二进制数的内存下就可以存储一个月中每天登录与否的信息。只需要在一个int的存储空间内即可记录下一个用户一整月的登录信息。
  2. 在统计连续一周登录的时候，
    • 在同一个月内统计连续登录时，只需要不断判断是否有长度为7的连续的1
    • 跨不同个月统计时，只需要考虑进去上一个月后6天和这个月开头的6天，判断这一段中是否有长度为7的连续的1.

如何预生成订单ID的

封装了一个组件：RedisIDWorker

截屏2023-07-07 21.12.08

以天为单位，在redis中记录一个自增的键，然后以当前的时间戳拼接上这个字增建，即可构建符合单调递增性和唯一性的id生成器。

为什么用 RabbitMQ

解耦合，消息异步通信

RabbitMQ 组件有哪些

Broker：一个RabbitMQ进程就是一个Broker

Exchange：交换机

Queue：队列

RabbitMQ 怎么用的

结合SpringAMQP

仿掘金官网

常用推荐算法有哪些

  • 经典算法

    • 协同过滤：基于用户评分的相似性或项目之间的相似性

      • User-based CF
      • Item-based CF
      • 矩阵分解
        • SVD
        • SVD++

    • 基于内容

  • 深度学习

TrustSVD 原理和优点

原理：

  1. 矩阵分解：TrustSVD使用矩阵分解技术将用户-项目评分矩阵分解为两个低维矩阵，分别表示用户和项目的潜在特征。这样可以捕捉到用户和项目之间的关系和偏好。

  2. 信任关系建模：除了用户-项目评分数据，TrustSVD还考虑了用户之间的信任关系。它引入了一个信任矩阵，用于表示用户之间的信任程度。通过将信任矩阵与用户-项目评分矩阵相结合，可以更准确地预测用户对项目的评分。

  3. 优化目标：TrustSVD使用最小化均方根误差（RMSE）作为优化目标，通过梯度下降等优化算法来学习用户和项目的潜在特征，以及信任关系的权重。

优点：

  1. 考虑信任关系：TrustSVD能够利用用户之间的信任关系来提升推荐的准确性。这对于社交网络等场景中的推荐系统特别有用，因为用户之间的信任关系可以提供额外的信息来推断用户的偏好。

  2. 捕捉潜在特征：通过矩阵分解，TrustSVD可以捕捉到用户和项目的潜在特征。这使得它能够在数据稀疏的情况下进行准确的推荐，同时还能够进行个性化的推荐。

  3. 可扩展性：TrustSVD的算法相对简单，易于实现和扩展。它可以与其他推荐算法结合使用，或者用于构建更复杂的混合推荐系统。

  4. 鲁棒性：TrustSVD对于数据中的噪声和缺失值具有一定的鲁棒性。它能够通过学习用户和项目的潜在特征来填补缺失值，并减少噪声的影响。

常用加密算法有哪些

  1. 对称加密算法（Symmetric Encryption）：对称加密算法使用相同的密钥来进行加密和解密。常见的对称加密算法包括：

    1. DES（Data Encryption Standard）、
    2. 3DES（Triple DES）、
    3. AES（Advanced Encryption Standard）

  2. 非对称加密算法（Asymmetric Encryption）：非对称加密算法使用一对密钥，即公钥和私钥。公钥用于加密数据，私钥用于解密数据。常见的非对称加密算法包括

    1. RSA（Rivest-Shamir-Adleman）、
    2. DSA（Digital Signature Algorithm）、
    3. ECC（Elliptic Curve Cryptography）等。

  3. 摘要算法/哈希函数（Hash Function）：哈希函数将任意长度的数据映射为固定长度的哈希值。常见的哈希函数包括

    1. MD5（Message Digest Algorithm 5）、
    2. SHA-1（Secure Hash Algorithm 1）、
    3. SHA-256

    哈希函数通常用于验证数据的完整性，而不是加密数据本身。

  4. 数字签名（Digital Signature）：数字签名使用非对称加密算法来验证消息的发送者和消息的完整性。常见的数字签名算法包括RSA、DSA等。

  5. 数字信封，用于在计算机网络中安全地传输数据。它基于非对称加密算法和对称加密算法的组合。

    在使用数字信封进行数据传输时，发送方首先生成一对非对称加密算法所需的公钥和私钥。发送方使用接收方的公钥对数据进行加密，形成一个密文。然后，发送方使用自己的私钥对对称加密算法所需的密钥进行加密，并将其附加到密文中。这个密文和加密后的对称密钥一起构成了数字信封。

    接收方收到数字信封后，首先使用自己的私钥解密对称密钥，然后使用对称密钥解密密文，从而获取原始的明文数据。

    数字信封的优势在于它结合了非对称加密和对称加密的优点。非对称加密算法提供了安全的密钥交换机制，而对称加密算法提供了高效的数据加密和解密过程。通过使用数字信封，可以在不安全的网络环境中安全地传输数据，同时保护数据的机密性和完整性。

    需要注意的是，数字信封只提供了数据的保密性和完整性，而没有提供身份验证。因此，在使用数字信封进行数据传输时，还需要考虑其他安全机制，如数字签名和身份验证，以确保数据的安全性。

为什么要用MD5+随机盐

如果不随机加盐的话，可以被彩虹表或字典攻击而破解，安全性存在问题。

比如说一些常用的密码可能是一些有规律的单词或数字组成的，如姓名+生日等，就可以通过构建常用单词的字典，组合碰撞出对应的密码。

David's Blog
Copyright © 2024 David Liu