Scheme 数据结构：list、vector、hash-table

Scheme 提供三种核心内置数据结构：list（列表）、vector（向量）和 hash-table（哈希表）。它们在内存布局、访问速度和使用场景上有显著区别。掌握它们的创建、读取、修改和查询方法，是高效编写 Scheme 程序的基础。

一、list：链式结构，适合顺序处理

list 是 Scheme 最基础的数据结构，本质是一个单向链表。它支持任意长度，元素类型可混用，但随机访问效率低。

创建 list

• 使用 list 函数：
  (list 1 "hello" #t) 返回包含三个元素的列表。
• 使用引号字面量：
  '(1 2 3) 等价于 (list 1 2 3)，但注意引号内的内容不可包含变量（会被当作字面值）。
• 使用 cons 构造：
  (cons 1 '(2 3)) 返回 (1 2 3)。cons 将一个元素“拼接”到已有列表头部。

访问元素

• 获取第一个元素：调用 car。
  (car '(a b c)) 返回 a。
• 获取除第一个外的剩余部分：调用 cdr。
  (cdr '(a b c)) 返回 (b c)。
• 获取第 n 个元素（从 0 开始）：调用 list-ref。
  (list-ref '(x y z) 1) 返回 y。

修改与拼接

• 在头部添加元素：使用 cons。
  (cons 'new lst) 返回新列表，原列表不变（Scheme 中 list 默认不可变）。
• 拼接两个列表：调用 append。
  (append '(1 2) '(3 4)) 返回 (1 2 3 4)。

注意：所有 list 操作均返回新列表，不修改原列表。若需可变列表，需使用 set-car! 或 set-cdr!，但一般不推荐。

二、vector：连续内存，支持快速随机访问

vector 是定长数组，元素在内存中连续存储，支持 O(1) 时间复杂度的随机访问，适合频繁读写指定位置的场景。

创建 vector

• 使用 vector 函数：
  (vector 10 20 30) 返回长度为 3 的向量。
• 使用 make-vector 初始化固定长度：
  (make-vector 5 0) 创建长度为 5、所有元素初始化为 0 的向量。
• 使用字面量语法：
  #(apple banana cherry) 表示一个包含三个符号的向量。

访问元素

• 读取第 i 个元素：调用 vector-ref。
  (vector-ref #(10 20 30) 1) 返回 20（索引从 0 开始）。

修改元素

• 更新第 i 个位置的值：调用 vector-set!。

  (define v (vector 1 2 3))
  (vector-set! v 1 99)
  ; 此时 v 变为 #(1 99 3)

其他操作

• 获取长度：调用 vector-length。
  (vector-length #(a b c)) 返回 3。
• 转换为 list：调用 vector->list。
  (vector->list #(1 2 3)) 返回 (1 2 3)。
• 从 list 创建 vector：调用 list->vector。

vector 是可变的，vector-set! 会直接修改原向量，无需重新赋值。

三、hash-table：键值映射，高效查找

hash-table（哈希表）用于存储键值对，通过键快速查找对应值，平均查找时间为 O(1)，适合实现字典、缓存等结构。

创建 hash-table

• 新建空哈希表：调用 make-hash-table。
  (define ht (make-hash-table))
• 指定哈希函数和比较函数（可选）：
  多数实现默认使用 equal? 比较键，如需用 eq? 或 string=?，可显式指定。

插入与更新

• 设置键值对：调用 hash-table-set!。
  (hash-table-set! ht 'name "Alice") 将键 'name 映射到 "Alice"。
• 若键不存在才设置：使用 hash-table-put!（部分实现）或先检查再设置。

查询值

• 获取键对应的值：调用 hash-table-ref。
  (hash-table-ref ht 'name) 返回 "Alice"。
• 安全查询（避免错误）：使用 hash-table-ref/default。
  (hash-table-ref/default ht 'age 0) 若 'age 不存在则返回 0。

检查与删除

• 判断键是否存在：调用 hash-table-exists?。
  (hash-table-exists? ht 'name) 返回 #t 或 #f。
• 删除键值对：调用 hash-table-delete!。
  (hash-table-delete! ht 'name)

遍历与转换

• 获取所有键：调用 hash-table-keys。
• 获取所有值：调用 hash-table-values。
• 转换为 alist（关联列表）：调用 hash-table->alist。
  返回形如 ((key1 . val1) (key2 . val2)) 的列表。

下表对比三种数据结构的关键特性：

四、如何选择合适的数据结构

优先使用 list 的情况：

• 数据量小且主要进行顺序遍历（如递归处理）。
• 需要频繁在头部添加或移除元素。
• 编写函数式风格代码，避免副作用。

优先使用 vector 的情况：

• 已知数据长度且需要频繁通过索引访问。
• 性能敏感，要求 O(1) 随机读写。
• 存储同类型数值（如矩阵、坐标）。

优先使用 hash-table 的情况：

• 需要通过非整数键（如字符串、符号）快速查找值。
• 实现配置表、缓存、计数器等映射逻辑。
• 数据无固定顺序，关注键的存在性与对应值。

转换技巧：

• 从 list 转 vector：(list->vector '(1 2 3))
• 从 vector 转 list：(vector->list #(1 2 3))
• 从 alist（关联列表）构建 hash-table：

  (define alist '((name . "Bob") (age . 30)))
  (define ht (make-hash-table))
  (for-each (lambda (pair)
              (hash-table-set! ht (car pair) (cdr pair)))
            alist)

避免常见错误：

• 不要对字面量 vector 或 list 使用 set! 修改：
  #(1 2 3) 是常量，尝试 (vector-set! #(1 2 3) 0 9) 可能导致错误或未定义行为。
• 不要混淆 eq?、eqv?、equal? 在 hash-table 中的行为：
  默认使用 equal?，若用数字或字符串作键通常没问题；若用自定义对象，需确保比较函数匹配。
• list 的 length 操作是 O(n)：
  在循环中反复调用 (length lst) 会导致性能下降，应提前计算或改用 vector。

根据数据访问模式和性能需求选择合适结构，能让程序更简洁高效。