CODEWITHSUNDEEP
arraysstringfunctionhashkey
alextoind
alextoind

Reputation: 1203

Array of strings as hash function key?

Is it possible, in any language (it doesn't matter), to have a hash function which uses an array of strings as keys?

I mean something like this:

hash(["word1", "word2", ...]) = "element"

instead of the classical:

hash("word") = "element"

I need something like that because each word I would like to use as key could change the output element of the function. I've got a sequence of words and I want a specific output for that sequence (also the order may change the result).

Upvotes: 7

Views: 4816

Answers (2)

Gene
Gene

Reputation: 47010

Sure. Any data structure at all can be hashed. You only need to come up with a strict definition of equality and then ensure that hash(A) == hash(B) if A == B. Suppose your definition is that [s1, s2, ..., sm] == [t1, t2, ..., tn] if and only if m == n and si == ti for i = 1..m and further string s == t if and only if |s|==|t| and s[i]==t[i] for 0<=i<|s|. You can build a hash in a many, many ways:

  • Concatenate all the strings in the list and hash the result with any string hash function.
  • Do the same, adding separators such as commas (,)
  • Hash each string individually and xor the results.
  • Hash eash string individually, shift the previous hash value, and xor the new value into the hash.
  • Infinitely many more possibilities...

Tigorous definition of equality is important. If for example order doesn't matter in the lists or the string comparison is case-insensitive, then the hash function must still be designed to ensure hash(A) == hash(B) if A == B . Getting this wrong will cause lookups to fail.

Java is one language that lets you define a hash function for any data type. And in fact a library list of strings will work just fine as a key using the default hash function.

HashMap<ArrayList<String>, String> map = new HashMap<ArrayList<String>, String>();

ArrayList<String> key = new ArrayList<String>();
key.add("Hello");
key.add("World");

map.put(key, "It's me.");
// map now contains mapping ["Hello", "World"] -> "It's me."

Upvotes: 4

Hisham
Hisham

Reputation: 442

Yes it is possible, but in most cases you will have to define your own hash function that translates an array into a hash-key. For example, in java, the array.hashCode() is based on the Object.hashCode() function which is based on the Reference itself and not the contents of the Object.

You may also have a look at Arrays.deepHashCode() function in java if you are interested in an implementation of a hashing function built on top of an array.

Upvotes: 1

Related Questions