11
\$\begingroup\$

Assume the built-in function Ascii(c), where c is a one character string, will return an integer containing the ASCII value of that character. Write a function that accepts a string, uses Ascii(c) and additional processing to produce a one way hash value from the string, and returns the hash value as a string. You may assume the initial string is not empty and contains several characters.

//one way hash using ascii
static string hashViaAscii(String S)
{
    int hashVal = 0;     

    for (int k = 0; k < S.Length; k++)
        hashVal += Ascii(S[k]);  //gets Ascii value, add them all

    return ((hashVal % HASH_TABLE_SIZE).ToString());  //return sum % table size as string
}

I don't think is a good approach. How can this be improved?

\$\endgroup\$
  • 4
    \$\begingroup\$ I just rolled back that edit because it made the question off-topic for the site. You need code for a code review. Plus since you already have answers, you shouldn't be substantively changing the question \$\endgroup\$ – Ben Aaronson Apr 14 '16 at 7:34
  • 3
    \$\begingroup\$ It's trivial to construct an input for any given output. So this is not a one-way function. \$\endgroup\$ – CodesInChaos Apr 14 '16 at 8:51
23
\$\begingroup\$

I'm confused by the phrase “one way hash value” and so is probably whoever specified this requirement. In cryptography, a one-way hash function has a well-defined meaning.

Let \$\Sigma\$ be an alphabet, for example, \$\Sigma=\{\mathtt{0}, \mathtt{1}\}\$. A family of functions \$(f_k)_{k\in\mathbb{N}}\$ with $$f_k: \Sigma^k \times \Sigma^* \to \Sigma^k$$ is a family of one-way hash functions if and only if for each \$k\in\mathbb{N}\$, the \$f_k\$ is computable by a polynomial-time algorithm and for every probabilistic polynomial-time algorithm \$\mathcal{A}\$, given random \$K\in\Sigma^k\$ and \$h\in\Sigma^k\$, the output \$m^*=\mathcal{A}(K,h)\$ will satisfy \$f_k(K,m^*)=h\$ only with probability negligible in \$k\$.

\$K\$ is called key or salt. It should be chosen randomly but need not be kept secret.

It is unknown whether such functions exist at all but there are some functions for which it hasn't been proved yet that they are not one-way functions.

If your function should compute such a cryptographic hash, I recommend that you look into one of the existing cryptographic hash function even though I doubt that you're supposed to implement one of these. (Although returning the result as a string would be meaningful in this context because for \$k>64\$, you usually cannot return the hash as an integer.) MD5 and SHA1 are two classical examples of cryptographic hash functions that are reasonably straight-forward to implement. The collision resistance (which is a stronger requirement than the one-way property) of both of them is known to be broken in theory. (Both are also only specified for fixed \$k\$ which means that the above definition doesn't really apply.)

Since I see the word “hash table” in your code, I suspect that instead of a cryptographic hash function, they wanted to see a “simple” hash function that is fast to compute and has low probability of collisions but is not collision-resistant against malicious attackers. Again, have a look at algorithms other people already invented.

  • The Fowler-Noll-Vo hash function gives good hashes and is easy to implement. It can also be parametrized on the length of the result. I would recommend the FNV-1a variant as your go-to hash function unless you have reasons to chose differently.
  • Jenkins' one-at-a-time hash function is equally easy to implement and will probably be faster because it only uses additions and bit-wise operations as opposed to multiplications.
  • Weinberger's PJW hash function is known for its use in the UNIX ELF format and for being mentioned in the Red Dragon Book.
  • The lose-lose hash function is the one you've actually implemented. It's name should give you a hint. To your rescue, it was once used as an example by Kernighan and Ritchie.

There are numerous other hash functions and the literature / internet is full of comparisons between them. As you can imagine, while there are clearly better and less good functions available, there is also a lot of personal preference involved in deciding which function to use.

Even if you're planning to use the hash as index for a hash table, don't take the hash modulo the table size in the hash function itself. This will needlessly limit its usefulness. Whoever uses the function should be responsible for wrapping the computed hash into the table size.

\$\endgroup\$
17
\$\begingroup\$

There are some issues with this function, some of them resulting from the fact that the task to be performed was poorly conceived to begin with.

  • The statement of the problem says that Ascii takes a "one character string". You give it a character, not a one-character string. Note that the Ascii function is completely unnecessary: a character in the ASCII range is already a number representing its ASCII code.

  • The statement of the problem says that the function returns a string. You do that, but boy, that does not make good sense. Why on earth would you return a number as a string when you could return it as a number???

  • It's not the 1970's anymore. Stop thinking that strings contain ASCII. They contain Unicode.

  • "You may assume the initial string is not empty and contains several characters." Whoever posed the problem forgot that strings can be null.

  • Who said anything about a hash table size in the statement of the problem? This comes out of nowhere.

  • Good hash functions produce different values when given inputs are the same characters in a different order. Your hash function produces the same output for "12345", "54321", "51234", and so on. I made that mistake in a hash function once; the function was used to hash zip codes, and so of course most of them hashed to the same buckets. That was bad.

  • C# uses PascalCase for function names and magic constants. SHOUTY_SNAKE_CASE is for C programmers and Java programmers.

  • C# uses lowercase for formal parameters.

I am thinking based on the incredible badness of the way the question is phrased, that whoever is posing you this question may not be an expert on C#. Consider taking a course from someone who is an expert on the subject matter.

\$\endgroup\$
  • \$\begingroup\$ Well I do come from C background. Question says that Ascii function returns integer, but the hash function returns a value as string. How would I modify it to have a good hash function? \$\endgroup\$ – david Apr 14 '16 at 3:53
  • \$\begingroup\$ Would +2 if I could for "SHOUTY_SNAKE_CASE is for Java programmers". Also the tone is ok IMHO since he does not attack the "unknowing" asker. \$\endgroup\$ – Sebb Apr 16 '16 at 17:08

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.