0
$\begingroup$

Is there a way to support adding characters in the middle and update the hash in O(1) ? All I have is the hash of ABBDE and I want to get the hash of ABBCDE.

$\endgroup$
  • $\begingroup$ Hashes are usually designed so that making a small change has a huge random-like effect on the output. You can design your own hash function that doesn't suffer from this, but it will likely be not very good for many applications. For example, you can XOR all characters. $\endgroup$ – Yuval Filmus Jun 6 '17 at 14:57
2
$\begingroup$

With just the Rolling HASH for the whole ABBDE, you can not insert into the middle of it.

But... as I understand rolling Hash...

If you are building the hashes up as you go (adding into the middle, adding other entries), you would need a little extra information to be able to insert into the middle at a latter access.

As I see it , You need need to know:

A) The whole hash (I assume you got by finding the entry there)
B) The hash for one of the halves (Left or Right)
C) A length of the HALF to know the offset that needs to be adjusted by.
D) An indicator to know which half is being adjusted to keep the halves balanced.`

Then all the parts can be used to recalculate, updated, replaced, and inserted to make new entries.

This would then give an O(1) time

BTW, what is this for?

The answer to another question with a related general solution: Finding Hash of Substring [i, j] in O(1) using O(|S|) pre computation

$\endgroup$
  • $\begingroup$ and how is the hash updated? $\endgroup$ – miracle173 Jun 7 '17 at 3:40
  • $\begingroup$ I suggest an internet search rolling hash explained And I suggest an internet search for: add remove hash table entry $\endgroup$ – Phillip Williams Jun 7 '17 at 13:26
  • $\begingroup$ I don't think I will find your method to calculate the new hash already by google as long as you don't add it to this post $\endgroup$ – miracle173 Jun 7 '17 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.