up vote 1 down vote favorite

What data structure would be best choice for fast and performant bidirectional SHA-1 to SHA-3 mapping? Or in other words fixed-length string to fixed-length string mapping?

To be more precise:

  1. There exists a set of data (which might count in mega-objects), over each of which SHA-1 and SHA-3 hash of is taken
  2. For given SHA-1 we want to know if object (data) exists, and its SHA-3 hash function
  3. For given SHA-3 we want to know if object (data) exists, and its SHA-1 hash function

The set of data is not immutable, but one can assume that only new data would be added.

Most important is fast query and low overhead; the modification may perform slower. It would be good if it could perform lock-less updates. Updates (append only) are much rare than queries, and only need to perform below human reaction time.

Background: one of proposals of moving Git away from SHA-1 requires fast SHA-1 to SHA-3 (or to whatever hash is chosen to replace broken SHA-1).

See it here: RFC: Another proposed hash function transition plan

share|improve this question
  • 1
    This is basically just a poll about how to move away from SHA-1. Furthermore, the answer(s) depend a massive amount on the various constraints, such as needing atomic operations, persistence, performance, etc. – DeadMG Mar 5 '17 at 20:30
  • This question is meant to find out what solutions are possible, and thus if the referenced plan is feasible given constraints Git must work under. I have added a bit of clarification. – Jakub Narębski Mar 5 '17 at 20:34
  • 2
    You are describing a database. In relational terms, you want a table representing an 1:1 mapping with an index over both columns. I'm sure there's plenty of R&D into database engines that you could look at for inspiration. The requirements you mention aren't particularly extraordinary. – amon Mar 5 '17 at 20:49
  • So, in other words, if the database with indices approach is a good one, the question is what data structures RDBMS uses for fast indices? On the other hand RDBMS must be more generic, thus less performant than possible. – Jakub Narębski Mar 5 '17 at 20:51
  • 2
    I doubt you'll find something much better than two hash-tables, one for each direction. Of course to populate it you need to rehash the original data. – CodesInChaos Mar 5 '17 at 21:04

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.