# Other[B4X] Quiz #7 - hash hash

#### Erel

##### B4X founder
Staff member
Longtime 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
Longtime 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
Longtime 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)

#### Erel

##### B4X founder
Staff member
Longtime User
True.
Forget from nulls. A string shouldn't be set to null.

#### udg

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

#### LucaMs

##### Expert
Longtime 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:

#### Erel

##### B4X founder
Staff member
Longtime User
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

##### Expert
Longtime 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.

Longtime User
A No
B No
C No
D No

#### OliverA

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

#### LucaMs

##### Expert
Longtime 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
Longtime User
(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

##### B4X founder
Staff member
Longtime User
All the answers above are wrong. Try it and you will see.

Longtime User

#### Erel

##### B4X founder
Staff member
Longtime User
I'm sorry but I wasn't clear. No one has yet to give the correct answer...

#### Erel

##### B4X founder
Staff member
Longtime User
What is the single task of the hash value? How is it used?

#### sorex

##### Expert
Longtime User
A no
B no
C yes
D yes

?

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

#### Star-Dust

##### Expert
Longtime 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
Longtime User
C is the only wrong one. It has no consistent output.

Replies
43
Views
79K
Android Code Snippet [B4X] RSA Encrypt and Decrypt
Replies
3
Views
5K
Replies
9
Views
5K
Replies
1
Views
3K