3
$\begingroup$

I'm wondering whether there exist any good hash functions with the following property: Assume that $x$ is some string over some alphabet $A$, then given $H(x)$ we can compute in $O(1)$ time both $H(ax)$ and $H(xa)$ for any letter $a\in A$. In practice one can assume that $A$ is for example the set of $8$-bit integers.

In other words, a hash function for strings that can quickly be extended in both directions. I'm only interested in hash functions that actually distribute the data well and which are very fast to compute in practice.

$\endgroup$
2
  • $\begingroup$ If you track the length of the input, the Java String.hashCode() function has this property. While it is indeed very fast to compute in practice, it is rather more debatable whether it distributes the data well. $\endgroup$ – Aaron Rotenberg Dec 9 '19 at 15:24
  • $\begingroup$ @Littlish I think your edit actually changed the meaning of the first sentence here. The question wasn't whether there exists a well-known hash function with this property, but whether existed a known hash function with this property that is also good, i.e. has desirable distribution properties such as avalanche effect. $\endgroup$ – Aaron Rotenberg Jan 10 '20 at 17:14
2
$\begingroup$

Use any rolling hash, e.g., the Rabin-karp rolling hash, Buzhash, or CRC. See also the following resources:

$\endgroup$

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.