跳表（Skip List）是一种数据结构，旨在提供高效的插入、删除和查找操作，同时保持相对简单的实现。它结合了链表和二叉搜索树的优点，通过引入多级索引来加速查找过程。跳表最早由William Pugh在1989年提出，并因其高效性和易于实现而被广泛应用于各种场景，尤其是在分布式系统和内存数据库中。

1. 基本概念

跳表本质上是一个多层链表，每一层都是对下一层的“抽样”或“稀疏表示”。最底层（通常称为第0层）包含所有元素，按升序排列。每一层之上的层则只包含一部分元素，形成一个稀疏的索引。随着层数的增加，每一层的元素数量逐渐减少，直到最顶层可能只有少数几个元素。

字典的实现

Redis 的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。

接下来的三个小节将分别介绍 Redis 的哈希表、哈希表节点、以及字典的实现。

哈希表

Redis 字典所使用的哈希表由 dict.h/dictht 结构定义：

typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;

链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度。

作为一种常用数据结构，链表内置在很多高级的编程语言里面，因为 Redis 使用的 C 语言并没有内置这种数据结构，所以 Redis 构建了自己的链表实现。

链表在 Redis 中的应用非常广泛，比如列表键的底层实现之一就是链表：当一个列表键包含了数量比较多的元素，又或者列表中包含的元素都是比较长的字符串时，Redis 就会使用链表作为列表键的底层实现。

举个例子，以下展示的 integers 列表键包含了从 1 到 1024 共一千零二十四个整数：

数据结构与对象

简单动态字符串

SDS的定义

每个 sds.h/sdshdr 结构表示一个 SDS 值：

struct sdshdr {
    // 记录 buf 数组中已使用字节的数量
    // 等于 SDS 所保存字符串的长度
    int len;
    // 记录 buf 数组中未使用字节的数量
    int free;
    // 字节数组，用于保存字符串
    char buf[];
};

1、Redis数据结构介绍

（1）STRING

	value：可以是字符串、整数或者浮点数      

	operate：对整个字符串或者字符串的其中一部分执行操作；对整数和浮点数执行自增（increment）或者自减(decrement)操作

（2）LIST

	value：一个链表，链表上的每个节点都包含了—个字符串

	operate：从链表的两端推入或者弹出元素;根据偏移量对链表进行修剪(trim)；读取单个或者多个元素;根据值查找或者移除元素

1、介绍

    Queue： 基本上，一个队列就是一个先入先出（FIFO）的数据结构
    Queue接口与List、Set同一级别，都是继承了Collection接口。LinkedList实现了Deque接 口。

2、Queue的实现：

一个是以ConcurrentLinkedQueue为代表的高性能队列；
一个是以BlockingQueue接口为代表的阻塞队列；

（1）没有实现的阻塞接口队列

	没有实现的阻塞接口的LinkedList： 实现了java.util.Queue接口和java.util.AbstractQueue接口

1、什么是hash表

	散列表（hash table，也叫哈希表），是根据关键码值（key value）而直接进行访问的数据结构。

	也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫 散列函数，存放记录的数组叫做散列表。

	给定表M，存在函数f（key），对于任意给定的关键字值 key，代入函数后若能得到包含改关键字的记录在表中的地址，则称表M为哈希（hash）表，函数 f（key）为哈希（hash）函数。

2、hash冲突

	对应不同的关键字可能获得相同的 hash 地址，即 key1 ≠ key2，但是f（key1） = f（key2）。这种现象就是冲突，而且这种冲突只能尽可能的减少，不能完全避免。

	因为哈希函数是从关键字集合和地址集合的映像，通畅关键字集合比较大，而地址集合的元素仅为哈希表中的地址值。

一、Comparable比较器的使用

	JAVA中可以通过实现 Comparable接口的方式让对象进行排序。使用方法：

		1、实体继承Comparable

		2、实现compareTo方法，根据需求进行比较

package com.bjut.fight.utils.comparable;

public class Student implements Comparable<Student> {
    private String name;
    private int age;

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int compareTo(Student o) {
        // 1表示大于，-1表示小于，0表示等于
        return this.age >= o.age ? 1 : -1;
    }

    public void print() {
        System.out.println(this.name + "," + this.age);
    }
}