可双向扩展且索引保持稳定的动态Array实现方案咨询

• 支持首尾双向扩展的数组结构，扩展后原有索引完全保持不变
• 原有索引位置的元素不会受前后新增元素影响，例如索引3的对象始终固定在索引3，即使在索引-1等负索引位置新增元素也不受干扰
• 数组允许存在预留的空单元格，可后续填充内容

• 采用字符串键的Dictionary存储
  • 需要频繁进行字符串和数字索引的转换，性能损耗过高
• 基于偏移量（Offset）动态扩容数组
  • 频繁创建新数组带来的性能开销过大
  • 曾尝试通过优化扩容算法降低开销，比如每次扩容直接翻倍容量、或每次固定扩容25个单位而非逐单位扩容
• 拆分两个数组分别存储正索引和负索引内容
  • 处理索引0附近的元素时逻辑复杂度大幅提升

正在开发2D网格类游戏，玩家可自由扩展世界地图，放置新tile时需要频繁读取周边tile的数据，玩法是《Dorfromantik》和《Islanders》的结合类型。

核心采用分段式块存储结构，完全匹配你的需求：

• 核心逻辑：将整个索引空间按固定大小（建议取64/128个元素为一个块，优先选择2的幂次）拆分，用Dictionary存储块索引到块数组的映射，直接用整数做键，完全避免字符串和数字的转换损耗
• 索引计算规则：给定任意整数索引idx，仅需通过简单整数运算即可快速定位，正负索引通用：

块大小 = 64
块索引 = idx >> 6 // 等价于idx // 64
块内偏移 = idx & 63 // 等价于idx % 64

• 核心优势：
  1. 双向扩展完全不影响原有元素索引，新增元素时仅需要创建对应缺失的块，不需要移动或重建已有数据，扩容开销极低
  2. 天然支持空单元格，未创建的块和块内未赋值的位置都可以标记为空，预留填充空间
  3. 访问性能接近原生数组，整数运算开销可以忽略，完全适配频繁读取周边tile的场景
  4. 逻辑简单，不需要处理正负索引分治的复杂边界，负索引的计算规则和正索引完全一致

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