Voici deux codes, l'un montrant un algorithme de "Hascoding" et son utilisation
L'autre une gestion d'une BitMap... Et à quoi ça sert !
Les deux avec les commentaires inclus dans les codes expliquant ce qu'il en est...
La fonction PureBasic "MAP" est une forme simple de gérer un index de Clef et basé sur une technique de
"Hascode" aussi... Ici ce n'est qu'une forme alternative avec certaines propriétés en plus.
La gestion d'une BitMap est aussi une forme de contrôler les enregistrements libre ou non dans un fichier.
Voir aussi les explications également inclus dans les codes.
J'ai choisis ces formes d'inclure les explication avec le code, de manière à importer les commentaires avec le code
par ce merveilleux système donné par ERIX 14 et le "Copier".
Code : Tout sélectionner
; ========================================================================
; HASHCODE : Ou système de rangement a partir de clef d'accès. 2010/07/09
; Explication : Et alternative GeBonet
; =============================================================================
; Une Forme de HashCode : Mais qu'est-ce qu'un HashCode ?
;
; C'est un algorithme (méthode) qui calcule une valeur unique à partir d'une chaîne (ou expression)
; de caractères. Exemple le système ci-dessous donne la valeur "1199" pour la chaîne "GeBonet"
; Mais cette valeur est aussi dépendante de l'espace dans lequel on doit trouver une place.
; ICI, j'ai donnée "Max=1250" soit autant de position qui en principe pourrait être octroyé...
; et c'est pour cela que cela à donnée 1199. Si je change cette valeur en 3250, j'aurais : 1449 !
;
; Toutefois il est évident que sur cette base un calcul peut produire la même valeur pour deux
; chaînes qui seraient différentes. Et cela sera d'autant plus vrai que l'espace sera petit... (Max)
; On parlera alors de "collision"... Il est de coutume d'utiliser une valeur "Max" de 1.5 fois le
; nombre de clef que l'on pense ranger... (Avec cet Algorithme ci).
;
; Alors deux solutions sont possibles ou on ajoute un caractère aléatoire avec un signe distinctif
; pour produire une autre valeur (ex: GeBonet+d, "+"=le signe et "d"=la valeur aléatoire) ou on refuse
; l'entrée et demandons à l'utilisateur un complément à la "Clef"...
;
; Il a aussi d'autres méthodes possibles comme celle-ci par exemple :
; -----------------------------------------------------------------
; Comme le fichier ou espace est de 1.5 fois le nombre d'enregistrement alors, si il y a
; collision et qu'il y a des "trous", on peut donc vérifier si la place suivante est occupée.
; Si non on y range la nouvelle clef et ainsi de suite. De cette manière il y a évidement des
; balayages séquentiels qui vont se produire, mais ceux-ci serons limités à de petit déplacements.
; De plus de cette sorte on peut faire admettre deux clef identique si nécessaire.
; Forme qui est présente dans l'exemple ci-dessous. Le [u]ELSE ligne 56 traite le débordement[/u] ou peut
; traiter le renvois vers l'utilisateur pour demander un complément de clef.
;
; ATTENTION : Une table HashCode ne peut pas être triée... Ni le fichier des données qui y est associé !
; ********** Ce qui n'empêche pas de constituer une table en parallèle qui elle serait trié au moment
; voulu et serait alors utilisée pour sortir des listes ordonnées.
;
; =======================================================================
; NOTE : [u]Je sais qu'il existe les Map et Structures de PureBasic, mais ici il s'agit d'une[/u]
; [u]alternative autonome avec acceptation de collision[/u] et une gestion étendue à une BitMap
; qui peut contrôler un accès direct...
; ========================================================================
; Exemple :
; ********
Declare.f Hasch(Key$,Max)
;
Max=1250 ; Nombre max d'enregistrement...
Dim Key$(Max) ; Les Clefs
Dim Pos(Max) ; Les Positions
Dim Deb(Max) ; Nbr de Débordements (Collision acceptée)
;
Restore mot
For K=1 To 30 ; Ici 30 noms dans les Data.... dont 4 fois 7 les mêmes + 2 autres
Read.s Key$
positionHC=Hasch(Key$,Max)
Repeat
If Pos(positionHC)=0 ; Position vacante
Pos(positionHC)=positionHC:Key$(positionHC)=Key$
Ok=1
Else ; <<------------------------------------------ Non vaccante alors une sociétée est exigée..!!!
; MessageErreur$="Occupé, donner une autre clef"
; CodeERR=-99:Break ... OU
; ICI on essaye les positions suivantes....
Nbr=Deb(positionHC) ; On mémorise le nombre de clef identique
Deb(positionHC)=Nbr+1 ; pour la recherche ultérieure....
While Pos(positionHC)<>0 ; Recherche de la première place vaccante !
positionHC=positionHC+1
Wend
Pos(positionHC)=positionHC:Key$(positionHC)=Key$:Ok=1
EndIf
Until Ok=1
Debug "positionHC de "+Key$+" N° "+Str(K)+" = "+Str(positionHC)
If Mod(K,7)=0 : Debug "============": EndIf
Next K
;CallDebugger
Debug "************************"
DataSection ; Ici une liste de noms pour test .... (Répétée pour provoquer des collisions normale)
mot:
Data.s "GeBonet", "Delaruelle","Gerhard","Jules","Juliette","Clement pierre","Albert de monaco"
Data.s "GeBonet", "Delaruelle","Gerhard","Jules","Juliette","Clement pierre","Albert de monaco"
Data.s "GeBonet", "Delaruelle","Gerhard","Jules","Juliette","Clement pierre","Albert de monaco"
Data.s "GeBonet", "Delaruelle","Gerhard","Jules","Juliette","Clement pierre","Albert de monaco"
Data.s "Caroline", "La Feuille"
EndDataSection
; -----------------------------------------------------
; ALGO de Calcul d'un HashCode à partir d'une Key$
; Avec Max = Nombre d'enregistrement MAX...
; Key$= la clef trouver un enregistrement ...
; --------------------------------------------------------------------------
; Note : Il s'agit ici d'"un" algorythme comme il peut y en avoir d'autres..
; Celui-ci est assez éfficace et date du temps ou il n'y avait pas
; beaucoup de place (+/- 30ans).
; --------------------------------------------------------------------------
Procedure.f Hasch(Key$,Max)
Define.f K0,K1,A0,A1,B0,B1,C0,C1
Lg=Len(Key$): Dim A.f(Lg)
positionHC=0: Key$=Trim(Key$)
For I=1 To Len(Key$)
J=Int((I/2-Int(I/2))*2+0.05):J+Sign(I/2):J=J-1
A=Asc(Mid(Key$,I,1)):A(J)=A(J)+A
Next I
A0=A(0)/256:A1=A(1)/256 :B0=Int(A0):B1=Int(A1) :C0=Sign(A0):C1=Sign(A1)
K0=Int((A0-B0)*256+0.05)*C0:K1=Int((A1-B1)*256+0.05)*C1:KF=K0+256*K1
positionHC=Int((KF/Max-Int(KF/Max))*Max+0.05)*Sign(KF/Max)
ProcedureReturn positionHC
EndProcedure
Code : Tout sélectionner
;///////////////////////////////////////////////////////////////////////////////////////////
;
; LE CODE SUIVANT EST UN COMPLEMENT NATUREL AU HASHCODE....
; *********************************************************
; L'un pour "les clefs" et le pointeur vers une position dans un fichier direct, le code du dessus.
; L'autre pour gerer la place (position) des élements d'un fichier a accés direct...
;
;\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
; ======================================================================
; * < GESTION de BIT MAP > *
; ======================================================================
; Objet : Gestion d'une BitMap. Mais Qu'est-ce qu'une BITMAP ?
; -------------------------------------------------------------------------------------------
; C'est une "carte" représentant sous forme binaire l'occupation ou non d'une position
; parmi un nombre déterminé d'enregistrement. Où si l'on veut à chaque 1 correspond une
; position OCCUPÈE et un 0 sera une position LIBRE soit pour 8 enregistrements crée nous
; aurions la carte ="11111111" tandis que "11110111" nous dis que la position 4 est libre
; (les bits se lisent de droite à gauche).
;
; Cet exemple de 8 n'est pas anodin. Je l'ai pris pour illustrer le fait que c'est aussi un
; BYTE. D'ou qu'un seul BYTE peut servir pour connaitre l'occupation ou non de 8 enregistrements
; qu'une carte binaire de 128 bytes permet de contrôler 1024 enregistrement et forcément 1 méga
; de carte = 8 méga d'enregistrement.
;
; L'INTERET de ce contrôle ? Cela permet de ne pas faire croître un fichier et de réaffecter
; directement les enregistrements effacés. Cela permet aussi au moment de l'effacement de ne
; supprimer que virtuellement l'enregistrement en mettant sa position dans la Map à 0 sans pour
; autant effacer réellement l'enregistrement.
;
; Tout en étant que cela va plus vite de mettre à 0 un bit qu'un enregistrement qui ne sera
; réellement effacé qu'au moment de sa réoccupation par un nouveau.
; Soit une réelle gestion dynamique d'un fichier a accès direct.
;
; Donc le principal intérêt est que sur des fichiers à accès direct et de très grande taille
; cela permet une gestion très rapide des "trous" par réaffectation des espaces vacants sans
; devoir réorganiser quoi que ce soit.
;
; Il va de soit que si l'on peu y associer la fonction "NewMap" ou une autre technique de HashCode
; pour la gestion des clefs auxquels on associerait la position du fichier (Voir ci-dessous).
; Dès lors l'écriture d'un enregistrement se ferait selon la séquence :
;
; 1- Recherche d'une place vacante du fichier direct grâce à la BitMap
; 2- Ecriture des données dans le fichier direct a la position donnée par ma BitMap...
; 2- Ecriture dans MAP()de la clef avec la position des données dans le fichier direct.
;
; La lecture c'est l'inverse... :
;
; 1- Grâce à FindMapElement(Map(), Key$) j'obtiendrait la position de L'enregistrement
; 2- Avec la position je lirais de L'enregistrement ou qu'il soit dans le fichier direct...
;
; Pour l'effacement :
;
; 1- On efface seulement la clef et le pointeur Position dans le HashCode
; 2- Puis son BIT représentant sa position dans la BitMap.
;
; On peut aussi associé une table HasCode (voir autre code) indépendante pour gérer ces accès
; par clef (type ci-dessus).
; ----------------------------------------------------------------------------------------
; NOTE : Dans cet ensemble il manque l'objet même de ceci, c'est le fichier des données,
; qui doit être accessible en mode direct. Soit a une position correspond l'ensemble des
; données reliées à une clef... Que ce soit via une Liste Chainée ou autre type de gestion
; de fichier pour autant que chaque bloc de données soit accessible directement.
; ====================================================================
; Simulation de Création d'une ligne de 128 bytes de la BitMap... En laissant
; le Byte 64 à 254 soit 1 bit à 0 donc égal à une position libre !
; Ce qui devrait pointer sur la position 63 x 8 = 504 + 1 bit vaccant de 254 = Position 505
; en effet chaque Byte = "11111111" 8 bit = 8 positions et 254=11111110
; ====================================================================
;
Debug "================================"
Debug "* Attention ICI test Bitmap !!!*"
Debug "================================"
Debug ""
Global BMap$
Declare Gest_BitMap(BMap$, Fonc.c, Position.l)
For i=1 To 128
If i<>64
BMap$+Chr(255) ; 255=11111111
Else
A=%11111110 ; 254=11111110 : Est le 64 ième Byte...
BMap$+Chr(A) ; Ici simulation un d'une position vaccante !
EndIf
Next i
; ---------------- Exemple ou l'on cherche une place vaccante -------
;
Fonc.c=1 ; Ici On cherche une place et on écrit ...
Position.l=0 ; Position a zéro pour partir et revient avec la position du Bit vaccant !
;
Debug "Test BitMap *"
Debug "Long. MAP : "+Str(Len(BMap$))
Debug "Position : "+Str(Gest_BitMap(BMap$, Fonc.c, Position.l))
End
; --------------------------------------------------------------------
; >>>>>>>>>>>>>>>>>>>>>>>>>>>> LA PROCEDURE <<<<<<<<<<<<<<<<<<<<<<<<<<
; --------------------------------------------------------------------
; ENTREE : BMAP$ = Chaine contenant la bit map
; Fonc = 1 ou 2 (Ecrit ou supprime, met a 1 ou 0)
; POSITION = Position …A supprimer si FONC=2 met a 0
;
; SORTIE : POSITION = Position vaccante OU -99 si erreur dans routine
; BMAP$ = Chaine contenant la bit map modifiée
; =====================================================================
Procedure Gest_BitMap(BMap$, Fonc.c, Position.l)
Dim Bit(8) ; Bit() = Table binaire de référence
Bit(1) = 1: Bit(2) = 2: Bit(3) = 4: Bit(4) = 8
Bit(5) = 16: Bit(6) = 32: Bit(7) = 64: Bit(8) = 128
OK = 0: ER = 0:LongueurMAP=Len(BMap$)
; -------------------------------------------------------------------
; FONC=1 : Recherche dans BMap$ d'un byte ayant un bit disponible.
; Sortie avec la "Position" correspondant à ce Bit.
; -------------------------------------------------------------------
If Fonc = 1
For I = 1 To LongueurMAP ; Recherche d'un Byte n'étant pas "plein" (255 ou "11111111")
car= Asc(Mid(BMap$, I, 1)): If car<> 255: N = car: Ok = 1: Break:EndIf
Next I
;
If Ok = 1 ; Trouvé le byte = N
Ok = 0
For I = 1 To 8 ; ; Test logique entre la valeur du Bit(i) et le caractère
L = Bit(I) | N ; qui donne la position K=I dans le byte N trouvé.
If L = N + Bit(I):BIT = Bit(I): K = I: OK = 1:Break:EndIf
Next I
;
If Ok = 1 ; CALCUL De la position
Byte$=Chr(N)
PO = FindString(BMap$,Byte$ ,1): BYT = BIT + N
Position= (PO - 1) * 8 + K: N = BYT: BYT = PO ;
ReplaceString(BMap$, Byte$, Chr(N), #PB_String_InPlace) ; Positionne le Bit à 1
EndIf
If OK <> 1:Position = -99:ProcedureReturn -99:EndIf
EndIf
ProcedureReturn Position
; retour avec la position mise à 1 ou Position donnant -99 = Erreur
EndIf
; --------------------------------------------------------------------------------------
; FONC=2 :Calcul et MISE A ZERO du BIT correspondant a la "POSITION" (Inverse de FONC=1)
; --------------------------------------------------------------------------------------
If Fonc = 2 ; CALCUL DU BIT A POSITIONNER A ZERO
;
BYT = Int(Position / 8): BIT = Position - BYT * 8
If BIT = 0 : BIT = 8: BYT = BYT - 1:EndIf
BYT = BYT + 1: If BYT = 0 :BYT = LongueurMAP:EndIf
N = Asc(Mid(BMap$, BYT, 1)):Byte$=Chr(N)
If CFLG = 0: N = N - Bit(BIT): Else :N = N + Bit(BIT):EndIf
If (N>255) | (N<0) : Position = -98 ; Erreur...
Else
ReplaceString(BMap$, Byte$, Chr(N), #PB_String_InPlace) ; POSITIONNE LE BIT A 1 dans BitMap
EndIf
EndIf
ProcedureReturn Position
EndProcedure
; ---------------------------------------------------------------------------------------
A++