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

Hash code conflict in LRUCache #1352

Closed
flowbehappy opened this issue Jan 14, 2021 · 0 comments · Fixed by #1852
Closed

Hash code conflict in LRUCache #1352

flowbehappy opened this issue Jan 14, 2021 · 0 comments · Fixed by #1852
Assignees

Comments

@flowbehappy
Copy link
Contributor

Currently, MarkCache and MinMaxIndexCache use LRUCache to manage the mapping. We hash the file path into UInt128, so that it is easy to use an unordered_map. Although it is efficient, the hash algorithm can still have chances of conflicts. i.e. two different paths share the same hash_code. We cannot tolerate the conflict, because it will cause data error or exceptions.

Instead of relying on hash code, we can use std::map<Path, Value>. In sacrificing some efficiency, we gain correctness.

@flowbehappy flowbehappy self-assigned this Jan 14, 2021
@flowbehappy flowbehappy changed the title Fix MarkCache and MinMaxIndexCache Hash code conflict in LRUCache Apr 29, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant