Other [B4X] Quiz #7 - hash hash

Erel

B4X founder
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:

Erel

B4X founder
Staff member
Licensed User
Is it the speed gain by searching on INT instead of STRINGs that this method is being used?
Not exactly.
The hash number is used to directly find the relevant bucket. (Almost) no searching is done. The average complexity of hash table is O(1) unlike the complexity of searching a list which is O(n).

D is inefficient because the base number 5338 is not prime.
I don't think that it will be inefficient because of this. You can make a test and check the number of collisions.
I tried to confuse by lowering the case of the key. This of course doesn't make the hash table case insensitive.
 
Upvote 0
Top