Other [B4X] Quiz #7 - hash hash

Erel

Administrator
Staff member
Licensed User
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.
B4X:
Private Sub CalcHash (key As String) As Int
  Return key.Length
End Sub
B.
B4X:
Private Sub CalcHash (key As String) As Int
  Return -5
End Sub
C.
B4X:
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.
B4X:
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
 
Last edited:

LucaMs

Expert
Licensed User
At the moment I don't know, but this is a "mistake":
Dim h As Int = 5338
Dim h As Int = Rnd(0, 1000)
😄

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

udg

Expert
Licensed User
Correct me if I am wrong
B4X:
h = Bit.ShiftLeft(h, 5) + h + Asc(key.CharAt(i))
is like
B4X:
 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)
 

udg

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

LucaMs

Expert
Licensed User
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.
 
Last edited:

OliverA

Expert
Licensed User
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.
 

OliverA

Expert
Licensed User

LucaMs

Expert
Licensed User
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

Expert
Licensed User

sorex

Expert
Licensed User
A no
B no
C yes
D yes

?

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

Star-Dust

Expert
Licensed User
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;
 
Last edited:

OliverA

Expert
Licensed User
C is the only wrong one. It has no consistent output.
 
Top