Tcl：列表转字典的内部开销及dict get性能差异探究

Donal Fellows曾针对我的Tcl字典相关问题给出过全面解答，但我仍不清楚：当用dict get访问列表元素时，元素本身是字典和是列表（被当作字典使用）的内部开销有何差异？

我做了两种场景的测试：

测试代码 #

# dict作为列表元素
set l1 [list first second [dict create one 111 two 222 three 333]]
puts [tcl::unsupported::representation [lindex $l1 2]]
puts [dict get [lindex $l1 2] two]

# list作为列表元素，但当作字典使用
set l2 [list first second [list one 111 two 222 three 333]]
puts [tcl::unsupported::representation [lindex $l2 2]]
puts [dict get [lindex $l2 2] two]

输出结果 #

value is a dict with a refcount of 2, object pointer at 0x556ef4f61980, internal representation 0x556ef4f56cc0:(nil), no string representation
222
value is a list with a refcount of 2, object pointer at 0x556ef4f61740, internal representation 0x556ef4f7c580:(nil), no string representation
222

从结果能看到，l1索引2的元素是字典类型，l2对应元素是列表类型。针对核心疑问，具体说明如下：

列表转字典的内部开销 #

Tcl的对象采用多表示设计，当对列表调用dict get时，会触发列表到字典的内部表示转换：

• 小型键值对列表（如示例中的3组）：开销几乎可忽略，仅需遍历列表构建一个小型哈希表，内存分配和哈希冲突处理的成本极低。
• 大型键值对列表（成百上千组）：开销会显著上升，需要分配更多内存空间、处理哈希冲突，完成完整的哈希表构建过程，时间复杂度为O(n)（n为键值对数量）。

dict get的运行时差异 #

• 元素本身是字典：dict get直接复用已有的哈希表结构，键查找的平均时间复杂度为O(1)，效率极高。
• 元素是列表：第一次调用dict get时会触发转换，生成字典的内部表示并缓存在对象中；后续再次调用dict get时，会直接使用缓存的字典表示，无需重复转换。但如果之后该对象被修改为列表（比如执行lappend操作），缓存的字典表示会被失效，下次调用dict get需要重新转换。

内容的提问来源于stack exchange，提问作者Ralf