跳跃表：实现高性能类有序映射std::map（Lua）-171主机测评

跳跃表：实现高性能类有序映射std::map（Lua）

引言

在软件开发中，我们经常需要一种能够根据键快速查找、插入、删除，并且能够按顺序遍历键值对的数据结构。传统的实现方案包括平衡树（如红黑树、AVL树）和哈希表，但它们各有优缺点：哈希表虽然查找快，但无法保持顺序；平衡树可以保持顺序，但实现复杂，且对并发修改的支持不够友好。跳跃表（Skip List）是一种可以替代平衡树的概率性数据结构，它通过多层索引实现快速查找，同时实现简单、易于理解。

一、跳跃表原理：用概率换取简单

1.1 从有序链表说起

考虑一个有序的单链表，查找一个元素需要从头遍历，时间复杂度为O(n)。为了提高查找效率，我们可以为链表建立多级索引：每两个节点提取一个作为上层索引的节点，这样查找时可以先从上层快速跳过大量节点，然后再逐层细化。这就是跳跃表的基本思想。

下图展示了一个包含4层索引的跳跃表结构。底层（L1）是完整的有序链表，包含所有节点；L2、L3、L4是稀疏的索引层，每个节点随机出现在若干层中。

#mermaid-svg-xpWvyEdbOFrw5QNT{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-xpWvyEdbOFrw5QNT .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-xpWvyEdbOFrw5QNT .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-xpWvyEdbOFrw5QNT .error-icon{fill:#552222;}#mermaid-svg-xpWvyEdbOFrw5QNT .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-xpWvyEdbOFrw5QNT .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-xpWvyEdbOFrw5QNT .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-xpWvyEdbOFrw5QNT .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-xpWvyEdbOFrw5QNT .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-xpWvyEdbOFrw5QNT .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-xpWvyEdbOFrw5QNT .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-xpWvyEdbOFrw5QNT .marker{fill:#333333;stroke:#333333;}#mermaid-svg-xpWvyEdbOFrw5QNT .marker.cross{stroke:#333333;}#mermaid-svg-xpWvyEdbOFrw5QNT svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-xpWvyEdbOFrw5QNT p{margin:0;}#mermaid-svg-xpWvyEdbOFrw5QNT .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-xpWvyEdbOFrw5QNT .cluster-label text{fill:#333;}#mermaid-svg-xpWvyEdbOFrw5QNT .cluster-label span{color:#333;}#mermaid-svg-xpWvyEdbOFrw5QNT .cluster-label span p{background-color:transparent;}#mermaid-svg-xpWvyEdbOFrw5QNT .label text,#mermaid-svg-xpWvyEdbOFrw5QNT span{fill:#333;color:#333;}#mermaid-svg-xpWvyEdbOFrw5QNT .node rect,#mermaid-svg-xpWvyEdbOFrw5QNT .node circle,#mermaid-svg-xpWvyEdbOFrw5QNT .node ellipse,#mermaid-svg-xpWvyEdbOFrw5QNT .node polygon,#mermaid-svg-xpWvyEdbOFrw5QNT .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-xpWvyEdbOFrw5QNT .rough-node .label text,#mermaid-svg-xpWvyEdbOFrw5QNT .node .label text,#mermaid-svg-xpWvyEdbOFrw5QNT .image-shape .label,#mermaid-svg-xpWvyEdbOFrw5QNT .icon-shape .label{text-anchor:middle;}#mermaid-svg-xpWvyEdbOFrw5QNT .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-xpWvyEdbOFrw5QNT .rough-node .label,#mermaid-svg-xpWvyEdbOFrw5QNT .node .label,#mermaid-svg-xpWvyEdbOFrw5QNT .image-shape .label,#mermaid-svg-xpWvyEdbOFrw5QNT .icon-shape .label{text-align:center;}#mermaid-svg-xpWvyEdbOFrw5QNT .node.clickable{cursor:pointer;}#mermaid-svg-xpWvyEdbOFrw5QNT .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-xpWvyEdbOFrw5QNT .arrowheadPath{fill:#333333;}#mermaid-svg-xpWvyEdbOFrw5QNT .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-xpWvyEdbOFrw5QNT .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-xpWvyEdbOFrw5QNT .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-xpWvyEdbOFrw5QNT .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-xpWvyEdbOFrw5QNT .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-xpWvyEdbOFrw5QNT .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-xpWvyEdbOFrw5QNT .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-xpWvyEdbOFrw5QNT .cluster text{fill:#333;}#mermaid-svg-xpWvyEdbOFrw5QNT .cluster span{color:#333;}#mermaid-svg-xpWvyEdbOFrw5QNT div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-xpWvyEdbOFrw5QNT .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-xpWvyEdbOFrw5QNT rect.text{fill:none;stroke-width:0;}#mermaid-svg-xpWvyEdbOFrw5QNT .icon-shape,#mermaid-svg-xpWvyEdbOFrw5QNT .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-xpWvyEdbOFrw5QNT .icon-shape p,#mermaid-svg-xpWvyEdbOFrw5QNT .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-xpWvyEdbOFrw5QNT .icon-shape rect,#mermaid-svg-xpWvyEdbOFrw5QNT .image-shape rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-xpWvyEdbOFrw5QNT .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-xpWvyEdbOFrw5QNT .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-xpWvyEdbOFrw5QNT :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

head

