# solidity如何实现抽取池

By [sen](https://paragraph.com/@sen-3) · 2022-04-29

---

背景
--

开发智能合约的时候，可能会遇到从固定池子中随机抽取不重复item的需求。

问题分析
----

solidity有以下限制

*   map
    
    *   不能获取length
        
    *   不能遍历keyset
        
    *   key不能是自定义类型
        
*   array
    
    *   只有原生数组array
        
    *   基于array实现功能丰富的list，update性能较差，gas费高
        
    *   只能从顶部push或pop（能remove指定下标的value，但其实只是置空，不会移除该项）
        

思路
--

先用array充当这个池子，假设池子中共有十个元素

![](https://storage.googleapis.com/papyrus_images/397369949b30ed6464a7c1145ff897316fa79c1c3364115168cc72c2802a3d2a.png)

第一次抽到了下标为3的元素（randomValue % 10 = 3）

![](https://storage.googleapis.com/papyrus_images/739bbb68cbf350a17e8506baa9ca66249653592e72ff1239efdf3813e1b211bc.png)

共10个元素，抽走了一个，应该剩余9个，但array不能移除指定下标元素，只能移除最后一个元素，那么我们假设刚才抽到的不是3，而是最后一个元素9，但同时要保证返回的是3对应的value。那么我们交换下标3、9对应的元素：

![](https://storage.googleapis.com/papyrus_images/48f5ac1b4249093a79e065917a2f174481aeebd71b8adf80270b55d285c7c608.png)

这样的话，下次抽奖公式就变成了：randomValue % 9 了，问题解决了

方案分析
----

这种方案简单，但有个问题：每次抽到时，都需要交换两个下标的值，造成额外的写入，gas费翻倍

升级版
---

假设还是先抽到3

![](https://storage.googleapis.com/papyrus_images/587cfbc3f38cbcbb220e2ba18a09a375a2717fbe4582c1e6156f5a44ee8590c3.png)

这里不与9交换了，而是做个标识，3已被抽，若下次再抽到3，请拿9的值

也就是3指向9（3 → 9）

下次的抽奖公式依然为：randomValue % 9

假设第二次还是抽到了3

![](https://storage.googleapis.com/papyrus_images/b04bd2af7a25d9a0590c9bd093ebef901ec94cdc8d82209aa13ce9511a325413.png)

3 → 8

同时记录

*   totalCount：池子总数
    
*   alreadyMintCount：已铸造数
    

那么被指向的下标targetPointIndex算法为：

    uint targetPointIndex = totalCount - alreadyMintCount - 1;
    if (pool[targetPointIndex].pointIndex > 0) { // 若目标也已经下发，则指向目标的目标
        targetPointIndex = pool[targetPointIndex].pointIndex;
    }
    

其中pool为“池子”数组，池子数组中存储元素结构体如下：

    struct Item {
        bool    status; /** alreday mint mark, true: yes */
        uint16  pointIndex;
    }
    

方案分析2
-----

如果item比较简单，仅仅是数字的话，可以节省struct Item的定义，使用mapping(uint => uint)取代更简洁，而且mapping不需要初始化，可以用于动态增加池子的场景。

升级版2
----

我写了个demo，供大家参考

[https://github.com/981859608/bc/tree/main/contracts/%E9%9A%8F%E6%9C%BA%E6%95%B0%E6%B1%A0](https://github.com/981859608/bc/tree/main/contracts/%E9%9A%8F%E6%9C%BA%E6%95%B0%E6%B1%A0)

---

*Originally published on [sen](https://paragraph.com/@sen-3/solidity)*