GATE IT 2006 | Question: 20

Question

Which of the following statement(s) is TRUE?

1. A hash function takes a message of arbitrary length and generates a fixed length code.
2. A hash function takes a message of fixed length and generates a code of variable length.
3. A hash function may give the same hash value for distinct messages.
   • A. I only
   • B. II and III only
   • C. I and III only
   • D. II only

Comments

The first two statements of this question belong to

Computer networks(Cryptographic Hash Functions).

so don't get confused.

---

I dont think that this is in syllabus now

---

Isn’t taking a message of arbitrary length and and generating a fixed length code(key) is known as pre-hashing ? Hashing is mapping a key to one of the bucket or location of a table . So in theory in a universe of key , every key is distinct and every distinct message will have distinct key?

---

consider linear probing , it takes h(k)  of any length but generates hash slot of same length I is true

III is basic hashing concept of collision.

---

Just one doubt in your statement what if hash table size is 110 then it generates hash slot of 3 different length i.e 1(0 to 9),2(10 to 99) and 3(100 to 109) .

---

but if number of slots in hash table is 0-9999 (let's suppose) then the hash function will generate a code of length 1 sometimes ,length 2 sometimes ,length 3 sometimes ,length 4 sometimes so isn't it depends on hash function and size of hash table ??

---

Fixed length in this context means fixed range i guess

Hash function always produces numbers within the particular range

---

i had the same doubt, answer to our doubt is 

The term "fixed length" refers to the number of bits or bytes the code(here hash value) occupies in memory, not the number of digits in its decimal representation.

---

Not in current syllabus of GATE CS

Answer 1

Answer is (C).

1. A hash function takes a message of arbitrary length and generates a fixed length code.. This is correct, this is directly from definition of hash function.   Ref: https://en.wikipedia.org/wiki/Hash_function
    
2. As I is correct II is wrong !
    
3. This is true. example: Hash function $N \%10$, this will generate same values for $1$ as well as $11$.

(Even in cryptographic hash functions collision happens, just that it is not easy to find colliding instances.)

Comments

but if number of slots in hash table is 0-9999 (let's suppose) then the hash function will generate a code of length 1 sometimes ,length 2 sometimes ,length 3 sometimes ,length 4 sometimes so isn't it depends on hash function and size of hash table ??

---

@sru12 what if the numbering of hash table cells is in $4$ digits like $0000,0001,0013..$?

---

. A hash function is a mathematical function that takes in an arbitrary string input and outputs a unique identifier of that string: H: {0,1}*{0,1}^k.
 

reference : https://web.stanford.edu/class/ee374/lec_notes/lec3.pdf
we can clearly see that we always have a fixed length output i.e k

Answer 2

for reference, hash function $f(x)$:
$$f(x) = x \text{ mod } 7$$

Statement I is true.
give hash function a number $x$ no matter big or small and it will map it to some fixed value(slot).

Statement III is true.
yes, it happens often that same number are mapped to same slots, giving rise to collisions in some cases.

Statement II maybe true.
we can code such a hash function too.

But since, I and III are given together as separate options then we choose option C as true.

Comments

Statement 1 can be made false if we take function as x%13. Then how’s it True?

---

but if number of slots in hash table is 0-9999 (let's suppose) then the hash function will generate a code of length 1 sometimes ,length 2 sometimes ,length 3 sometimes ,length 4 sometimes so isn't it depends on hash function and size of hash table ??

Answer 3

Option is C because

i) its right because we can get value of variable length which will be divided by Hash Table size in further steps

ii)Its wrong because we will get a fixed value by dividing the value by HTS

iii)Yeah it may be same that's  what we called collision

so i and iii is right

Answer 4

https://youtu.be/_sfJP26uf7U

Answer 5

Statement 1: Is correct

A hash function takes a message of arbitrary length and generates a fixed length code because it is working on method of (mod )

for example if we take (mod 10) then code will come in 0 ,1,2,3 …..up to 9 always so its give the fixed length 

statement 2: statement 2 is contrapositive of S1 so if s1 IS  true then 2 will be false

statement 3:a hash function may give the same hash value for distinct message

yes it may because its always generate fixed length so it will be possible 

Answer 6

I think answer is B.... Correct me if wrong

Comments

If you can plz tell how will it generate variable length code?

Answer must be C.

---

c is ans...

1. A hash function takes a message of arbitrary length and generates a fixed length code. by taking mod (some value)
2. A hash function may give the same hash value for distinct messages. true when mod 10 given to 44 and 4..same value come 4