nil

head

nil

head

nil

head

nil

图1：跳跃表多层索引结构（节点中的数字表示键值）

然而，严格的“每两个节点建一层”会导致插入删除时维护索引成本过高。跳跃表的巧妙之处在于：它采用概率平衡，每个节点随机决定自己的层数，使得索引结构在统计意义上保持平衡，同时大大简化了实现。

1.2 层级与概率

在跳跃表中，每个节点有一个“层数”（level），表示它出现在多少层索引中。最底层（第1层）是一个完整的有序链表，包含所有节点。上层是稀疏的索引层。节点的层数通过一个随机函数生成，通常以概率p（经典值为0.5或0.25）决定是否继续增加一层，直到达到最大层数限制。

这样，平均每个节点出现在1/(1-p)层中，且高层节点数量呈指数减少。这种随机化策略保证了查找、插入、删除的期望时间复杂度为O(log n)，与平衡树相当。

1.3 查找过程

查找从最高层开始，在该层中向右移动直到遇到第一个键大于目标键的节点，然后下降到下一层继续，如此重复，直到最底层。在底层，目标节点要么正好是当前节点的下一个，要么不存在。

下图演示了查找键值为9的节点的路径（红色箭头）。从L4的head开始，向右到节点3，发现下一个节点是nil（或大于9），于是下降到L3；在L3从节点3向右到节点6，下一个节点是nil，下降到L2；在L2从节点6向右到节点9，找到目标。

#mermaid-svg-hbneHjsIk24ibiTF{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-hbneHjsIk24ibiTF .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-hbneHjsIk24ibiTF .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-hbneHjsIk24ibiTF .error-icon{fill:#552222;}#mermaid-svg-hbneHjsIk24ibiTF .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-hbneHjsIk24ibiTF .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-hbneHjsIk24ibiTF .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-hbneHjsIk24ibiTF .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-hbneHjsIk24ibiTF .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-hbneHjsIk24ibiTF .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-hbneHjsIk24ibiTF .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-hbneHjsIk24ibiTF .marker{fill:#333333;stroke:#333333;}#mermaid-svg-hbneHjsIk24ibiTF .marker.cross{stroke:#333333;}#mermaid-svg-hbneHjsIk24ibiTF svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-hbneHjsIk24ibiTF p{margin:0;}#mermaid-svg-hbneHjsIk24ibiTF .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-hbneHjsIk24ibiTF .cluster-label text{fill:#333;}#mermaid-svg-hbneHjsIk24ibiTF .cluster-label span{color:#333;}#mermaid-svg-hbneHjsIk24ibiTF .cluster-label span p{background-color:transparent;}#mermaid-svg-hbneHjsIk24ibiTF .label text,#mermaid-svg-hbneHjsIk24ibiTF span{fill:#333;color:#333;}#mermaid-svg-hbneHjsIk24ibiTF .node rect,#mermaid-svg-hbneHjsIk24ibiTF .node circle,#mermaid-svg-hbneHjsIk24ibiTF .node ellipse,#mermaid-svg-hbneHjsIk24ibiTF .node polygon,#mermaid-svg-hbneHjsIk24ibiTF .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-hbneHjsIk24ibiTF .rough-node .label text,#mermaid-svg-hbneHjsIk24ibiTF .node .label text,#mermaid-svg-hbneHjsIk24ibiTF .image-shape .label,#mermaid-svg-hbneHjsIk24ibiTF .icon-shape .label{text-anchor:middle;}#mermaid-svg-hbneHjsIk24ibiTF .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-hbneHjsIk24ibiTF .rough-node .label,#mermaid-svg-hbneHjsIk24ibiTF .node .label,#mermaid-svg-hbneHjsIk24ibiTF .image-shape .label,#mermaid-svg-hbneHjsIk24ibiTF .icon-shape .label{text-align:center;}#mermaid-svg-hbneHjsIk24ibiTF .node.clickable{cursor:pointer;}#mermaid-svg-hbneHjsIk24ibiTF .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-hbneHjsIk24ibiTF .arrowheadPath{fill:#333333;}#mermaid-svg-hbneHjsIk24ibiTF .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-hbneHjsIk24ibiTF .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-hbneHjsIk24ibiTF .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-hbneHjsIk24ibiTF .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-hbneHjsIk24ibiTF .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-hbneHjsIk24ibiTF .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-hbneHjsIk24ibiTF .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-hbneHjsIk24ibiTF .cluster text{fill:#333;}#mermaid-svg-hbneHjsIk24ibiTF .cluster span{color:#333;}#mermaid-svg-hbneHjsIk24ibiTF div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-hbneHjsIk24ibiTF .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-hbneHjsIk24ibiTF rect.text{fill:none;stroke-width:0;}#mermaid-svg-hbneHjsIk24ibiTF .icon-shape,#mermaid-svg-hbneHjsIk24ibiTF .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-hbneHjsIk24ibiTF .icon-shape p,#mermaid-svg-hbneHjsIk24ibiTF .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-hbneHjsIk24ibiTF .icon-shape rect,#mermaid-svg-hbneHjsIk24ibiTF .image-shape rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-hbneHjsIk24ibiTF .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-hbneHjsIk24ibiTF .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-hbneHjsIk24ibiTF :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

head

nil

head

nil

head

nil

head

nil

图2：查找键值9的路径（红色箭头）

