Map - search algorithm

[Josh]

I have no idea how the search algorithm of a map works. Wouldn't it be possible to find not only a complete search term, but also the beginning of a specific entry?

For example:

FindMapElement (MyMap (), "Pure", #AnyFlag)
would find 'PureBasic', if this is the first mapelement, which fits with my search term.

[PeterJ]

Simplistic description of MAPS: If you save/retrieve via a map key, it is translated via a hash routine in a real number, which is used to identify the storage location. As you can imagine the translation of the map key doesn't create a unique numer, there migth be collisions, which mean an alternative number must be built to save/locate the value. Practically it can be a multi stage process to find the real storage location of a map key and it's value.

Coming now to your question: is there a way to perform a "wildcard search" on map keys. The answer is no, because of the way maps are stored.

As I needed a "sorted Map", I created a couple macros which link to the MAP a LIST, which then can be sorted. With this you can access the MAP in a sorted way, which comes near your wildcard search request.
Maybe this helps you:

Code: Select all

; ----------------------------------------------------------------------------------------------
; Sorted MAP
; ----------------------------------------------------------------------------------------------
; to use Pointers in Macros it is sometimes easier to work with integers  
;        e.g. Global NewUniqueList(myUniqueLst)   
; ----------------------------------------------------------------------------------------------
CompilerIf #PB_Compiler_Processor=#PB_Processor_x86
 Macro ptr(pointer)   
    pointer.i
 EndMacro   
CompilerElseIf #PB_Compiler_Processor=#PB_Processor_x64
 Macro ptr(pointer)   
    pointer.q
 EndMacro   
CompilerElse 
 CompilerError "Neither x86 nor x64 Compiler"
CompilerEndIf 
;
; ----------------------------------------------------------------------------------------------
; Sort the Map, by sorting the associated LIST    
; Define SortedMap in any GLOBAL, DEFINE, PROTECTED definition as NewSortedMAP
; ----------------------------------------------------------------------------------------------
Macro NewSortedMap(MapName,maxItem=16000)
  MapName#MustbeSorted.b, NewList MapName#Sorted.s(), NewMap MapName.s(maxitem), NewMap ptr(MapName#BPTR)(maxitem)
EndMacro
; Structure Version as SortedMAP. 
Macro SortedMap(MapName,maxItem=16000)
  MapName#MustbeSorted.b 
  List MapName#Sorted.s()
  Map MapName.s(maxitem)
  Map ptr(MapName#BPTR)(maxitem)
EndMacro
;
; ----------------------------------------------------------------------------------------------
; Frees the Sorted Map (and its associated MAP and LIST)    
; ----------------------------------------------------------------------------------------------
Macro FreeSortedMap(Mapname)
  FreeMap(MapName())
  FreeMap(MapName#BPTR()) 
  FreeList(MapName#Sorted())
EndMacro
;
; ----------------------------------------------------------------------------------------------
; FOREACH type loop to retrieve the Sorted Map (via it's associated LIST)    
; ----------------------------------------------------------------------------------------------
Macro ForEachSortedMap(MapName)
  ForEach MapName#sorted()
EndMacro
;
; ----------------------------------------------------------------------------------------------
; Returns the active Sorted Map Element (to be used from within FOREACHSORTEDMAP)    
; ----------------------------------------------------------------------------------------------
Macro SortedMapElement(MapName)
   MapName(MapName#Sorted())
EndMacro
;
; ----------------------------------------------------------------------------------------------
; Returns the active Sorted Map Key (to be used from within FOREACHSORTEDMAP)    
; ----------------------------------------------------------------------------------------------
Macro SortedMapKey(MapName)
   MapName#Sorted()
EndMacro
;
; ----------------------------------------------------------------------------------------------
; Adds a new Element to the Sorted Map Element, if the key is already existing, the content 
;        will be modified 
; ----------------------------------------------------------------------------------------------
Macro AddSortedElement(MapName,xkey,xcontent)
  If FindMapElement(MapName(),xKey)=0     
     MapName#BPTR(xkey)=AddElement(MapName#Sorted())
     MapName#sorted()=xkey
     MapName#MustbeSorted=1
  EndIf   
  MapName(xkey)=xcontent
EndMacro;
;
; ----------------------------------------------------------------------------------------------
; Deletes an exisiting Element to the Sorted Map Element    
; ----------------------------------------------------------------------------------------------
Macro DelSortedElement(MapName,xkey)
  If FindMapElement(MapName(),xKey)>0  
     DeleteMapElement(MapName())
     ChangeCurrentElement(MapName#sorted(),MapName#BPTR(xkey)) 
     DeleteElement(MapName#sorted())
     DeleteMapElement(MapName#BPTR(),xkey)
  EndIf   
EndMacro;
;
; ----------------------------------------------------------------------------------------------
; Sorts a SortedMap after adding new Elements     
; ----------------------------------------------------------------------------------------------
Macro SortMap(MapName,mode=#PB_Sort_Ascending) 
  If MapName#MustbeSorted=1
     SortList(MapName#Sorted(),mode)
     MapName#MustbeSorted=0
  EndIf 
EndMacro  
;
; ----------------------------------------------------------------------------------------------
; Migrates an ordinary MAP  to a SortedMap, by adding List of Map Keys     
; ----------------------------------------------------------------------------------------------
Macro MakeSortedMap(MapName,scope=Global)
scope NewList MapName#Sorted.s()
ClearList(MapName#Sorted())  
ForEach MapName()
  AddElement(MapName#Sorted())
  MapName#Sorted()=MapKey(MapName())
Next
SortList(MapName#Sorted(),#PB_Sort_Ascending)
EndMacro
;
; ==============================================================================================
; Main Program 
; ==============================================================================================

Structure fred
  SortedMap(Mike)
EndStructure
Global SSD.fred
; create map from 100 to 1, to demonstrate SORTMAP

For i=100 To 1 Step -1  
    Item$="Line "+Str(i) 
    key$=RSet(Str(i),7,"0")
    AddSortedElement(ssd\Mike,key$,item$)
Next
SortMap(ssd\Mike) 
ForEachSortedMap(ssd\Mike) 
   Debug SortedMapkey(ssd\Mike)+": "+SortedMapElement(ssd\mike)
Next 

Regards

Peter

[spikey]

Wouldn't it be possible to find not only a complete search term, but also the beginning of a specific entry?

Not efficiently, which is the purpose of using a map. As PeterJ said above the map key is converted into a number, known as the hash, which gets stored in the map. In order to do a partial key search you would have to 'unhash' each map key in turn, do a partial string comparison on the key to see if it matches etc. Also as PeterJ suggests, there are other ways to do this sort of thing efficiently though - indexing, trees...

[Josh]

Somehow I have suspected that it is not possible. In any case thank you for your expositions.