OpenZeppelin库EnumerableMap数据结构的分

EnumerableMap库是基于EnumerableSet库实现了一些具有Map功能的数据结构。

支持类型：

1. bytes32 -> bytes32 （ Bytes32ToBytes32Map）
2. uint256 -> address （ UintToAddressMap）
3. address -> uint256 （ AddressToUintMap）
4. uint256 -> uint256 （ UintToUintMap）
5. bytes32 -> uint256 （ Bytes32ToUintMap）

特性

1. 具体新增或修改set、删除remove、检查contains函数。
2. 无序性。

在这里使用了EnumerableSet.Bytes32Set类型，主要用来存储key，保证key的唯一性，也可以更方便实现删除remove功能。

using EnumerableSet for EnumerableSet.Bytes32Set;

前面列举出的5种类型，其中Bytes32ToBytes32Map类型是该库的基础类型，其他四个类型都是基于Bytes32ToBytes32Map来实现的，只有Bytes32ToBytes32Map是基于EnumerableSet.Bytes32Set。

可以从每个结构体声明的变量可以看出来

struct Bytes32ToBytes32Map {
        // Storage of keys
        EnumerableSet.Bytes32Set _keys;
        mapping(bytes32 => bytes32) _values;
    }
 struct UintToUintMap {
        Bytes32ToBytes32Map _inner;
    }
struct UintToAddressMap {
        Bytes32ToBytes32Map _inner;
    }
struct AddressToUintMap {
        Bytes32ToBytes32Map _inner;
    }
struct Bytes32ToUintMap {
        Bytes32ToBytes32Map _inner;
    }

Bytes32ToBytes32Map

基础类型声明了2个类型的变量，一个是_keys，EnumerableSet.Bytes32Set类型，用来存储key；另一个是_values，mapping(bytes32 => bytes32)类型，用来存储value。

新增或修改函数 set

    // EnumerableMap.sol
    /**
     * @dev Adds a key-value pair to a map, or updates the value for an existing
     * key. O(1).
     *
     * Returns true if the key was added to the map, that is if it was not
     * already present.
     */
    function set(Bytes32ToBytes32Map storage map, bytes32 key, bytes32 value) internal returns (bool) {
        // 存储在mapping
        map._values[key] = value;
        // 存储在EnumerableSet.Bytes32Set
        return map._keys.add(key);
    }

    //  EnumerableSet.sol
    /**
     * @dev Add a value to a set. O(1).
     *
     * Returns true if the value was added to the set, that is if it was not
     * already present.
     */
    function add(Bytes32Set storage set, bytes32 value) internal returns (bool) {
        return _add(set._inner, value);
    }

因为map._values[key] = value; 这里是直接赋值，所以该函数支持新增和修改。这里将值存储在mapping(bytes32 => bytes32)类型的空间中。而key可以从return返回值 return map._keys.add(key)看出，是存储在EnumerableSet.Bytes32Set类型的空间中。这也从代码实现方面印证了前面的说法。

删除函数 remove

 // EnumerableMap.sol
  /**
     * @dev Removes a key-value pair from a map. O(1).
     *
     * Returns true if the key was removed from the map, that is if it was present.
     */
    function remove(Bytes32ToBytes32Map storage map, bytes32 key) internal returns (bool) {
        delete map._values[key];
        return map._keys.remove(key);
    }

  //  EnumerableSet.sol
  /**
     * @dev Removes a value from a set. O(1).
     *
     * Returns true if the value was removed from the set, that is if it was
     * present.
     */
    function remove(Bytes32Set storage set, bytes32 value) internal returns (bool) {
        return _remove(set._inner, value);
    }

remove函数做了两件事，其一是删除值，其二是删除key。删除key，最终是调用了EnumerableSet库的remove函数，从数组中删除key。删除值则是直接删除mapping的方式delete map._values[key];

EnumerableMap库支持的类型在检查是否存在、获取长度时都是通过检查或获取key的相关信息实现，这是因为key具有唯一性。当前这些函数最终也是调用了EnumerableSet库的contains（检查）和length（长度）函数。

image.png

通过索引获取值 at函数

function at(Bytes32ToBytes32Map storage map, uint256 index) internal view 
returns (bytes32, bytes32) {
        bytes32 key = map._keys.at(index);
        return (key, map._values[key]);
    }

先根据索引index从EnumerableSet.Bytes32Set中获取到key，再根据key从
mapping(bytes32 => bytes32) 中获取值。这里没有去验证值的有效性。

根据key获取值

/**
     * @dev Tries to returns the value associated with `key`. O(1).
     * Does not revert if `key` is not in the map.
     */
    function tryGet(Bytes32ToBytes32Map storage map, bytes32 key) internal view 
      returns (bool, bytes32) { 
        bytes32 value = map._values[key];
        if (value == bytes32(0)) {
            return (contains(map, key), bytes32(0));
        } else {
            return (true, value);
        }
    }

    /**
     * @dev Returns the value associated with `key`. O(1).
     *
     * Requirements:
     *
     * - `key` must be in the map.
     */
    function get(Bytes32ToBytes32Map storage map, bytes32 key) internal view
      returns (bytes32) {
        bytes32 value = map._values[key];
        require(value != 0 || contains(map, key), "EnumerableMap: nonexistent key");
        return value;
    }

根据key获取值有2种方式，一种是tryGet，另一种是get。
tryGet方式：在获取值时，当没有找到值，不会去验证值的有效性，会直接返回值或者默认值。
get方式：会去验证获取到的值是否是有效的值，如果不是则会中断。
get方式使用了require去验证值，而tryGet没有使用。

其他四种类型UintToAddressMap、AddressToUintMap、UintToUintMap、Bytes32ToUintMap的函数和Bytes32ToBytes32Map一致，最终都是通过Bytes32ToBytes32Map的函数去调用。
由于这四种类型的key-value可能和Bytes32ToBytes32Map的key-value类型不一致，所以在函数调用时需要进行类型转换。
这里的类型转换原理同EnumerableSet库一致，函数需要什么类型，一次次转换成需要的类型即可。

总结

1. EnumerableMap同EnumerableSet一样，具有无序性。
2. 类型不同时，需要进行类型转换。
3. 查找快速，根据key获取值。

思考

1. 为什么Bytes32ToBytes32Map要使用EnumerableSet库来存储key，使用一个数组来实现不可以吗？
2. tryGet和get的区别是是否使用require，二者的使用场景有何不同？