1.4 插入与删除

插入时，先执行查找，记录每一层中最后一个小于插入键的节点（即前驱节点）。然后随机生成新节点的层数，将其插入到每一层的前驱之后。删除类似，先找到节点，然后从每一层中将其移除。

由于层数是随机的，插入和删除不需要复杂的旋转操作，只需要修改指针，因此实现非常简单。

下面是用mermaid绘制的插入过程示意图。假设要在跳跃表中插入键值为7的节点，随机生成的层数为2（即出现在L1和L2）。首先找到各层的前驱节点（L2的前驱是6，L1的前驱也是6），然后修改指针，将新节点插入。

#mermaid-svg-dCQnL1MXjvhE67JN{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-dCQnL1MXjvhE67JN .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-dCQnL1MXjvhE67JN .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-dCQnL1MXjvhE67JN .error-icon{fill:#552222;}#mermaid-svg-dCQnL1MXjvhE67JN .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-dCQnL1MXjvhE67JN .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-dCQnL1MXjvhE67JN .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-dCQnL1MXjvhE67JN .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-dCQnL1MXjvhE67JN .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-dCQnL1MXjvhE67JN .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-dCQnL1MXjvhE67JN .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-dCQnL1MXjvhE67JN .marker{fill:#333333;stroke:#333333;}#mermaid-svg-dCQnL1MXjvhE67JN .marker.cross{stroke:#333333;}#mermaid-svg-dCQnL1MXjvhE67JN svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-dCQnL1MXjvhE67JN p{margin:0;}#mermaid-svg-dCQnL1MXjvhE67JN .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-dCQnL1MXjvhE67JN .cluster-label text{fill:#333;}#mermaid-svg-dCQnL1MXjvhE67JN .cluster-label span{color:#333;}#mermaid-svg-dCQnL1MXjvhE67JN .cluster-label span p{background-color:transparent;}#mermaid-svg-dCQnL1MXjvhE67JN .label text,#mermaid-svg-dCQnL1MXjvhE67JN span{fill:#333;color:#333;}#mermaid-svg-dCQnL1MXjvhE67JN .node rect,#mermaid-svg-dCQnL1MXjvhE67JN .node circle,#mermaid-svg-dCQnL1MXjvhE67JN .node ellipse,#mermaid-svg-dCQnL1MXjvhE67JN .node polygon,#mermaid-svg-dCQnL1MXjvhE67JN .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-dCQnL1MXjvhE67JN .rough-node .label text,#mermaid-svg-dCQnL1MXjvhE67JN .node .label text,#mermaid-svg-dCQnL1MXjvhE67JN .image-shape .label,#mermaid-svg-dCQnL1MXjvhE67JN .icon-shape .label{text-anchor:middle;}#mermaid-svg-dCQnL1MXjvhE67JN .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-dCQnL1MXjvhE67JN .rough-node .label,#mermaid-svg-dCQnL1MXjvhE67JN .node .label,#mermaid-svg-dCQnL1MXjvhE67JN .image-shape .label,#mermaid-svg-dCQnL1MXjvhE67JN .icon-shape .label{text-align:center;}#mermaid-svg-dCQnL1MXjvhE67JN .node.clickable{cursor:pointer;}#mermaid-svg-dCQnL1MXjvhE67JN .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-dCQnL1MXjvhE67JN .arrowheadPath{fill:#333333;}#mermaid-svg-dCQnL1MXjvhE67JN .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-dCQnL1MXjvhE67JN .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-dCQnL1MXjvhE67JN .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-dCQnL1MXjvhE67JN .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-dCQnL1MXjvhE67JN .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-dCQnL1MXjvhE67JN .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-dCQnL1MXjvhE67JN .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-dCQnL1MXjvhE67JN .cluster text{fill:#333;}#mermaid-svg-dCQnL1MXjvhE67JN .cluster span{color:#333;}#mermaid-svg-dCQnL1MXjvhE67JN div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-dCQnL1MXjvhE67JN .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-dCQnL1MXjvhE67JN rect.text{fill:none;stroke-width:0;}#mermaid-svg-dCQnL1MXjvhE67JN .icon-shape,#mermaid-svg-dCQnL1MXjvhE67JN .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-dCQnL1MXjvhE67JN .icon-shape p,#mermaid-svg-dCQnL1MXjvhE67JN .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-dCQnL1MXjvhE67JN .icon-shape rect,#mermaid-svg-dCQnL1MXjvhE67JN .image-shape rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-dCQnL1MXjvhE67JN .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-dCQnL1MXjvhE67JN .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-dCQnL1MXjvhE67JN :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

插入后

nil

插入前

nil

图3：插入键值7（层数2）的前后对比

二、Lua实现的高性能有序映射

下面我们深入分析给定的Lua代码。该代码实现了一个功能完备、性能优异的OrderedMap，支持自定义比较器、安全比较、迭代器等功能。

2.1 模块结构与常量定义

local OrderedMap = {}
OrderedMap.__index = OrderedMap

— 局部化常用函数，提升性能
local random = math.random
local type = type
local tostring = tostring
local pcall = pcall
local setmetatable = setmetatable

— 最大层数（2^20 ≈ 1e6，设置为 32 足够支持千万级数据）
local MAX_LEVEL = 32
— 随机提升层数的概率（经典值 0.5）
local PROBABILITY = 0.5

这里将常用函数局部化是为了减少全局查找开销，提升性能。MAX_LEVEL设为32，理论上可支持多达2^32个节点，实际应用中足够。PROBABILITY采用0.5，这是经典值，可以保证索引层数的期望值为2。

2.2 节点定义

local function createNode(key, value, level)
return {
key = key,
value = value,
level = level,
next = {}
}
end

每个节点包含key、value、level（节点实际层数）和一个数组next，next[l]指向第l层的下一个节点。保存level可以在删除时只遍历该节点存在的层，提高效率。

2.3 随机层数生成

local function randomLevel()
local level = 1
while level < MAX_LEVEL and random() < PROBABILITY do
level = level + 1
end
return level
end

经典的几何分布随机层数生成器。平均层数为1/(1-PROBABILITY)=2，每个节点平均出现在2层，索引总节点数约为原链表节点数的两倍，空间开销可以接受。

2.4 安全比较器设计

跳跃表依赖于键之间的比较来确定顺序。用户可以提供自定义比较器，但比较器可能抛出错误或无法处理不同类型。为了鲁棒性，代码实现了一个安全比较器包装。

local function makeSafeComparator(userCmp)
local typeOrder = { number=1, string=2, boolean=3, table=4, func=5, thread=6, userdata=7 }
return function(a, b)
— 处理nil
if a == nil or b == nil then
return a == nil
end

local typeA, typeB = type(a), type(b)
if typeA ~= typeB then
return (typeOrder[typeA] or 8) < (typeOrder[typeB] or 8)
end

if typeA == "number" or typeA == "string" then
local ok, result = pcall(userCmp, a, b)
if ok then return result else return a < b end
else
local ok1, strA = pcall(tostring, a)
local ok2, strB = pcall(tostring, b)
if ok1 and ok2 then return strA < strB
else return typeA < typeB end
end
end
end

该安全比较器做了以下工作：

类型不同时，按预定义的类型顺序比较（数字 < 字符串 < 布尔 < 表 …）。
数字或字符串类型优先调用用户比较器，若出错则回退到默认 < 比较。
其他类型先尝试转为字符串比较，若失败则回退到类型名比较。

这种设计使得OrderedMap可以安全地处理任意类型的键，即使比较器有缺陷也不会导致崩溃，非常实用。

2.5 构造函数

function OrderedMap.new(cmp)
local baseCmp
if cmp == nil or cmp == "asc" or cmp == "<" then
baseCmp = function(a, b) return a < b end
elseif cmp == "desc" or cmp == ">" then
baseCmp = function(a, b) return a > b end
elseif type(cmp) == "function" then
baseCmp = cmp
else
error("比较器必须是函数、'asc'、'desc'、'<' 或 '>'")
end

local head = createNode(nil, nil, MAX_LEVEL)
local self = {
head = head,
_cmp = makeSafeComparator(baseCmp),
_size = 0,
_update = {}, — 预分配的update数组，避免频繁创建
}
return setmetatable(self, OrderedMap)
end

构造函数支持字符串形式的"asc"/"desc"或函数比较器，非常友好。注意head节点不存储数据，其层数为MAX_LEVEL，作为所有层的起始哨兵。self中预分配了一个_update表，用于查找时存储每层的前驱节点，避免每次查找都新建表，减少了内存分配开销。

2.6 核心查找方法：_findPredecessors

function OrderedMap:_findPredecessors(key)
local update = self._update
local current = self.head
local cmp = self._cmp

for level = MAX_LEVEL, 1, –1 do
while current.next[level] and cmp(current.next[level].key, key) do
current = current.next[level]
end
update[level] = current
end

local nextNode = current.next[1]
if nextNode and not cmp(nextNode.key, key) and not cmp(key, nextNode.key) then
return update, nextNode
end
return update, nil
end

该方法查找key的前驱节点，并返回每层的前驱节点数组update。同时，如果key已存在，返回对应的节点。比较逻辑遵循严格弱序：若a < b 和 b < a 都不成立，则认为相等。

注意，查找是从最高层到最底层，利用update数组记录每层最后一个小于key的节点，为后续插入删除提供准备。该方法复用self._update表，无需创建新表。

下面用mermaid流程图描述_findPredecessors的逻辑：

