算法与理论计算机2025arxiv.org
Tiny Pointers：极小指针数据结构
Tiny Pointers
专业 · 约 90 分钟读完前置知识：数据结构、算法复杂度分析、概率论基础
导读
这篇论文提出“Tiny Pointers（微小指针）”这一数据结构原语：指针本身可以比传统指针小得多，因为解引用时需要结合原始 key 一起使用，两个不同 key 甚至可以共享同一个指针值。论文证明了这种结构在空间复杂度上优于传统方案，并探讨了它与现有数据结构结合的应用。
HN 关注点：是因为这是一种有趣的理论原语，讨论焦点集中在它与开放寻址哈希表、Python 紧凑字典等已有实现的相似性，以及实际应用价值是否明确。
HN 评论精选
这几条评论里：质疑 2 补充 1
质疑解释了 Tiny Pointers 的工作原理，类似开放寻址哈希表，但质疑其实际应用价值
我几年前研究过这个，觉得挺有意思。虽然叫“Tiny Pointers”，但我觉得它更接近开放寻址哈希表：你有一个 key，可以在哈希表中“分配”一个条目并得到一个“指针”，之后用原始 key 加指针一起确定条目的索引。分配也有小概率失败（类似哈希冲突）。这里的“技巧”在于两个不同的 key 可以拥有完全相同的指针（因为解引用总是要配合 key），因此更紧凑。不过我一直在想好的使用场景——论文的例子都是与现有数据结构结合、展示空间复杂度更小，但实际中是否可行并不清楚。
judofyr查看英文原文
I looked a bit into this a few years back and found it quite interesting. Despite them calling them "Tiny Pointers" I would say it's closer to a open addressing hash map. You have a specific key, and then you can "allocate" an entry in the hash map. This gives you back a "pointer". You can then later use the original key and the pointer together to determine the index of the entry. There's also a slight chance that the allocation will fail (similar to a hash collision in a hash map). The "trick" here is that two different keys can end up having the exact same pointer (because we're always dereferencing with the key). This makes them more compact. I was struggling a bit to come up with good use cases for it. Their examples are all around combining them with existing data structures and they show that the space complexity is smaller, but it wasn't completely clear to me how feasible this would actually be in practice.
补充指出 Python 3.6 的紧凑字典早已用小索引实现类似思路
Python 的紧凑字典实现十年前不就做了这件事吗？“dict 类型现在使用基于 Raymond Hettinger 提案、最早由 PyPy 实现的‘紧凑’表示，相比 Python 3.5 内存占用减少 20% 到 25%。”小字典的索引可以小到一个字节，大字典两个字节，超大字典才用完整指针宽度。“Tiny pointers”就对应概念验证代码里的 _make_index 方法，这套逻辑至今仍存在于 CPython 中。
mont_tag查看英文原文
Didn't Python's compact dictionary implementation do this a decade ago? "The dict type now uses a “compact” representation based on a proposal by Raymond Hettinger which was first implemented by PyPy. The memory usage of the new dict() is between 20% and 25% smaller compared to Python 3.5." -- https://docs.python.org/3.6/whatsnew/3.6.html#whatsnew36-compactdict "Note, the sizeof(index) can be as small as a single byte for small dicts, two bytes for bigger dicts and up to sizeof(Py_ssize_t) for huge dict." -- https://mail.python.org/pipermail/python-dev/2012-December/123028.html The "tiny pointers" are in the _make_index method in the proof of concept code. -- https://code.activestate.com/recipes/578375-proof-of-concept-for-a-more-space-efficient-faster/ @staticmethod def _make_index(n): 'New sequence of indices using the smallest possible datatype' if n <= 2**7: return array.array('b', [FREE]) * n # signed char if n <= 2**15: return array.array('h', [FREE]) * n # signed short if n <= 2**31: return array.array('l', [FREE]) * n # signed long return [FREE] * n The logic is still present today in CPython. -- https://raw.githubusercontent.com/python/cpython/3e222e3a15959690a41847a1177ac424427815e5/Objects/dictobject.c dk_indices is actual hashtable. It holds index in entries, or DKIX_EMPTY(-1) or DKIX_DUMMY(-2). Size of indices is dk_size. Type of each index in indices varies with dk_size: * int8 for dk_size <= 128 * int16 for 256 <= dk_size <= 2**15 * int32 for 2**16 <= dk_size <= 2**31 * int64 for 2**32 <= dk_size
质疑质疑论文是否经过同行评审
这篇有同行评审版本吗，还是 Hacker News 只发未经同行评审的工作？
kittikitti查看英文原文
Is there a peer reviewed version of this or does Hacker News exclusively post non peer reviewed works?
历次讨论
- 2025Hacker News 讨论帖163 分 · 35 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选通信的数学理论
A Mathematical Theory of Communication
是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。
算法与理论计算机2020 · 495 分 · 91 评进阶 · 约 120 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。
算法与理论计算机2014 · 327 分 · 57 评 · 引用 4进阶 · 约 25 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选