A true HashMap implementation for Solidity — including .keys() and .entries(). More storage-efficient than alternatives.

HashMap.sol

// SPDX-License-Identifier: MIT
// See Solidity forum discussion: https://forum.soliditylang.org/t/adding-hashmap-style-storage-layout-to-solidity/1448
// This HashMap implementation is somewhat similar to how Java's HashMap works.
// For example: https://anmolsehgal.medium.com/java-hashmap-internal-implementation-21597e1efec3

pragma solidity >=0.7.0 <0.9.0;

struct HashMap {
    bool init;
}

library HashMapLib {
    uint constant BUCKET_COUNT = 256;

    function bytesHash (bytes32 key) private pure returns (uint hash) {
        hash = uint(keccak256(abi.encode(key)));
    }

    function baseSlot (HashMap storage map) private pure returns (uint slot) {
        assembly {
            slot := map.slot
        }
    }

    function size (HashMap storage map) internal view returns (uint mapSize) {
        uint slot = baseSlot(map);
        assembly {
            mapSize := sload(slot)
        }
    }

    function _bucket (HashMap storage map, bytes32 key) private pure returns (uint slot) {
        return baseSlot(map) + 1 + (bytesHash(key) % BUCKET_COUNT);
    }

    function _findKey (HashMap storage map, bytes32 key) private view returns (uint keySlot, bytes32 currKey, uint bucketSlot) {
        bucketSlot = _bucket(map, key);

        assembly {
            keySlot := add(bucketSlot, BUCKET_COUNT)
            currKey := sload(keySlot)
        }

        while (currKey != "" && currKey != key) {
            assembly {
                keySlot := add(keySlot, mul(BUCKET_COUNT, 2))
                currKey := sload(keySlot)
            }
        }
    }

    function _increaseSize (HashMap storage map, uint bucketSlot) private {
        assembly {
            sstore(map.slot, add(sload(map.slot), 1))
            sstore(bucketSlot, add(sload(bucketSlot), 1))
        }
    } 

    function _decreaseSize (HashMap storage map, uint bucketSlot) private {
        assembly {
            sstore(map.slot, sub(sload(map.slot), 1))
            sstore(bucketSlot, sub(sload(bucketSlot), 1))
        }
    } 

    function _bucketSize (HashMap storage map, uint bucket) private view returns (uint bucketSize) {
        assembly {
            let bucketSlot := add(add(map.slot, 1), bucket)
            bucketSize := sload(bucketSlot)
        }
    }

    function _getKeyInBucketByIndex (HashMap storage map, uint bucket, uint index) private view returns (bytes32 key, uint keySlot) {
        uint firstKeySlot = baseSlot(map) + 1 + bucket + BUCKET_COUNT;
        keySlot = firstKeySlot + (2 * BUCKET_COUNT) * index;

        assembly {
            key := sload(keySlot)
        } 
    }

    function _getKeyValueInBucketByIndex (HashMap storage map, uint bucket, uint index) private view returns (KV memory kv) {
        (bytes32 key, uint keySlot) = _getKeyInBucketByIndex(map, bucket, index);

        if (key == "") return KV("", "");

        uint valueSlot = keySlot + BUCKET_COUNT;
        bytes32 value;
        assembly {
            value := sload(valueSlot)
        }

        kv = KV(key, value);
    }

    function keys (HashMap storage map) internal view returns (bytes32[] memory keyList) {
        uint mapSize = size(map);
        uint keyCount = 0;
        keyList = new bytes32[](mapSize);

        for (uint currBucket = 0; currBucket < BUCKET_COUNT; currBucket++) {
            uint bucketSize = _bucketSize(map, currBucket);

            for (uint bucketIndex = 0; bucketIndex < bucketSize; bucketIndex++) {
                (bytes32 key,) = _getKeyInBucketByIndex(map, currBucket, bucketIndex);
                if (key == "") continue;
                keyList[keyCount] = key;
                keyCount++;
            }

            if (keyCount == mapSize) break;
        }

        return keyList;
    }

    struct KV {
        bytes32 key;
        bytes32 value;
    }

    function entries (HashMap storage map) internal view returns (KV[] memory) {
        uint mapSize = size(map);
        uint kvCount = 0;
        KV[] memory pairs = new KV[](mapSize);

        for (uint currBucket = 0; currBucket < BUCKET_COUNT; currBucket++) {
            uint bucketSize = _bucketSize(map, currBucket);

            for (uint bucketIndex = 0; bucketIndex < bucketSize; bucketIndex++) {
                KV memory kv = _getKeyValueInBucketByIndex(map, currBucket, bucketIndex);
                if (kv.key == "") continue;
                pairs[kvCount] = kv;
                kvCount++;
            }

            if (kvCount == mapSize) break;
        }

        return pairs;
    } 

    function set (HashMap storage map, bytes32 key, bytes32 value) internal {
        (uint keySlot, bytes32 currKey, uint bucketSlot) = _findKey(map, key);

        assembly {
            sstore(keySlot, key)
            sstore(add(keySlot, BUCKET_COUNT), value)
        }

        if (currKey != key) {
            _increaseSize(map, bucketSlot);
        }
    }

    function get (HashMap storage map, bytes32 key) internal view returns (bytes32 value) {
        (uint keySlot,,) = _findKey(map, key);
        assembly {
            value := sload(add(keySlot, BUCKET_COUNT))
        }
    }

    function remove (HashMap storage map, bytes32 key) internal {
        (uint keySlot, , uint bucketSlot) = _findKey(map, key);
        assembly {
            let valueSlot := add(keySlot, BUCKET_COUNT)
            sstore(keySlot, "")
            sstore(valueSlot, "")
        }
        _decreaseSize(map, bucketSlot);
    } 

}

