Search code examples
ethereumsolidity

HashSet data structure in Solidity

Is there any way of implementing a set in Solidity, in order to check if an element exists, in O(1) average? I have been thinking of using a mapping object with no values, is that faster than using an array and iterating in order to find elements?

Solution

  • Yes in sense of speed you are better off using a mapping. The closest thing to a set in solidity is to us a mapping and an array. But it will have terrible cost to iterate when you want to remove an element.

    Mapping Example

    mapping (address => bool) yourMapping; // maps address (key) to boolean (value)

    Set Example

    contract Contract {

    struct Set {
        uint[] values;
        mapping (uint => bool) is_in;
    }

    Set my_set;

    function add(uint a) public {
         if (!my_set.is_in[a]) {
             my_set.values.push(a);
             my_set.is_in[a] = true;
         }
    }
}