1
$\begingroup$

I need to process queries to Hash various ranges of a character array. I am currently using the Arrays.hashCode from the standard java library. But the problem is that this method is too slow. Also my array remains the same throughout the process of hashing, I only am changing the range. To deal with this, I have to make an entire copy of the array everytime I process a query, and then compute the hash from the above function.

I am using Arrays.copyOfRange to create a copy everytime I process a query. I need to avoid this. So I was thinking of devising a hashing scheme of my own. This scheme should be such that I whould get a unique hash for each array range. Hashes should be same if all characters in the range are same.

Any Help on how to proceed with the making of such a hash function will be appreciated.

$\endgroup$
  • $\begingroup$ So hash yourself. Is that a problem? $\endgroup$ – Karolis Juodelė Dec 11 '13 at 12:22
  • $\begingroup$ @KarolisJuodelė had that not been a problem, I wouldn't have posted this. $\endgroup$ – Alice Dec 11 '13 at 12:41
1
$\begingroup$

Use a rolling hash function, such as the Rabin-Karp hash. This allows you to compute hashes of any subrange of $A$ very efficiently, e.g., in $O(1)$ time, assuming you use some extra memory to keep track of all of the intermediate states of the rolling hash.


If $A[0..n-1]$ is your array, a rolling hash defines the hash of the entire array using a recurrence like this:

$$x_i = f(x_{i-1}, A[i])$$

where $x_{-1}$ is some fixed constant and $f$ is some function. Now here's what you can do. You can store the $x$ values in an array $X[0..n-1]$ (where $X[i]=x_i$). This will allow you to compute the hash of any prefix of $A$.

If you want to be able to compute the hash of any consecutive range of $A$, choose the function $f$ carefully to be reversible.


A simple instantiation: let $X[-1] = 0$ (for some constant $c$) and

$$X[i+1] = \alpha \cdot X[i] + A[i] \bmod 2^{32},$$

where $\alpha$ is some 32-bit constant (you'll want it to be odd). Preprocess the array $A$ once to compute the array $X[0..n-1]$.

Now, the hash of $A[i..j-1]$ can be very efficiently computed: it is the following:

$$X[j-1] - \alpha^{j-i} X[i-1] \bmod 2^{32}.$$

Notice that $\alpha^{j-i} \bmod 2^{32}$ can be computed efficiently using fast exponentiation algorithms, i.e., repeated squaring modulo $2^{32}$. Thus, assuming you've stored the array $X$ alongside the array $A$, a hash of any range of $A$ can be done in $O(1)$ time.


If you want something even simpler and easier to implement, set $\alpha$ to 1. Then the hash of $A[i..j-1]$ just becomes $A[i]+ A[i+1]+ \cdots + A[j-1]$, and $X[i]$ stores $A[0] + A[1] + \cdots + A[i]$, so the hash of $A[i..j-1]$ is just $X[j]-X[i]$.
However, the quality of this hash degrades and you might see an increase in hash collisions.

$\endgroup$
0
$\begingroup$
int hash = 0;
for (int i = range_start; i < range_end; i++)
    hash = hash*31 + your_array[i];
$\endgroup$
  • 1
    $\begingroup$ Since questions with code are off-topic here at CS:StackExchange, answers with code are unexpected. Even so, the answer should include an explanation of how it solves the problem in the question. $\endgroup$ – Guy Coder Dec 11 '13 at 14:40
  • $\begingroup$ that would have been a good approach, had I had a small array. But since I was talking of performance improvement, the is very large (of the order of 1e5). So I dont think this approach will be good enough (It is still linear, which was the case before). Thanks anyways. $\endgroup$ – Alice Dec 11 '13 at 15:53
  • $\begingroup$ Is that a good hash function? Why? What makes it better than any other function you could have chosen? Also, @Alice, I don't think 100,000 elements is particularly large -- it's not even a megabyte of data. $\endgroup$ – David Richerby Dec 11 '13 at 16:36
  • $\begingroup$ @GuyCoder, I've already voted the question as off topic and now answered it as I would in stack overflow. $\endgroup$ – Karolis Juodelė Dec 11 '13 at 17:09
  • $\begingroup$ @Alice, from the question gathered that your problem was cloning the required range for every hash. Have you actually tried this and saw no improvement? $\endgroup$ – Karolis Juodelė Dec 11 '13 at 17:14

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