Solidity纯函数内实现字符串集合去重的最优方案咨询

原代码问题说明 #

你给出的初始代码无法通过编译，核心原因是 Solidity 不支持在 pure 函数中声明 memory 类型的 mapping，mapping 只能作为状态变量或 storage 引用使用，因此你原本基于 mapping 实现O(1)存在性判断的思路无法在 pure 函数中直接落地。

最高效实现方案 #

根据输入数组的长度，可选择两种适配方案：

方案1：哈希遍历法（适用输入长度<15的场景） #

实现简单，固定开销低，逻辑为将每个字符串转为keccak256哈希存入内存数组，每次新元素计算哈希后与已存哈希逐一对比，无重复则加入结果集。

function dedupe(string[] memory keys) public pure returns(string[] memory) {
    if (keys.length == 0) return new string[](0);
    // 暂存已出现的字符串哈希
    bytes32[] memory seenHashes = new bytes32[](keys.length);
    // 暂存去重结果，最大长度不超过原数组长度
    string[] memory tempResult = new string[](keys.length);
    uint256 resultCount = 0;

    for (uint256 i = 0; i < keys.length; i++) {
        bytes32 currentHash = keccak256(abi.encodePacked(keys[i]));
        bool isDuplicate = false;
        // 遍历已出现的哈希判断是否重复
        for (uint256 j = 0; j < resultCount; j++) {
            if (seenHashes[j] == currentHash) {
                isDuplicate = true;
                break;
            }
        }
        if (!isDuplicate) {
            seenHashes[resultCount] = currentHash;
            tempResult[resultCount] = keys[i];
            resultCount++;
        }
    }
    // 裁剪结果数组到实际长度
    string[] memory deduped = new string[](resultCount);
    for (uint256 k = 0; k < resultCount; k++) {
        deduped[k] = tempResult[k];
    }
    return deduped;
}

方案2：排序去重法（适用输入长度≥15的场景） #

时间复杂度为O(n log n)，输入元素越多，效率优势越明显，逻辑为给所有元素计算哈希后按哈希排序，相同哈希会相邻，遍历一次即可完成去重。

// 辅助函数：排序哈希数组，同步关联原字符串索引
function sortHashes(bytes32[] memory hashes, uint256[] memory indices) internal pure {
    quickSort(hashes, indices, int256(0), int256(hashes.length - 1));
}

function quickSort(bytes32[] memory hashes, uint256[] memory indices, int256 left, int256 right) internal pure {
    if (left >= right) return;
    int256 p = partition(hashes, indices, left, right);
    quickSort(hashes, indices, left, p - 1);
    quickSort(hashes, indices, p + 1, right);
}

function partition(bytes32[] memory hashes, uint256[] memory indices, int256 left, int256 right) internal pure returns (int256) {
    bytes32 pivot = hashes[uint256(right)];
    int256 i = left - 1;
    for (int256 j = left; j < right; j++) {
        if (hashes[uint256(j)] < pivot) {
            i++;
            (hashes[uint256(i)], hashes[uint256(j)]) = (hashes[uint256(j)], hashes[uint256(i)]);
            (indices[uint256(i)], indices[uint256(j)]) = (indices[uint256(j)], indices[uint256(i)]);
        }
    }
    (hashes[uint256(i + 1)], hashes[uint256(right)]) = (hashes[uint256(right)], hashes[uint256(i + 1)]);
    (indices[uint256(i + 1)], indices[uint256(right)]) = (indices[uint256(right)], indices[uint256(i + 1)]);
    return i + 1;
}

// 主去重函数
function dedupe(string[] memory keys) public pure returns(string[] memory) {
    if (keys.length == 0) return new string[](0);
    uint256 len = keys.length;
    bytes32[] memory hashes = new bytes32[](len);
    uint256[] memory indices = new uint256[](len);
    // 预计算所有字符串的哈希和对应索引
    for (uint256 i = 0; i < len; i++) {
        hashes[i] = keccak256(abi.encodePacked(keys[i]));
        indices[i] = i;
    }
    // 按哈希排序
    sortHashes(hashes, indices);
    // 遍历排序后的数组去重
    string[] memory tempResult = new string[](len);
    uint256 resultCount = 0;
    bytes32 lastHash = 0;
    for (uint256 i = 0; i < len; i++) {
        if (i == 0 || hashes[i] != lastHash) {
            tempResult[resultCount] = keys[indices[i]];
            resultCount++;
            lastHash = hashes[i];
        }
    }
    // 裁剪结果数组
    string[] memory deduped = new string[](resultCount);
    for (uint256 k = 0; k < resultCount; k++) {
        deduped[k] = tempResult[k];
    }
    return deduped;
}

补充说明 #

• keccak256哈希碰撞概率极低，普通业务场景可以完全忽略该风险，若对安全性要求极高，可在哈希匹配后额外增加一步原字符串内容对比，额外开销极低。
• 两种方案均为纯内存操作，无需操作状态变量，避免了状态读写的高额gas消耗。

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