1

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

|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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.