jsp 淘宝网站验证码 设计什么是优化
Redis 数据类型？
主要有 STRING、LIST、ZSET、SET 和 HASH。
STRING
String 类型底层的数据结构实现主要是 SDS（简单动态字符串），其主要应用场景包括：
- 缓存对象：可以用 STRING 缓存整个对象的 JSON；
- 计数：Redis 处理命令是单线程，所以执行命令的过程是原子的。故 String 适合技术场景，比如计算访问次数、点赞、转发、库存数量等；
- 分布式锁：利用 SETNX 命令；
- 共享 Session 信息：服务器都会去同一个 Redis 获取相关的 Session 信息，解决了分布式系统下 Session 存储的问题；
LIST
LIST 类型底层采用双向链表和压缩列表实现。
- 若列表元素个数小于 512 个，其元素值小于 64 bytes，Redis 用压缩列表作为 List 类型的底层数据结构；
- 否则使用双向链表；
Redis 3.2 之后，List 类型底层只由 quicklist 实现。Redis 7.0 之后，压缩列表数据结构被废弃，由 listpack 实现。
LIST 的应用场景包括：
- 微信朋友圈点赞：要求按照点赞顺序显示点赞好友的信息，如果点赞取消则移除相应的好友信息；
- 消息队列：可以使用左进右出的命令组成来完成队列的设计。
HASH
Hash 类型的底层数据结构是由压缩列表或哈希表实现的：
- 如果哈希类型元素个数小于 512 个，所有值小于 64 字节的话，Redis 会使用压缩列表作为 Hash 类型的底层数据结构；
- 如果哈希类型元素不满足上面条件，Redis 会使用哈希表作为 Hash 类型的底层数据结构。
在Redis 7.0 中，压缩列表数据结构被废弃，交由 listpack 来实现。HASH 应用场景主要有：
- 缓存对象：一般采用 String + JSON 存储，对象中某些频繁变化的属性可以考虑抽出来用 Hash 类型存储；
- 购物车：以用户 id 为 key，商品 id 为 field，商品数量为 value，恰好构成了购物车的3个要素。
SET
Set 类型的底层数据结构是由哈希表或整数集合实现的：
- 如果集合中的元素都是整数且元素个数小于 512个，Redis 会使用整数集合作为 Set 类型的底层数据结构；
- 如果集合中的元素不满足上面条件，则 Redis 使用哈希表作为 Set 类型的底层数据结构。
为什么 Redis 中的 SET 是 Key-Value 结构？
原因在于，Redis 是一个键值对数据库，其中的所有数据类型（String、List、Hash、Set、Sorted Set 等）都以 key-value 的形式存储。对于 Set 来说，key 是集合名称，value 是集合的内容。
SET 应用的主要场景：
- 点赞：key 是文章 id、value 是用户 id；
- 共同关注：Set 类型支持交集运算，故可用来计算共同好友或共同关注的公众号。key 是用户 id，value 是已关注的公众号的 id；
- 去重：存储某活动中中奖的用户名 ，Set 类型因为有去重功能，可以保证同一个用户不会中奖两次。
ZSET
ZSET 类型（Sorted Set，有序集合）可以根据元素的权重来排序，可以自己来决定每个元素的权重值。比如说，可以根据元素插入Sorted Set 的时间确定权重值，先插入的元素权重小，后插入的元素权重大。应用场景主要有：
- 在面对需要展示最新列表、排行榜等场景时，如果数据更新频繁或者需要分页显示，可以优先考虑使用 ZSET；
- 有序集合比较典型的使用场景就是排行榜。例如学生成绩的排名榜、游戏积分排行榜、视频播放排名、电商系统中商品的销量排名等。
BITMAP
bit 是计算机中最小的单位，使用它进行储存将非常节省空间，特别适合一些数据量大且使用二值统计的场景。可以用于签到统计、判断用户登陆态等操作。
HyperLogLog
HyperLogLog用于统计，统计规则是基于概率完成的，不准确，标准误算率是 0.81%。优点是，在输入元素的数量或者体积非常非常大时，所需的内存空间总是固定的、并且很小。比如百万级网页 UV 计数等；
GEO
主要用于存储地理位置信息，并对存储的信息进行操作。底层是由Zset实现的，使用GeoHash编码方法实现了经纬度到Zset中元素权重分数的转换，这其中的两个关键机制就是「对二维地图做区间划分」和「对区间进行编码」。一组经纬度落在某个区间后，就用区间的编码值来表示，并把编码值作为Zset元素的权重分数。
Stream
Redis专门为消息队列设计的数据类型。相比于基于 List 类型实现的消息队列，有这两个特有的特性：自动生成全局唯一消息ID，支持以消费组形式消费数据。
之前方法缺陷：不能持久化，无法可靠的保存消息，并且对于离线重连的客户端不能读取历史消息。
Redis 底层数据结构？
SDS
SDS 不仅可以保存字符串，还可以保存二进制数据。
SDS 可以在 O(1) 内获取字符串长度，因为有 Len 属性。
SDS 不会发生缓冲区溢出，因为 SDS 在拼接字符串之前会检查空间是否满足要求，如果空间不够那么就自动扩容，故不会导致缓冲区溢出的问题。
链表
Redis 封装了名为 listNode 的数据结构，并构成双向链表。双向链表包括节点数量len，以及可以自定义实现的 dup、free、match 函数。
- listNode 链表结点的结构中只包含 prev 和 next 指针；
- list 提供了 head 和 tail 指针，因此获取链表首尾元素的时间复杂度为
O(1)。
缺点：
- 链表每个节点之间的内存都是不连续的，无法很好利用 CPU 缓存。能很好利用CPU缓存的数据结构是数组，因为数组的内存是连续的。
- 保存一个链表节点的值都需要一个链表节点结构头的分配，内存开销较大。
压缩列表
压缩列表是由连续内存块组成的顺序型数据结构，类似于数组。不仅可以利用 CPU 缓存，而且会针对不同长度的数据，进行相应编码，这种方法可以有效地节省内存开销。不能保存过多的元素，否则查询效率就会降低；新增或修改某个元素时，压缩列表占用的内存空间需要重新分配，甚至可能引发连锁更新的问题。
缺点：
- 空间扩展操作也就是重新分配内存，因此连锁更新一旦发生，就会导致压缩列表占用的内存空间要多次重新分配，直接影响到压缩列表的访问性能。
- 如果保存的元素数量增加了，或是元素变大了，会导致内存重新分配，会有连锁更新的问题。
- 压缩列表只会用于保存的节点数量不多的场景，只要节点数量足够小，即使发生连锁更新也能接受。
哈希
哈希表是一种保存键值对(key-value)的数据结构。优点在于能以O(1)的复杂度快速查询数据。Redis 采用了拉链法来解决哈希冲突，在不扩容哈希表的前提下，将具有相同哈希值的数据串起来，形成链接。
跳表
跳表（Skip List） 是一种基于有序链表的数据结构，通过添加多级索引来实现高效的查找、插入和删除操作。跳表的平均时间复杂度为 O(log n)，接近平衡树的性能，但实现更简单。
跳表的核心思想
一. 多层链表
- 跳表由多层链表组成，最底层是完整的有序链表，每一层都是下一层的“索引”；
- 每一层的元素是随机选择的，高层元素少，低层元素多；
二. 跳跃查找：
- 查找时从最高层开始，如果当前节点的下一个节点小于目标值，则向右移动；否则向下移动一层。
- 通过跳跃查找，可以快速缩小查找范围。
三. 随机化
- 插入新节点时，通过随机算法决定节点的高度（即层数），保证跳表的平衡性。
整数集合
整数集合本质上是一块连续内存空间。
整数集合有一个升级规则，就是当将一个新元素加入到整数集合里面，如果新元素的类型（int32_t）比整数集合现有所有元素的类型（int16_t）都要长时，整数集合需要先进行升级，也就是按新元素的类型（int32_t）扩展 contents 数组的空间大小，然后才能将新元素加入到整数集合里，升级的过程中也要维持整数集合的有序性。
quicklist
其实 quicklist 就是双向链表 + 压缩列表组合，quicklist 就是一个链表，而链表中的每个元素又是一个压缩列表。quicklist 解决办法，通过控制每个链表节点中的压缩列表的大小或者元素个数，来规避连锁更新的问题。因为压缩列表元素越少或越小，连锁更新带来的影响就越小，从而提供了更好的访问性能。
listpack
listpack 没有压缩列表中记录前一个节点长度的字段了，listpack 只记录当前节点的长度，当向 listpack 加入一个新元素的时候，不会影响其他节点的长度字段的变化，从而避免了压缩列表的连锁更新问题。
为什么用跳表而不用平衡树？
- 从内存占用上来说，跳表比平衡树更灵活一些：平衡树每个结点包含 2 个指针，而跳表每个结点平均包含
1/(1-p)。 - 在做范围查找的时候，跳表比平衡树操作要简单：在平衡树上，找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在跳表上进行范围查找就非常简单，只需要在找到小值之后，对第 1 层链表进行若干步的遍历就可以实现。
- 从算法的实现难度上来说，跳表比平衡树要简单很多：平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而跳表的插入和删除只需要修改相邻节点的指针，操作简单又快速。