#mermaid-svg-RCoBWZevIPT0HOc3{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-RCoBWZevIPT0HOc3 .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-RCoBWZevIPT0HOc3 .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-RCoBWZevIPT0HOc3 .error-icon{fill:#552222;}#mermaid-svg-RCoBWZevIPT0HOc3 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-RCoBWZevIPT0HOc3 .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-RCoBWZevIPT0HOc3 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-RCoBWZevIPT0HOc3 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-RCoBWZevIPT0HOc3 .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-RCoBWZevIPT0HOc3 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-RCoBWZevIPT0HOc3 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-RCoBWZevIPT0HOc3 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-RCoBWZevIPT0HOc3 .marker.cross{stroke:#333333;}#mermaid-svg-RCoBWZevIPT0HOc3 svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-RCoBWZevIPT0HOc3 p{margin:0;}#mermaid-svg-RCoBWZevIPT0HOc3 .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-RCoBWZevIPT0HOc3 .cluster-label text{fill:#333;}#mermaid-svg-RCoBWZevIPT0HOc3 .cluster-label span{color:#333;}#mermaid-svg-RCoBWZevIPT0HOc3 .cluster-label span p{background-color:transparent;}#mermaid-svg-RCoBWZevIPT0HOc3 .label text,#mermaid-svg-RCoBWZevIPT0HOc3 span{fill:#333;color:#333;}#mermaid-svg-RCoBWZevIPT0HOc3 .node rect,#mermaid-svg-RCoBWZevIPT0HOc3 .node circle,#mermaid-svg-RCoBWZevIPT0HOc3 .node ellipse,#mermaid-svg-RCoBWZevIPT0HOc3 .node polygon,#mermaid-svg-RCoBWZevIPT0HOc3 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-RCoBWZevIPT0HOc3 .rough-node .label text,#mermaid-svg-RCoBWZevIPT0HOc3 .node .label text,#mermaid-svg-RCoBWZevIPT0HOc3 .image-shape .label,#mermaid-svg-RCoBWZevIPT0HOc3 .icon-shape .label{text-anchor:middle;}#mermaid-svg-RCoBWZevIPT0HOc3 .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-RCoBWZevIPT0HOc3 .rough-node .label,#mermaid-svg-RCoBWZevIPT0HOc3 .node .label,#mermaid-svg-RCoBWZevIPT0HOc3 .image-shape .label,#mermaid-svg-RCoBWZevIPT0HOc3 .icon-shape .label{text-align:center;}#mermaid-svg-RCoBWZevIPT0HOc3 .node.clickable{cursor:pointer;}#mermaid-svg-RCoBWZevIPT0HOc3 .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-RCoBWZevIPT0HOc3 .arrowheadPath{fill:#333333;}#mermaid-svg-RCoBWZevIPT0HOc3 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-RCoBWZevIPT0HOc3 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-RCoBWZevIPT0HOc3 .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-RCoBWZevIPT0HOc3 .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-RCoBWZevIPT0HOc3 .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-RCoBWZevIPT0HOc3 .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-RCoBWZevIPT0HOc3 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-RCoBWZevIPT0HOc3 .cluster text{fill:#333;}#mermaid-svg-RCoBWZevIPT0HOc3 .cluster span{color:#333;}#mermaid-svg-RCoBWZevIPT0HOc3 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-RCoBWZevIPT0HOc3 .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-RCoBWZevIPT0HOc3 rect.text{fill:none;stroke-width:0;}#mermaid-svg-RCoBWZevIPT0HOc3 .icon-shape,#mermaid-svg-RCoBWZevIPT0HOc3 .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-RCoBWZevIPT0HOc3 .icon-shape p,#mermaid-svg-RCoBWZevIPT0HOc3 .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-RCoBWZevIPT0HOc3 .icon-shape rect,#mermaid-svg-RCoBWZevIPT0HOc3 .image-shape rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-RCoBWZevIPT0HOc3 .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-RCoBWZevIPT0HOc3 .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-RCoBWZevIPT0HOc3 :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

是

否

是

否

开始_findPredecessors(key)

初始化current=head, level=MAX_LEVEL

level >= 1?

在当前层向右移动: while current.next[level]存在且 cmp(current.next[level].key, key) 为真

记录update[level]=current

level = level – 1

检查底层current的下一个节点nextNode

nextNode存在且与key相等?

返回update和nextNode

返回update和nil

图4：_findPredecessors 方法流程图

2.7 插入与更新：set

function OrderedMap:set(key, value)
if key == nil then error("键不能为 nil") end

local update, node = self:_findPredecessors(key)
if node then
node.value = value — 更新
return
end

local level = randomLevel()
local newNode = createNode(key, value, level)

for l = 1, level do
newNode.next[l] = update[l].next[l]
update[l].next[l] = newNode
end

self._size = self._size + 1
end

插入逻辑非常清晰：先查找，如果key已存在则更新值；否则随机生成层数，创建新节点，并利用update中记录的前驱节点将新节点插入各层。时间复杂度期望O(log n)。

插入过程的流程图如下：

#mermaid-svg-Am3Uv5NMpGzQh3s8{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-Am3Uv5NMpGzQh3s8 .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .error-icon{fill:#552222;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .marker.cross{stroke:#333333;}#mermaid-svg-Am3Uv5NMpGzQh3s8 svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-Am3Uv5NMpGzQh3s8 p{margin:0;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .cluster-label text{fill:#333;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .cluster-label span{color:#333;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .cluster-label span p{background-color:transparent;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .label text,#mermaid-svg-Am3Uv5NMpGzQh3s8 span{fill:#333;color:#333;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .node rect,#mermaid-svg-Am3Uv5NMpGzQh3s8 .node circle,#mermaid-svg-Am3Uv5NMpGzQh3s8 .node ellipse,#mermaid-svg-Am3Uv5NMpGzQh3s8 .node polygon,#mermaid-svg-Am3Uv5NMpGzQh3s8 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .rough-node .label text,#mermaid-svg-Am3Uv5NMpGzQh3s8 .node .label text,#mermaid-svg-Am3Uv5NMpGzQh3s8 .image-shape .label,#mermaid-svg-Am3Uv5NMpGzQh3s8 .icon-shape .label{text-anchor:middle;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .rough-node .label,#mermaid-svg-Am3Uv5NMpGzQh3s8 .node .label,#mermaid-svg-Am3Uv5NMpGzQh3s8 .image-shape .label,#mermaid-svg-Am3Uv5NMpGzQh3s8 .icon-shape .label{text-align:center;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .node.clickable{cursor:pointer;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .arrowheadPath{fill:#333333;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-Am3Uv5NMpGzQh3s8 .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-Am3Uv5NMpGzQh3s8 .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-Am3Uv5NMpGzQh3s8 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .cluster text{fill:#333;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .cluster span{color:#333;}#mermaid-svg-Am3Uv5NMpGzQh3s8 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-Am3Uv5NMpGzQh3s8 rect.text{fill:none;stroke-width:0;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .icon-shape,#mermaid-svg-Am3Uv5NMpGzQh3s8 .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .icon-shape p,#mermaid-svg-Am3Uv5NMpGzQh3s8 .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .icon-shape rect,#mermaid-svg-Am3Uv5NMpGzQh3s8 .image-shape rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-Am3Uv5NMpGzQh3s8 .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-Am3Uv5NMpGzQh3s8 .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-Am3Uv5NMpGzQh3s8 :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

