Hash function for string with complexity O(N)

One simple algorithm could be:

int x = 0;
int s = 0;
for each character c in the string str
{
 x = x ^ c
 s = s + ASCII value of c
}

hash(str) = x + s

Collisions Handling

The reason I added the value s in the final answer is because suppose we have two strings s1 = "ab" and s2 = "ef", they would result in a collision just by xor operation,however after we add the value of sum of their ASCII values, they do not result in collision.

The xor operation also helps to avoid collision when sum of ASCII values of the characters is same. Suppose we have s1 = "ad" and s2 = "bc". By only considering the sums of ASCII values, it would result in collision but after the considering the xor operation as well it does not.

Also for strings of even length like "aaaa" and "bbbb" , if we only consider the xor operations, still we have collision but by adding the sums of ASCII values, we can avoid the collision.

So combining the sum of ASCII values of characters of the string and the xor operation, collision can be handled to a larger extent.

Well, you could do it like this, in C# :

string text = "abc";
int hash = 0;

foreach(char c in text)
{
  int value = (int)c;
  hash += value;
}

The distribution of the hash value won't be great, but it does the job.

UPDATE: Since you've mentioned that the alphabet just consists of A-Z and a-z then another option is to map their position in the alphabet to bits in a long, with the uppercase characters taking up the first 26 bits and the lower case characters taking up the next 26 bits:

long MakeHash(string text)
{
    long hash = 0;
    long numberOfCharacters = 0;

    foreach(var c in text)
    {
        int offset = 0;

        if(c >= 'A' && c <='Z')
        {
            offset = c - 'A';
        }
        else
        {
            offset = (c - 'a') + 26;
        }

        hash |= (1L << offset);

        numberOfCharacters++;
    }

    hash |= (numberOfCharacters << 52);

    return hash;
}

Note how at the end the number of characters is OR'd into the bits 52 and beyond. Without this strings like aa and aaa would map to the same value as they'd all just set the a bit. With the length combined into the value you get a different value.

This sounds like you want the hash of a multiset. If there are no other requirements, such as fast recalculation for substrings or concatenation, you can just do the following:

1. Build some canonic representation of the multiset as a string: a string which is the same for every object you consider the same, and different for objects you consider different. For that, just sort the characters of the string. For a small alphabet (English only? ASCII?), this can be done with counting sort in O(N) time and O(|A|) memory where A is the alphabet: just calculate in a single pass how many of each letter you have. Admittedly, this won't go so well for larger alphabets, as you'll need a usual sort with O(N log N) time complexity.

2. Now, just calculate the usual polynomial hash of the string you got. That is, for a string S = s₀s₁...s_n-1, the hash is s₀p^n-1 + s₁p^n-2 + ... + s_n-1p⁰ mod q for some primes p and q. From the array of size |A| where you store how many of each letter was there, you can construct the sorted string on-the-fly, thus not needing an additional O(n) space for it. This step works in O(n + |A|).

If the O(N) requirement doesn't matter too much, here's what I propose : sort the string, then use a native hash method :

char[] characters=inputString.toCharArray();
Arrays.sort(characters);
return new String(characters).hashCode();

As Alper commented, this is a O(N * log(N)) solution due to the sort complexity.

Here's a Java ideone to test it.

If the O(N) requirement is important but collision isn't, you can just use any commutative operation, for example addition of the char values. The problem with that example solution is that you'll end up with the same result for "bc" and "ad", or "abb" and "aac".

With Aggregation of the hashcodes of the chars, the order would not matter. e.g.:

var hash = text.Aggregate(text.Length, (h,c) => h | c.GetHashCode()); //NB "aab" == "bba"

Base is text.Length, so "aaa" != "aa" etc. But this still results in "aab" == "bba".

Instead of | other variations are possible, such as XOR, but then "aa" == "bb" (because the result would be 0).

Perhaps reoccurring chars is not a problem (?) , otherwise ordering or grouping the chars is needed. Easiest would be to create a new string with the ordered chars, but that is heavier on processing/memory. To order by and aggregate in one go, this could work:

var hash = text.OrderBy(c=>c).Aggregate(text.Length, (h,c) => (h << 1) ^ c.GetHashCode());

(The hash << 1 is to make sure "aab" !== "abb") But more efficient versions could be made if there are strict rules on the possible permutations. Not completely O(n) of course. You could come closer to O(n) with counting occurrences (collisions) of the same hash (char), but I reckon the branching that causes, would imply a heavier hit on performance.

1. Compute the sums s1, s2, ..., sn of each of the n possible input symbols in your string
2. Consider the unary (base 1) representations thereof: u1, u2, ..., un. We'll take the unary representation of a number n to be the string 0^n.
3. Construct a binary string hash = (u1)1(u2)1...1(un)
4. Interpret hash as the binary representation of a number of string and use a hash with your properties

If x and y have the same number of symbol k, then uk will be the same; and if this is true for all 1 <= k <= n then the hashes must be the same. It is also easy to show that strings that have different counts will have different hashes.

How big are these hashes? When the total number of symbols in the input is zero, the output is 1^n of length n bits. When you add a symbol to the input, one count increases by one, one unary representation increases in length by 1, and the overall size of the hash increases by one bit. So an input string of length m will have length m+n bits.

This algorithm is O(m+n) time and space where n is the fixed number of input symbols and m is the number of elements in the input string.

EDIT: An example would help.

Say that the input alphabet is A = {a, b, c, d, e}. We impose an ordering on the set to get the sequence L = (a, b, c, d, e). So L(0) = a, L(1) = b, etc. Now we want to hash the following two strings: abcd and bcda.

We record the partial sums in unary (note that the result is the same for both strings):

u1 = 0
u2 = 0
u3 = 0
u4 = 0
u5 = (empty)

We construct the hash as follows: (u1)1(u2)1(u3)1(u4)1(u5)1 = 010101011.

So the hash of both strings is equal to 171 when the output of the above procedure is interpreted as the binary encoding of an integer. If interpreted as a string over the input alphabet of size 5, 171 = 1*125 + 1*25 + 4*5 + 1*1 and thus we can encode it as bbeb. To be explicit, we are considering the input alphabet to be digits of a base-5 encoding of numbers where the digit x is equal to x's place in the ordering of the alphabet. So a = 0, b = 1, c = 2, d = 3, e = 4. The number bbeb is therefore equal to 1*5^3 + 1*5^2 + 4*5^1 + 1*5^0 = 125 + 25 + 20 + 1 = 171.

One might object that this is going to produce a hash that is similar in length to the input. If you want one that's fixed length, just run a hash on the output of this one that has the properties you want. Then the composition will be a hash function that you like.