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.

  • $\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$ Jun 6, 2017 at 14:57

1 Answer 1


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

  • $\begingroup$ and how is the hash updated? $\endgroup$
    – miracle173
    Jun 7, 2017 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$ Jun 7, 2017 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, 2017 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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