是

否

是

否

开始set(key, value)

key为nil?

抛出错误

调用_findPredecessors(key)

节点已存在?

更新节点value

随机生成level

创建新节点

l从1到level循环

将新节点插入第l层: newNode.next[l] = update[l].next[l]; update[l].next[l] = newNode

size增加1

结束

图5：set方法流程图

2.8 删除：delete

function OrderedMap:delete(key)
if key == nil then error("键不能为 nil") end
local update, node = self:_findPredecessors(key)
if not node then return end

for l = 1, node.level do
if update[l].next[l] == node then
update[l].next[l] = node.next[l]
end
end

self._size = self._size – 1
end

删除同样借助_findPredecessors获得前驱数组和待删除节点。注意，只需要遍历node.level层（节点实际存在的层）进行删除，不需要处理更高层，因为更高层中没有该节点。

2.9 查询：get

function OrderedMap:get(key)
if key == nil then error("键不能为 nil") end
local _, node = self:_findPredecessors(key)
return node and node.value
end

直接调用_findPredecessors，如果返回节点则取值，否则返回nil。

2.10 遍历与迭代器

function OrderedMap:pairs()
local current = self.head.next[1]
return function()
if current then
local key, value = current.key, current.value
current = current.next[1]
return key, value
end
end
end

OrderedMap.__pairs = function(self)
return self:pairs(), nil, nil
end

迭代器基于底层链表（第1层）遍历，保证了键的顺序。实现了__pairs元方法，使得pairs(map)可以按顺序遍历。

2.11 辅助方法

function OrderedMap:size() return self._size end
function OrderedMap:keys() — 返回所有键数组
function OrderedMap:toArray() — 返回键值对数组

这些方法为调试和使用提供了便利。

三、跳跃表复杂度

3.1 时间复杂度

查找：期望 O(log n)，最坏 O(n)（当所有节点层数都为1时，退化为链表）。但概率上最坏情况概率极低。
插入：查找 + 常数时间插入多层，期望 O(log n)
删除：查找 + 常数时间删除，期望 O(log n)
遍历：O(n)

与平衡树（红黑树）相比，跳跃表在期望时间复杂度上一致，但常数略大（因为涉及多层指针操作），但实现简单，且对并发修改友好（不需要复杂的重平衡）。

3.2 空间复杂度

跳跃表需要额外存储多层索引。每个节点的平均层数为 1/(1-p)，取p=0.5，平均层数为2。因此总指针数约为节点数的2倍，加上键值存储，空间复杂度为 O(n)。相比红黑树需要存储颜色位和左右孩子指针，跳跃表空间开销略高，但仍在可接受范围。

3.3 随机化与概率保证

跳跃表的性能依赖于随机层数生成的均匀性。理论上，当节点数足够大时，各层节点数服从几何分布，查找路径长度的期望为 log_{1/p} n。下面给出不同数据量下的期望查找长度对比：

数据量 n期望查找长度 (p=0.5)红黑树比较次数

1000	~10	~10
10000	~14	~14
100000	~17	~17
1000000	~20	~20

可见期望性能与平衡树非常接近。

3.4 实测性能

代码中包含了简单的性能测试，插入10000个随机键值对耗时约0.0x秒（取决于机器），遍历耗时极短。实际应用中，跳跃表在插入频繁的场景下表现优异，因为不需要像平衡树那样频繁旋转。

附录：完整测试代码运行示例

— ============================================================================
— 高性能有序映射（基于跳跃表 Skip List）
— 支持自定义比较器，按 key 排序，插入/删除/查找均为期望 O(log n)
— ============================================================================

local OrderedMap = {}
OrderedMap.__index = OrderedMap

— 局部化常用函数，提升性能
local random = math.random
local type = type
local tostring = tostring
local pcall = pcall
local setmetatable = setmetatable

— 最大层数（2^20 ≈ 1e6，设置为 32 足够支持千万级数据）
local MAX_LEVEL = 32
— 随机提升层数的概率（经典值 0.5）
local PROBABILITY = 0.5

— 创建一个新节点
— @param key 键（不能为 nil）
— @param value 值
— @param level 节点层数（1 ~ MAX_LEVEL）
local function createNode(key, value, level)
return {
key = key,
value = value,
level = level, — 保存节点层数，便于删除优化
next = {} — next[1] 底层，next[level] 最高层
}
end

