runtime/hashtable2.mm 作用与实现原理
objc4 runtime NXHashTable 集合结构 runtime/hashtable2.mm 作用与实现原理 这个文件实现了旧 NeXT/Objective-C runtime 暴露的 NXHashTable:一个可存放任意指针或整数数据的哈希集合。它不保存 key-value 对;需要映射关系时,runtime 另用 maptable.mm 的 NXMapTable。 一遍读懂 它用 callback 决定“怎么 hash、怎么判等、怎么释放”。 每个 bucket 是一条很短的冲突链。 bucket 中只有 1 个元素时直接存指针,避免额外分配。 元素数超过 bucket 数时扩容并重算位置。 删除会把 2 个元素的 bucket 收缩回单指针形态。 1. 它解决什么问题 NXHashTable 是 runtime 内部和兼容 API 使用的通用集合容器。调用者传入一组 NXHashTablePrototype,告诉表如何处理元素:hash(info, data) 计算哈希,isEqual(info, a, b) 判断相等,free(info, data) 在销毁或 reset 时释放元素。这样同一套表结构可以存指针、字符串,或“结构体首字段作为 key”的对象。 **关键不变量:**如果两个元素被 isEqual 判为相等,它们的 hash 必须一致;而且参与 hash 的内容不能在入表后变化。否则扩容重排后会找不到元素。 2. 数据结构:一层数组 + 小冲突链 NXHashTable保存 prototype、元素总数、bucket 数组和可透传给 callback 的 info。 ...