Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

In several places on the Internet there's the interview 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?

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer
    
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 Dec 31 '12 at 4:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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