— 随机生成层数（满足几何分布）
local function randomLevel()
local level = 1
while level < MAX_LEVEL and random() < PROBABILITY do
level = level + 1
end
return level
end

— 安全比较器：接受用户比较器，返回一个永不抛错的比较函数
local function makeSafeComparator(userCmp)
— 预定义类型排序（稳定且安全）
local typeOrder = {
number = 1,
string = 2,
boolean = 3,
table = 4,
func = 5,
thread = 6,
userdata = 7,
}
return function(a, b)
— 处理 nil（理论上不会出现，但防御性编程）
if a == nil or b == nil then
if a == nil and b == nil then return false end
return a == nil — nil 最小
end

local typeA, typeB = type(a), type(b)
if typeA ~= typeB then
— 类型不同：按预定义顺序比较
return (typeOrder[typeA] or 8) < (typeOrder[typeB] or 8)
end

— 类型相同
if typeA == "number" or typeA == "string" then
— 尝试调用用户比较器
local ok, result = pcall(userCmp, a, b)
if ok then
return result
else
— 用户比较器出错，回退到默认比较
return a < b
end
else
— 其他类型：安全地转为字符串比较
local ok1, strA = pcall(tostring, a)
local ok2, strB = pcall(tostring, b)
if ok1 and ok2 then
return strA < strB
else
— 若 tostring 失败，回退到类型名比较
return typeA < typeB
end
end
end
end

— 创建有序映射
— @param cmp 比较器，可以是：
— – 字符串 "asc" 或 "<" （默认，升序）
— – 字符串 "desc" 或 ">" （降序）
— – 函数 cmp(a, b) 返回 true 表示 a 应该排在 b 前面
function OrderedMap.new(cmp)
— 生成基础比较器
local baseCmp
if cmp == nil or cmp == "asc" or cmp == "<" then
baseCmp = function(a, b) return a < b end
elseif cmp == "desc" or cmp == ">" then
baseCmp = function(a, b) return a > b end
elseif type(cmp) == "function" then
baseCmp = cmp
else
error("比较器必须是函数、'asc'、'desc'、'<' 或 '>'")
end

— 创建头节点（不存储数据）
local head = createNode(nil, nil, MAX_LEVEL)

local self = {
head = head,
_cmp = makeSafeComparator(baseCmp), — 安全比较器
_size = 0,
_update = {}, — 预分配的 update 数组，避免频繁创建表
}
return setmetatable(self, OrderedMap)
end

— 内部方法：查找给定 key 的前驱节点（每层的前一个节点）
— 使用实例内的 _update 表存储每层的前驱节点
— 返回两个值：
— update: 数组，update[l] 表示第 l 层上最后一个小于 key 的节点
— node: 如果 key 已存在，则返回该节点；否则返回 nil
function OrderedMap:_findPredecessors(key)
local update = self._update — 复用实例中的表
local current = self.head
local cmp = self._cmp

— 从最高层开始向下搜索
for level = MAX_LEVEL, 1, –1 do
— 在当前层向前移动，直到下一个节点的 key 不小于 key
while current.next[level] and cmp(current.next[level].key, key) do
current = current.next[level]
end
update[level] = current
end

— 到达底层后，current 是最后一个小于 key 的节点
local nextNode = current.next[1]
if nextNode and not cmp(nextNode.key, key) and not cmp(key, nextNode.key) then
— 根据严格弱序，两个方向都不小于则视为相等
return update, nextNode
end
return update, nil
end

— 插入或更新键值对
— @param key 键（不能为 nil）
— @param value 值
function OrderedMap:set(key, value)
if key == nil then error("键不能为 nil") end

local update, node = self:_findPredecessors(key)
if node then
— key 已存在，更新值
node.value = value
return
end

— 不存在，创建新节点
local level = randomLevel()
local newNode = createNode(key, value, level)

— 插入到每一层
for l = 1, level do
newNode.next[l] = update[l].next[l]
update[l].next[l] = newNode
end

self._size = self._size + 1
end

— 获取指定 key 的值，不存在返回 nil
function OrderedMap:get(key)
if key == nil then error("键不能为 nil") end — 与 set 保持一致
local _, node = self:_findPredecessors(key)
return node and node.value
end

— 删除指定 key 的键值对
function OrderedMap:delete(key)
if key == nil then error("键不能为 nil") end — 与 set 保持一致
local update, node = self:_findPredecessors(key)
if not node then return end — 不存在

— 从每一层中移除该节点（只遍历节点实际存在的层）
for l = 1, node.level do
if update[l].next[l] == node then
update[l].next[l] = node.next[l]
end
end

self._size = self._size – 1
end

— 返回有序映射的元素个数
function OrderedMap:size()
return self._size
end

— 返回所有键的数组（按顺序）
function OrderedMap:keys()
local keys = {}
local current = self.head.next[1]
local i = 1
while current do
keys[i] = current.key
i = i + 1
current = current.next[1]
end
return keys
end

— 返回一个迭代器，用于遍历所有键值对（按顺序）
— 用法：for key, value in map:pairs() do … end
function OrderedMap:pairs()
local current = self.head.next[1]
return function()
if current then
local key, value = current.key, current.value
current = current.next[1]
return key, value
end
end
end

— 支持 Lua 5.2+ 的 __pairs 元方法，使得 pairs(map) 按顺序遍历
— 符合标准：返回三个值（迭代器、状态、初始键）
OrderedMap.__pairs = function(self)
return self:pairs(), nil, nil
end

