五大数据结构

一. String: 字符串

数据结构中，字符串要单独用一种存储结构来存储，称为串存储结构。这里的串指的就是字符串。

严格意义上讲，串存储结构也是一种线性存储结构，因为字符串中的字符之间也具有”一对一”的逻辑关系。只不过，与之前所学的线性存储结构不同，串结构只用于存储字符类型的数据。

存储一个字符串，数据结构包含以下 3 种具体存储结构：

1. 定长顺序存储：实际上就是用普通数组（又称静态数组）存储。例如 C 语言使用普通数据存储字符串的代码为 char a[20] = “data.biancheng.net”；
2. 堆分配存储：用动态数组存储字符串；
3. 块链存储：用链表存储字符串；
   

二. Hash: 散列

Hash，一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入（又叫做预映射 pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

概念

若结构中存在和关键字 K 相等的记录，则必定在 f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系 f 为散列函数（Hash function），按这个事先建立的表为散列表。

对不同的关键字可能得到同一散列地址，即 key1≠key2，而 f(key1)=f(key2)，这种现象称碰撞。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数 H(key)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象” 作为记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。

若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。

性质

所有散列函数都有如下一个基本特性：如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果。但另一方面，散列函数的输入和输出不是一一对应的，如果两个散列值相同，两个输入值很可能是相同的，但不绝对肯定二者一定相等（可能出现哈希碰撞）。输入一些数据计算出散列值，然后部分改变输入值，一个具有强混淆特性的散列函数会产生一个完全不同的散列值。

典型的散列函数都有无限定义域，比如任意长度的字节字符串，和有限的值域，比如固定长度的比特串。在某些情况下，散列函数可以设计成具有相同大小的定义域和值域间的一一对应。一一对应的散列函数也称为排列。可逆性可以通过使用一系列的对于输入值的可逆“混合”运算而得到。

三. List: 列表

在编程语言中 List 是标准类库中的一个类，可以简单视之为双向链表，以线性列的方式管理物件集合。list 的特色是在集合的任何位置增加或删除元素都很快，但是不支持随机存取。list 是类库提供的众多容器（container）之一，除此之外还有 vector、set、map 等。list 以模板方式实现（即泛型），可以处理任意型别的变量，包括使用者自定义的资料型态例如：它可以是一个放置整数（int）型态的 list、也可以是放置字串（char 或 string）型态的 list、或者放置使用者自定类别（user-defined class）的 list。

有序的 collection（也称为序列）。此接口的用户可以对列表中每个元素的插入位置进行精确地控制。用户可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。

列表是一种可变的、有序的数据结构，可以随时添加和删除其中的元素。 列表非常适合利用顺序和位置定位某一元素，尤其是当元素的顺序或内容经常发生改变时。 与字符串不同，列表是可变的。

四. Set: 集合

集合（set）是一个无序的不重复元素序列。

集合中的元素不会重复，并且可以进行交集、并集、差集等常见的集合操作。

可以使用大括号 { } 创建集合，元素之间用逗号 , 分隔， 或者也可以使用 set() 函数创建集合。

特点

Set（集合）是一种无序的、不重复的数据结构，它的特点如下：

1. 集合中的元素是无序的：Set 中的元素没有顺序，无法通过索引来访问。
2. 集合中的元素是唯一的：Set 中不允许有重复的元素，每个元素在集合中只能出现一次。
3. 内部实现采用哈希表或树形结构：Set 内部通常是基于哈希表或平衡树等数据结构实现的。
4. 可以用于去重和快速查找：因为 Set 中的元素是唯一的，所以可以很方便地用来做去重操作。同时，由于内部实现采用哈希表或树形结构，所以查找某个元素的时间复杂度为 O(1) 或 O(log n)。
5. Set 中的元素必须是可哈希的：由于 Set 中的元素是基于哈希表实现的，所以集合中的元素必须是可哈希的，即元素必须有一个明确的哈希值。如果一个元素没有哈希值，那么它就不能被用作 Set 的元素。

五. Sorted Set: 有序集合

Zset，即有序集合（Sorted Set），是 Redis 提供的一种复杂数据类型。 Zset 是 set 的升级版，它在 set 的基础上增加了一个权重参数 score，使得集合中的元素能够按 score 进行有序排列。 在 Zset 中，集合元素的添加、删除和查找的时间复杂度都是 O(1)。