Hash-Map vs LL

[Nik]

One Debug says more then 1000 words

Code: Select all

Structure pair
Key.s
Value.l
Belegt.b
EndStructure

start=ElapsedMilliseconds()

Global Mapsize.l=100000
Global Dim map.pair(Mapsize+1);

Procedure.l GetHash(InKey.s);
Protected hash= CRC32Fingerprint(@InKey,StringByteLength(InKey))%mapsize
ProcedureReturn Abs(hash)
EndProcedure

Procedure Add(Key.s, Value.l)
Protected Hash.l
Hash=GetHash(Key.s)
Repeat
 If map(hash)\Belegt=#False
  map(hash)\Key=Key
  map(hash)\Value=Value
  map(hash)\Belegt=#True
  ProcedureReturn 
 Else
  hash=(hash+1)%mapsize
 EndIf
ForEver
EndProcedure 

Procedure Get(Key.s)
Protected Hash.l
Hash=GetHash(Key.s)
Repeat
  If map(hash)\Belegt=#False
    ProcedureReturn 0
  ElseIf map(hash)\key=key
    ProcedureReturn map(hash)\Value 
 Else
  hash=(hash+1)%mapsize
 EndIf
ForEver
EndProcedure

For k = 0 To 9000
  Add(Str(k),k)
Next

For k = 0 To 9000
  Get(Str(k))
Next

Debug ElapsedMilliseconds()-start

;-----------------------------------------------------

start=ElapsedMilliseconds()
NewList test.pair()

For t = 0 To 9000
  AddElement(test())
  test()\value=t
  test()\key=Str(t)
Next

For t = 0 To 9000
  S.s=Str(t)

  ForEach test()  
    If test()\key=S
      Break
    EndIf
  Next
Next

Debug ElapsedMilliseconds()-start

[akj]

Nik, You say

One Debug says more then 1000 words

I say

One comment line says more then 1000 Debugs

[Joakim Christiansen]

I say

One comment line says more then 1000 Debugs

I second this!

[thefool]

with debugger: first is 112 times faster
without debug: first is 38 times faster

Never speed test with debugger.
I like the simple example though, and the speed is STILL improved a lot!

[Konne]

Here is your explanation:
http://en.wikipedia.org/wiki/Hash_table

I think the code is so trivial (and the procedure and Variable names are so good) that it should be easy to understand even without comments.

Awesome example thx

One comment line says more then 1000 Debugs

Oh and thx to Niks C++ style typing there are many comment lines.

[blueznl]

... but what is it supposed to do?

[Konne]

Storing data efficiently in tasks of searches.

[Froggerprogger]

...but the comparison is like "apples vs. pears"...
These data-structures do have totally different qualities, as well as arrays, trees, stacks or heaps do have their individual pro and contra.

...anyway: Nice small hashmap-example.