HashMapContract.sol

// SPDX-License-Identifier: MIT

pragma solidity >=0.7.0 <0.9.0;

import "./HashMap.sol";

contract HashMapContract {
    using HashMapLib for HashMap;

    HashMap hashmap;
    HashMap hashmap2;

    function size2 () public view returns (uint mapSize) {
        return hashmap2.size();
    }

    function size () public view returns (uint mapSize) {
        return hashmap.size();
    }

    function keys () public view returns (bytes32[] memory) {
        return hashmap.keys();
    } 

    function entries () public view returns (HashMapLib.KV[] memory) {
        return hashmap.entries();
    } 

    function set (bytes32 key, bytes32 value) public {
        return hashmap.set(key, value);
    }

    function get (bytes32 key) public view returns (bytes32 value) {
        return hashmap.get(key);
    }

    function remove (bytes32 key) public {
        return hashmap.remove(key);
    } 

}

HashMapContract.test.js

const { expect } = require("chai");
const { ethers } = require("hardhat");

describe("HashMapContract", function () {
  const strToBytes = ethers.utils.formatBytes32String;
  let hashmap;

  beforeEach(async () => {
    const HashMapContract = await ethers.getContractFactory("HashMapContract");
    const hashmapDeployment = await HashMapContract.deploy();
    await hashmapDeployment.deployed();
    hashmap = await ethers.getContractAt("HashMapContract", hashmapDeployment.address);
  });

  it("should return different sizes for different hashmaps", async function () {
    const tx = await hashmap.set(strToBytes("test3"), strToBytes("testing 1"));
    await tx.wait();
    const value1 = await hashmap.size();
    const value2 = await hashmap.size2();
    expect(value1).to.deep.equal(1);
    expect(value2).to.deep.equal(0);
  });

  it("should return list of all keys", async function () {
    const tx = await hashmap.set(strToBytes("test3"), strToBytes("testing 1"));
    await tx.wait();
    const tx2 = await hashmap.set(strToBytes("test4"), strToBytes("testing 2"));
    await tx2.wait();
    const value = await hashmap.keys();
    expect(value).to.deep.equal([strToBytes("test3"), strToBytes("test4")]);
  });

  it("should return list of all entries", async function () {
    const tx = await hashmap.set(strToBytes("test3"), strToBytes("testing 1"));
    await tx.wait();
    const tx2 = await hashmap.set(strToBytes("test4"), strToBytes("testing 2"));
    await tx2.wait();
    const value = await hashmap.entries();
    expect(value).to.deep.equal([
      [strToBytes("test3"), strToBytes("testing 1")],
      [strToBytes("test4"), strToBytes("testing 2")]
    ]);
  });

  it("should reduce size when deleting a key", async () => {
    const tx = await hashmap.set(strToBytes("test3"), strToBytes("testing 1"));
    await tx.wait();
    const tx2 = await hashmap.remove(strToBytes("test3"));
    await tx2.wait();
    expect((await hashmap.size()).toNumber()).to.equal(0);
  });

  it("should empty the value when key is removed", async () => {
    const tx = await hashmap.set(strToBytes("test3"), strToBytes("testing 1"));
    await tx.wait();
    const tx2 = await hashmap.remove(strToBytes("test3"));
    await tx2.wait();
    const value = await hashmap.get(strToBytes("test3"));
    expect(value).to.equal(strToBytes(""));
  });

  it("should keep 2 keys with same `bucket` separately", async function () {
    const tx = await hashmap.set(strToBytes("test3"), strToBytes("testing 1"));
    await tx.wait();
    const tx2 = await hashmap.set(strToBytes("test4"), strToBytes("testing 2"));
    await tx2.wait();
    const value = await hashmap.get(strToBytes("test3"));
    expect(value).to.equal(strToBytes("testing 1"));
  });

  it("should overwrite values if setting same key", async function () {
    const tx = await hashmap.set(strToBytes("test"), strToBytes("testing 1"));
    await tx.wait();
    const tx2 = await hashmap.set(strToBytes("test"), strToBytes("testing 2"));
    await tx2.wait();
    const value = await hashmap.get(strToBytes("test"));
    expect(value).to.equal(strToBytes("testing 2"));
  });

  it("should return values as set originally", async function () {
    const tx = await hashmap.set(strToBytes("test"), strToBytes("testing"));
    await tx.wait();
    const value = await hashmap.get(strToBytes("test"));
    expect(value).to.equal(strToBytes("testing"));
  });

  it("should not increase size when setting same key twice", async function () {
    const tx = await hashmap.set(strToBytes("test"), strToBytes("testing"));
    await tx.wait();
    const tx2 = await hashmap.set(strToBytes("test"), strToBytes("testing"));
    await tx2.wait();
    expect((await hashmap.size()).toNumber()).to.equal(1);
  });

  it("should increase size after set()", async function () {
    const tx = await hashmap.set(strToBytes("test"), strToBytes("testing"));
    await tx.wait();
    expect((await hashmap.size()).toNumber()).to.equal(1);
  });

  it("should have initial size 0", async function () {
    expect((await hashmap.size()).toNumber()).to.equal(0);
  });
});