Other [B4X] Quiz #7 - hash hash

[Erel]

I've implemented a hash table / map as part of the "teachers examples": https://www.b4x.com/android/forum/threads/?‍?-?‍?-examples-for-teachers-algorithms.115894/post-724991

The keys are strings and there is a sub that calculates their hash code.

Which of the following alternative hashes will work properly and which won't:


A.

Private Sub CalcHash (key As String) As Int
  Return key.Length
End Sub

B.

Private Sub CalcHash (key As String) As Int
  Return -5
End Sub

C.

Private Sub CalcHash (key As String) As Int
    Dim h As Int = Rnd(0, 1000)
    For i = 0 To key.Length - 1
        h = Bit.ShiftLeft(h, 5) + h + Asc(key.CharAt(i))
    Next
    Return h
End Sub

D.

Private Sub CalcHash (key As String) As Int
key = key.ToLowerCase
  Dim h As Int = 5338
    For i = 0 To key.Length - 1
        h = Bit.ShiftLeft(h, 5) + h + Asc(key.CharAt(i))
    Next
    Return h
End Sub

 

[LucaMs]

At the moment I don't know, but this is a "mistake":

Dim h As Int = 5338
Dim h As Int = Rnd(0, 1000)

?

Spoiler: Thinking...

Just by intuition, since you added the D (and ToLowerCase)... I suppose you might have problems with the Asc function with some characters.

 

[Erel]

Oops. I mistakenly left that line in option D. Fixed now.

Quiz is still open. Developers you should know how Map works. If not check that example: https://www.b4x.com/android/forum/t...es-for-teachers-algorithms.115894/post-724991

 

[udg]

Correct me if I am wrong

h = Bit.ShiftLeft(h, 5) + h + Asc(key.CharAt(i))

is like

 h = (h * 33) + Asc(key.CharAt(i))

Other points I'd like a confirmation about:
an int is 32 bit
the Asc function returns a 32 bit value since it expects a unicode char (so no limits on how the string is formed)
a null string is automatically corrected to the string "null" (with or without quotation marks, I can't recall exactly)
the algorythm which will use the hash function accounts for collisions (I didn't look at the code yet)

 

[Erel]

is like

True.
Forget from nulls. A string shouldn't be set to null.

 

[udg]

Ok. I'm not there yet, but is starts to sound like a polynomial with powers of 32

 

[LucaMs]

Quiz is still open. Developers you should know how Map works. If not check that example: https://www.b4x.com/android/forum/threads/?‍?-?‍?-examples-for-teachers-algorithms.115894/post-724991

If you are referring to this (in that post):

Quiz: what will happen if we change CalcHash to always return 5 ? Will it work properly?

If CalcHash returns a non-unique "key", when you use the Set method you will replace an already existing key/value. However, this does not mean that the 4 routines are wrong, unless it is assumed that CalcHash must always return a unique value, never repeated.

 

[Erel]

Luca this is a yes or no question. For each one of the four methods you should say answer whether the custom Hash Table or Map will work properly or not.

 

[OliverA]

A No
B No
C No
D Yes *
* Yes, just note that keys are case insensitive
* Yes as a pure guess, since I'm assuming that the calculation used is good enough to keep collisions rare as to make this usable. I don't have the math skills to proof that one way or the other, so I'm just guessing.

 

[LucaMs]

A No
B No
C No
D No

 

[OliverA]

D No

A guess or you're really good with math? Or is it the lower casing of the string? (I admit, I'm guessing)

 

[LucaMs]

A guess or you're really good with math? Or is it the lower casing of the string? (I admit, I'm guessing)

D:
H is a fixed number, therefore words of equal length, the final value of only H, not taking into account Asc (), will have equal values.
I mean that for Talk and Walk you would have a fixed value of H (always not considering Asc ()).

Asc() does not take into account the position of the letters, so for two words that contain the same letters (anagram) the hashes will be identical
(Team and Mate will have the same hash code).

 

[OliverA]

(Team and Mate will have the same hash code).

Nope:

2039760993
2039505697

fixed value of H

The only fixed H value is the initial value. It constantly changes then in the loop. And at that point, each ASC value affects it and the position is important due to the multiplication (the shifting).

 

[Erel]

All the answers above are wrong. Try it and you will see.

 

[OliverA]

All the answers above are wrong

A No
B No
C No
D No

Now I'm jealous

 

[Erel]

I'm sorry but I wasn't clear. No one has yet to give the correct answer...

 

[Erel]

What is the single task of the hash value? How is it used?

 

[sorex]

A no
B no
C yes
D yes

?

(it depends for what purpose the hash is being used)

 

[Star-Dust]

I'm sure one is correct

Solution 01: A: No; B: No; C: No; D: No; (already excluded by erel)
Solution 02: A: No; B: No; C: No; D: Yes; (already excluded by erel)
Solution 03: A: No; B: No; C: Yes; D: No;
Solution 04: A: No; B: No; C: Yes; D: Yes;
Solution 05: A: No; B: Yes; C: No; D: No;
Solution 06: A: No; B: Yes; C: No; D: Yes;
Solution 07: A: No; B: Yes; C: Yes; D: No;
Solution 08: A: No; B: Yes; C: Yes; D: Yes;
Solution 09: A: Yes; B: No; C: No; D: No;
Solution 10: A: Yes; B: No; C: No; D: Yes;
Solution 11: A: Yes; B: No; C: Yes; D: No;
Solution 12: A: Yes; B: No; C: Yes; D: Yes;
Solution 13: A: Yes; B: Yes; C: No; D: No;
Solution 14: A: Yes; B: Yes; C: No; D: Yes;
Solution 15: A: Yes; B: Yes; C: Yes; D: No;
Solution 16: A: Yes; B: Yes; C: Yes; D: Yes;

 

[OliverA]

C is the only wrong one. It has no consistent output.