Data structure

概述

参考：

• Wiki, Data structure

Data structure(数据结构) 在计算机科学中，是一种数据组织和存储格式，通常为了高效访问数据而选择。更准确地说，数据结构是数据值的集合、它们之间的关系以及可以应用于数据的函数或操作 ，i.e. 它是一种关于数据的代数结构 。

线性结构

非线性结构

https://claude.ai/chat/8460f68d-5e65-4a16-88ee-c642e53b618b

map 和 数组 哪个取数更快？时间复杂度更低？

14:14

Map vs 数组 取数速度对比

结论

取数速度：Map 更快（在大多数场景下）

细节说明

数组按索引取数：O(1)

go

arr[0]  // 直接内存寻址，极快

如果你知道下标，数组是最快的，甚至比 Map 快，因为没有哈希计算开销。

数组按 key 查找：O(n)

go

// 必须遍历
for _, v := range arr {
    if v.id == targetID { ... }
}

Map 按 key 取数：O(1) 均摊

go

m[key]  // 哈希计算后直接定位

哈希冲突严重时最坏 O(n)，但实际中几乎不会发生。

怎么选？

• 已知下标 → 用数组，O(1) 且无哈希开销，内存局部性更好
• 按 key 查找 → 用 Map，O(1) vs 数组的 O(n)
• 顺序遍历 → 用数组，缓存友好，实际性能更好
• 频繁增删 → 用 Map，数组移动元素是 O(n)

一句话总结

按 key 查找：Map 赢；按下标访问：数组赢。 大多数"取数"场景指的是 key 查找，所以通常说 Map 更快。

这俩的底层数据结构是 hash 还是 线性表？我这问题合理吗？

14:18

问题合理，但不够精确

“hash 还是线性表” 这个二选一本身没问题，但两者并不互斥——hash 表的底层通常就是用数组（线性表）实现的。

直接回答

Map 的底层到底是什么？

Map 本质是 哈希表，而哈希表的核心是：

key → hash函数 → 索引 → 数组[索引]

所以 Map 的底层还是数组，只是多了一层哈希映射。

冲突处理方式一般两种：

• 链地址法：数组每个槽挂一个链表（Go、Java HashMap）
• 开放寻址法：冲突了就找下一个空槽（Python dict、Go map 部分实现）

问题哪里不够精确？

你问的是"hash 还是 线性表"，暗示两者是对立的。
实际上更准确的说法是：

数组是线性表；Map 是哈希表，哈希表是建立在线性表之上的高级结构。

所以问"底层数据结构是什么"是合理的，但选项改成 “线性表 还是 哈希表” 会更准确。

那跟线性表对应的概念是什么，有多少个

14:18

跟线性表对应的概念

线性表的对立面是非线性结构。

数据结构按逻辑结构分为两大类：

数据结构
├── 线性结构        → 元素之间是一对一关系
│   ├── 数组
│   ├── 链表
│   ├── 栈
│   └── 队列
│
└── 非线性结构      → 元素之间是一对多 / 多对多关系
    ├── 树           （一对多）
    │   ├── 二叉树
    │   ├── B树
    │   └── 堆 ...
    └── 图           （多对多）

一句话总结

跟线性表对应的概念就是非线性结构，细分下来主要是树和图两大类。

哈希表比较特殊，它是一种数据结构的实现方式，底层用数组（线性），但从逻辑上看不属于上面任何一类，算是独立的一种——所以有时单独列出来，不强行归类。