On the internet, I've come across this question:

Classify the Hashing Functions based on the various methods by which the key value is found.

with answers like

  • Direct method
  • Subtraction method
  • Modulo-Division method
  • Digit-Extraction method
  • Mid-Square method
  • Folding method
  • Pseudo-random method

which I find strange. I think I know a lot about hashing, but this is plain gibberish to me, could anybody explain?

1 Answer 1


They are methods of turning a hashcode into an index of the array that contains the values. Let's say you have a hashcode of 0x12345678. A very large number and you're unlikely to have an array of this size. If you do you can just do

Value = array[0x12345678];

And be done (direct method).

If you don't then you have a figure out a way to turn this value into one that fits the array size while trying to avoid too many collisions. The terms used are probably known by other names too, but for example you could just mask off the higher bits of the hashcode

Value = array[hashcode & 0xffff];

Or mod the hashcode against the array size

Value = array[hashcode % array.size()]; // modulo division

Etc etc

Edit: this link may help

  • Thanks, that's it - the link seems to be the source of this ***. It still makes no sense as they're mixing many things together: 1. computing the hashCode from a key (e.g., fold and add), 2. improving (=smearing) the hash (e.g., mid-square), 3. mapping the hash to the index (e.g., modulus, "&").
    – maaartinus
    Commented Dec 31, 2012 at 4:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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