字符串是只读字节
Go 字符串是一段不能就地修改的字节序列,len 得到的是字节数,不是看到的字符个数。
示例:书中的 "Go语言" 看起来像 4 个字,实际是 2 个 ASCII 字节加上 2 个各占 3 字节的汉字,len 为 8。字符串适合稳定共享;要修改或按字符遍历,必须按 UTF-8 码点(rune)处理,不能按字节切开汉字。
主题对照
比较字符串、数组、切片、哈希表等内置结构的内存布局、扩容与复制代价。
Go 字符串是一段不能就地修改的字节序列,len 得到的是字节数,不是看到的字符个数。
示例:书中的 "Go语言" 看起来像 4 个字,实际是 2 个 ASCII 字节加上 2 个各占 3 字节的汉字,len 为 8。字符串适合稳定共享;要修改或按字符遍历,必须按 UTF-8 码点(rune)处理,不能按字节切开汉字。
rune 是 Unicode 码点,解决“一个字符不等于一个字节”的问题。range 遍历 UTF-8 字符串时得到字节偏移量和 rune 值,不是逐字节索引;组合字符仍可能由多个码点构成,处理用户可见字符还需更高层的文本规则。
字符串与 []byte 的互转常常意味着复制和分配,因为前者只读、后者可变。性能敏感路径要把转换次数纳入设计;这和 [[逃逸分析原则]] 一样,都是减少隐藏分配的入口。
Go 数组包含固定长度和元素类型,赋值或传参会复制整个数组。它的值语义让别名关系更简单,但大数组复制成本高;需要共享和变长时应转向切片。
切片在运行时是三个字段:指向底层数组的指针、当前元素个数(长度)和还能容下多少元素(容量)。把切片赋给另一个变量或当作参数传递,只复制这三个字段,元素仍在同一块数组里。
示例:a := []int{1, 2} 之后写 b := a,再执行 b[0] = 9,a[0] 也会变成 9。要得到互不影响的副本,必须另行分配并复制元素。
append 在容量够时继续使用原来的底层数组,容量不够时申请新数组并复制旧元素。书中因此把追加写成 a = append(a, x),更新后的切片在返回值里。
扩容之后,新切片不一定换掉地址。所以不能认定追加后还和旧切片共用数组,也不能认定每次都会换成新数组;要看的是这次容量够不够。
从大切片截取小片段,新切片的指针仍指向原来的底层数组。书中 bar 截取 foo 中间的元素后再改 bar,foo 里对应的元素也会变。小片段因此可能把整块大数组留住。要得到互不影响的数据,用 copy 复制到新的数组。
哈希表用哈希值把键映射到存储位置,遇到碰撞还要继续定位并比较具体键。哈希质量、装载程度和碰撞处理方式共同影响访问成本;平均 O(1) 不是每次访问的保证。Go map 的具体分组与扩容结构会随运行时版本变化。
map 的 key 必须支持相等比较,因为哈希命中后还要确认具体键是否相同。切片、函数等不可比较类型不能做 key;这不是语法限制,而是哈希表正确性的前提。
书中旧版 Go map 扩容时先保留旧桶,后续写入逐步迁移相关桶,避免单次搬完整张表。它体现以多次操作分摊迁移成本的设计取舍。Go 1.24 起内置 map 改用 Swiss Table,不能把这套旧桶迁移机制当作现行实现。
JS 对象是可变键控集合,属性名可以是任意字符串,属性值可以是任意值包括 undefined(并非现代新增能力,而是原书”属性值不能是undefined”表述本身不准确)。读取得 undefined 因此不能区分属性不存在和值就是undefined,判断存在性应用 Object.hasOwn(obj, key) 而非比较取值。发散:把对象当散列表理解,比套用类模型更接近本性。
从语言行为看,JavaScript 数组是特殊对象:整数索引参与属性访问,原型链上有数组方法,并带有随索引变化的 length;元素可混放不同类型。原书把数组与线性内存数组对比,这能解释稀疏下标和对象属性,但不能据此断言现代引擎一律采用某种存储布局或必然更慢。发散:分析语义与测量性能时应分别取证。
数组 length 不是已存在元素的数量。给较大整数索引赋值会把它提高到该索引加一,但中间可有空洞;也能直接把 length 设大而不新增元素,设小则删除超出范围的元素。数组索引与 length 都有规格上界,不能照搬原书“没有上界”的说法。发散:处理数组前先辨明它是密集序列还是稀疏结构。
for...in 遍历数组的键,会看到额外的可枚举属性,也可能看到继承属性;稀疏数组的空洞不会作为自有索引出现。现行普通数组的索引键有确定的枚举顺序,原书“不保证顺序”不可照搬。需按位置处理时用下标循环;要值时可用 for...of,但空洞会读成 undefined。关联:[[反射需防原型]]。
数组默认不预置值,访问未赋值元素得 undefined;算法假设每个元素有初始值时须显式创建填充数组。多维数组同理:JS 没有原生多维数组,只能用”数组的数组”模拟,须逐层显式创建每一维——让每个元素共享同一子数组引用是错误做法,会导致改一行影响所有行。发散:嵌套结构最好用工厂函数按需生成独立实例,避免共享默认子对象引发联动 bug。
Java对象即使没有字段也有对象头、引用和对齐等开销,集合还会为桶、节点和包装对象付费。发散:当对象数量巨大时,面向对象的表达力会转化为真实内存账单。
对象占用还取决于运行时、对象头、引用宽度与对齐填充。书中的字节表是指定模型下的估算;JOL可以观察具体JVM的对象布局,不能把示例的12字节对象头当作所有环境常量。参见OpenJDK JOL。
数组、ArrayList、LinkedList、HashSet的单元素成本差异很大;HashSet用更多内存换常数级查找、去重和删除。发散:选集合时同时问两个问题:需要哪些操作,愿意为这些操作付多少空间。
散列表通常以额外槽位、节点或装箱对象换取期望常数时间访问,这需要相应散列与负载假设。原书以Trove的基本类型专用容器减少装箱,以SparseArray的平行键值数组和二分查找换取更紧凑表示;两者优化对象不同,不能仅凭元素数比较集合成本。
ArrayBuffer只持有一段固定长度的原始字节,既不能改变大小,也不能直接读写;DataView和类型数组负责把这些字节解释为特定格式并读写。存储与解释分离后,同一块数据可以被多种视图共享,例如subarray只共享原缓冲区,slice才会复制数据。文件解析、GPU上传都建立在这一层之上,见[[DataView管偏移]]。
TypedArrayList用固定类型的数组模拟可扩容的动态数组,目的不是补齐普通数组的全部功能,而是重用一大块连续内存,减少频繁生成顶点数据时的重新分配;清空后可以反复填充。删除操作效率极低、渲染场景也用不到,所以干脆不实现。容器只为真实的使用模式提供能力。
动态类型数组扩容时,内部存储已换成一块新的缓冲区。TypedArrayList在成员中放一个capacityChangedCallback回调,扩容时通知外部:“我扩容了,你要做什么?”需要同步的调用方(如统计、调试或关联的GPU缓冲)可以在这一刻响应,而不必侵入push的核心逻辑。
书中的双向循环链表用一个头节点作为哨兵:初始化时它的next和prev都指向自己;有数据后,头节点的前驱指向尾节点、尾节点的后继指向头节点,首尾相连成环。这样空表、首节点、尾节点的插入和删除都走同一套指针改写规则,不必写特殊分支。很多容器代码的复杂度来自边界分支,哨兵用结构消除了它们。
给树节点添加子节点时,若把它的祖先挂到它下面,树就变成了环,遍历会陷入死循环甚至让程序崩溃。所以添加前必须检查:要加入的节点是否已是当前节点的祖先,书中为此专门实现了判断方法。层级模型要在写入关系时就守住不变量,等遍历、删除或序列化时才发现环,修复代价高得多。
树的遍历可以按广度或深度、先根或后根、从左到右或从右到左组合出多种顺序。书中发现:先根左右遍历的逆序就是后根右左遍历,反之亦然;所以只需实现先根枚举器,后根枚举器包装它倒序输出即可。渲染、命中检测、销毁、序列化需要的顺序各不相同,不能把“遍历树”当成唯一算法。
树的非递归遍历要自己管理栈或队列、方向和先后顺序,书中把这些都藏进枚举器:树枚举器实现第2章定义的通用枚举器接口,调用方只按统一的迭代方式逐个拿到节点。这与[[迭代器暴露解析]]一致:复杂的游标逻辑留在内部,外部按序消费结果。
多叉树除了“父节点加儿子列表”,还可以用“第一个儿子加下一个兄弟”两个指针表示,把任意多叉树变成类似二叉的链式结构。书中主体用前一种存储,但模拟了后一种的查询属性,并演示其遍历:先找儿子,没有就找兄弟,再没有就沿祖先回溯找其右兄弟,直到根。换一种表示,遍历成本和实现复杂度随之改变。
Go 的字符串字面量有反引号包围的原始形式和双引号包围的解释形式。前者保留文本中的换行与反斜杠,后者解析 \ 转义且不能直接跨行;编译器分别走 rawString 和 stdString 路径。写正则、路径或多行文本时,先选符合预期的字面量形式,避免把转义层数弄错。
字符串不可修改,所以多个变量通过 + 拼接时,运行时先算结果长度,再为新结果准备空间并复制内容;它不会把后一个字符串直接接到前一个的存储尾部。反复拼接可能不断复制已有内容。常量表达式可在编译期合并,不能据此推断变量拼接没有运行时成本。
Go 数组类型写作 [n]T,长度 n 与元素类型 T 都在编译期确定。字面量里的 [...]T{...} 让编译器根据元素数推断长度,但不会得到可扩容容器;不同长度的数组是不同类型。它解释了 [[数组是值]] 的固定形状,也为编译器检查常量下标提供了长度信息。
切片的 len 是当前可索引的元素数,cap 是从切片起点到其底层数组末尾可用的容量,始终有 len≤cap。截取切片会改变新切片的长度和容量,却仍可能与原切片共享数据。理解这两个边界,才能判断 append 是否可能触发扩容,也能解释为什么共享数据不代表两个切片的头部同步变化。
append 返回更新后的切片头部,调用方应把结果赋回变量,如 s = append(s, x)。容量足够时可能共用原数组,容量不足时可能换成新数组;两种情况下新长度都在返回的切片值中。只观察旧切片是否还能看到元素,无法替代接收返回值。
点击箭头逐层展开,点击卡片标题查看详情。路径上下文仅用于连接层级,不计入主题卡片数。
来源书籍
编程语言类
书籍类型:未标注
清单覆盖 6/9
80 张卡片
来源书籍
编程语言类
书籍类型:经典原理
清单覆盖 8/9
182 张卡片
来源书籍
编程语言类
书籍类型:未标注
类别清单尚未核对
106 张卡片
来源书籍
书籍类型:经典原理
125 张卡片
来源书籍
图形渲染引擎实战类
书籍类型:工程实践
清单覆盖 7/7
47 张卡片
来源书籍
图形渲染引擎实战类
书籍类型:工程实践
清单覆盖 5/5
46 张卡片
来源书籍
代码可读性与重构类
书籍类型:经典原理
清单覆盖 7/7
109 张卡片
来源书籍
源码分享类
书籍类型:工程实践
清单覆盖 8/8
242 张卡片
来源书籍
设计模式类
书籍类型:经典原理
清单覆盖 7/7
65 张卡片
来源书籍
系统架构类
书籍类型:工程实践
类别清单尚未核对
67 张卡片
主题索引
比较渐近复杂度、摊销分析、基准测试以及以抽象换空间、局部性等时间与空间效率的权衡。
主题索引
把算法、职责与对象间通信分配清楚:责任链、命令、解释器、迭代器、中介者、备忘录、观察者、状态、策略、模板方法、访问者。
主题索引
比较数据交换格式的简洁性、互通性与安全解析要求。
主题索引
比较分级分配、页/块管理与多级缓存降锁等分配器设计。
主题索引
比较扫描、时间槽与分层时钟轮的调度成本,及截止时间校验和周期任务重排的边界。
与 16 张主题卡片存在结构化链接;共享 1 个其他主题;来自相同书籍;属于相同分类
与 3 张主题卡片存在结构化链接
与 1 张主题卡片存在结构化链接;共享 1 个其他主题;来自相同书籍;属于相同分类
与 1 张主题卡片存在结构化链接;共享 1 个其他主题;来自相同书籍;属于相同分类
与 1 张主题卡片存在结构化链接;共享 1 个其他主题;来自相同书籍;属于相同分类
与 1 张主题卡片存在结构化链接;共享 1 个其他主题;来自相同书籍;属于相同分类