Membership in a set of strings

Question

I'm looking solidity help in storing a set of strings and checking for membership in that set. I have a concrete and an abstract question on that:

Concrete

What is the data structure in solidity that gives me a (potentially append-only) set that I can interrogate for membership? eg, I am looking specifically for something like:

myset = ["a", "b", "c"] # registers my set on-chain
"d" in myset            # return True or False

Further, are there better or worse ways of using this data structure without a lot of data duplication?

Does the answer change if myset is a million members long?

Abstract

How is such a thing implemented under the hood? Read access testing for membership seems possible, but since chains are immutable, how would such a list be practically updated?

Answer 1

A mapping is all you need:

pragma solidity ^0.4.25;

contract Test { 
    mapping(string => bool) seen;

    function add(string foo) external {
        seen[foo] = true;
    }

    function alreadySeen(string foo) external view returns (bool) {
        return seen[foo];
    }
}

Contract storage is mutable. Calling the blockchain "immutable" is perhaps misleading... a better term might be "append only." By sending new transactions to a smart contract, you can append to the blockchain, and the state in the latest block can be different than the state in previous blocks. So all the old blocks are still there and immutable, but the current state of your smart contract storage can be different over time (because "current" means the latest block).

Note that the keys of a mapping can't be enumerated. If you need to enumerate the values that you've added to your set, I have a blog post about enumerable sets that should help: https://programtheblockchain.com/posts/2018/06/03/storage-patterns-set/.