— 返回键值对数组（每个元素是 {key, value}），用于调试
function OrderedMap:toArray()
local arr = {}
local current = self.head.next[1]
local i = 1
while current do
arr[i] = { current.key, current.value }
i = i + 1
current = current.next[1]
end
return arr
end

— ============================================================================
— 测试代码（保留原样，验证正确性）
— ============================================================================

— 辅助函数：打印 map 内容
local function printMap(map, title)
print(title or "Map 内容:")
for k, v in map:pairs() do
print(" " .. tostring(k) .. " -> " .. tostring(v))
end
print("大小:", map:size())
end

— 测试 1：默认升序
print("=== 测试 1: 默认升序 ===")
local map1 = OrderedMap.new()
map1:set("banana", 2)
map1:set("apple", 1)
map1:set("cherry", 3)
map1:set("date", 4)
printMap(map1, "插入 apple, banana, cherry, date 后:")

— 测试 2：降序
print("\\n=== 测试 2: 降序 ===")
local map2 = OrderedMap.new("desc")
map2:set(10, "ten")
map2:set(5, "five")
map2:set(20, "twenty")
map2:set(1, "one")
printMap(map2, "插入 10,5,20,1 后:")

— 测试 3：自定义比较器（按字符串长度）
print("\\n=== 测试 3: 自定义比较器（按长度）===")
local map3 = OrderedMap.new(function(a, b) return #a < #b end)
map3:set("apple", "fruit")
map3:set("banana", "fruit")
map3:set("pear", "fruit")
map3:set("kiwi", "fruit")
printMap(map3, "按字符串长度排序:")

— 测试 4：更新值
print("\\n=== 测试 4: 更新值 ===")
local map4 = OrderedMap.new()
map4:set("x", 100)
map4:set("y", 200)
printMap(map4, "更新前:")
map4:set("x", 999)
printMap(map4, "更新 x -> 999 后:")

— 测试 5：删除
print("\\n=== 测试 5: 删除 ===")
local map5 = OrderedMap.new()
map5:set("a", 1)
map5:set("b", 2)
map5:set("c", 3)
printMap(map5, "删除前:")
map5:delete("b")
printMap(map5, "删除 'b' 后:")
map5:delete("z")
printMap(map5, "删除不存在的 'z' 后:")

— 测试 6：获取值
print("\\n=== 测试 6: 获取值 ===")
local val = map5:get("a")
print("get('a'):", val)
val = map5:get("z")
print("get('z'):", val)

— 测试 7：大量随机数据，验证排序正确性
print("\\n=== 测试 7: 随机插入并验证顺序 ===")
math.randomseed(os.time())
local map6 = OrderedMap.new()
local keys = {}
for i = 1, 1000 do
local k = math.random(1, 10000)
table.insert(keys, k)
map6:set(k, tostring(k))
end
local prev = nil
local sorted = true
for k, _ in map6:pairs() do
if prev and k < prev then
sorted = false
break
end
prev = k
end
print("是否升序?", sorted)

local toDelete = keys[math.random(1, #keys)]
print("删除键:", toDelete)
map6:delete(toDelete)
local exists = map6:get(toDelete) ~= nil
print("键仍然存在?", exists)
print("最终大小:", map6:size())

— 测试 8：性能测试（简单计时）
print("\\n=== 测试 8: 性能测试（插入 10000 个元素）===")
local map7 = OrderedMap.new()
local start = os.clock()
for i = 1, 10000 do
map7:set(math.random(1, 100000), i)
end
local elapsed = os.clock() – start
print(string.format("插入 10000 个随机键: %.3f 秒", elapsed))

start = os.clock()
local count = 0
for _ in map7:pairs() do
count = count + 1
end
elapsed = os.clock() – start
print(string.format("遍历 %d 个元素: %.3f 秒", count, elapsed))

print("\\n所有测试完成。")

return OrderedMap

下面是在Lua环境中运行测试代码的部分输出：

=== 测试 1: 默认升序 ===
插入 apple, banana, cherry, date 后:
apple -> 1
banana -> 2
cherry -> 3
date -> 4
大小:4

=== 测试 2: 降序 ===
插入 10,5,20,1 后:
20 -> twenty
10 -> ten
5 -> five
1 -> one
大小:4

=== 测试 3: 自定义比较器（按长度）===
按字符串长度排序:
pear -> fruit
apple -> fruit
banana -> fruit
大小:3

=== 测试 4: 更新值 ===
更新前:
x -> 100
y -> 200
大小:2
更新 x -> 999 后:
x -> 999
y -> 200
大小:2

=== 测试 5: 删除 ===
删除前:
a -> 1
b -> 2
c -> 3
大小:3
删除 'b' 后:
a -> 1
c -> 3
大小:2
删除不存在的 'z' 后:
a -> 1
c -> 3
大小:2

=== 测试 6: 获取值 ===
get('a'):1
get('z'):nil

=== 测试 7: 随机插入并验证顺序 ===
是否升序?true
删除键:7619
键仍然存在?false
最终大小:942

=== 测试 8: 性能测试（插入 10000 个元素）===
插入 10000 个随机键: 0.198 秒
遍历 9525 个元素: 0.003 秒

所有测试完成。

跳跃表：实现高性能类有序映射std::map（Lua）