Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

v2 store UnorderedMap implementation #580

Closed
austinabell opened this issue Sep 22, 2021 · 0 comments · Fixed by #584
Closed

v2 store UnorderedMap implementation #580

austinabell opened this issue Sep 22, 2021 · 0 comments · Fixed by #584
Assignees

Comments

@austinabell
Copy link
Contributor

austinabell commented Sep 22, 2021

As part of the revamp of collection types, I'll list the issues with the current version and how this new type will solve the issue.

Problems with near_sdk::collections::UnorderedMap:

  • Removing a value from the map requires re-writing entries not touched by the operation
    • Create a new bucket type, which maintains indices on removals not to require updating
  • There are two Vector types for the keys and values, which exaggerates the previous problem, but also requires multiple individual reads and writes
  • API does not match standard Rust map types
  • Inefficient for multiple access of the same key because it duplicates reads and deserializations
    • There are caching layers built into both inner data structures used already (Vector/Bucket(PR soon) and LookupMap)
  • Uses storage manually to store the indices of each key to the index in each Vector, hard to maintain and open to bugs
    • Only uses LookupMap, and the value will contain the index for the bucket.

So the data structure will look something like this (visualized in JSONish):

Bucket: ["key0", "key2", "key1"]

LookupMap: {
  "<key0hash>": (<key0value>, 0),
  "<key1hash>": (<key1value>, 2),
  "<key2hash>": (<key2value>, 1),
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant