Page 1 of 2

hash with (x)harbour - knowledge base

Posted: Tue Sep 21, 2010 6:08 am
by Otto
To all,
I would like to start a knowledge base about the use of hash with (x)harbour.
If someone has additional information please post it here. Thanks in advance.
----------------------------------------------

From a post of Mr. Rao:

In general Hash is a number derived from a large data value ( mostly character strings ) uniquely identifying it. Something like a checksum. Hash table is a table that stores such values and it gets easier to index and search on such tables.

But the Hashes we are talking about in (x)Harbour are different.
Hashes are like Arrays but with more flexibility. They are also called Associative Arrays.

For arrays, the index is always an integer from 1,...n.
For Hashes, the index can be a Character, Numeric, Date.
For example, hHash[ "One" ] := <somevalue>

We instantiate Arrays as aArray := {} or aArray := Array(n)

We instantiate Hashes as hHash := {=>} or Hash() ( xharbour )

We can add elements like

hDays[ "Jan" ] := 31
hDays[ "Feb" ] := 28, etc.
Later, hDays[ "Feb" ] --> 28

In xhabour both the above syntax works and also we can write hDays:Jan := 31 and hDays:Feb := 28

Here "Jan" and "Feb" are called Keys and 31 and 28 are called Values

There are many Hash functions to operate on Hashes.
ValType( hDays ) is 'H'

You can learn more from xharbour.chm help file.

Regards
Rao

----------------------------------------------

HSetCaseMatch( ::hStates, .f. ) // make it case insensitive
USE ("States " ) NEW SHARED READONLY
DbEval( { || ::hStates[States -> Code] := States ->name } )

// Alternative Syntax:
// DbEval( { || HSet( hStates, States ->Code, States->Name ) } )
CLOSE code

TRY
stateName := ::hStates[ (States)->Code ]
CATCH
END


How to use with xBrowse:

WITH OBJECT ::oBrw:AddCol()
:cHeader := " State Name "
:bEditValue := { || ::hStates[ (::cAlias)->Code ] }
END
----------------------------------------------

Hash is like Array. Only difference is for Arrays the index is an integer and for Hashes the index can be number, date or character value. If the index is out of range for arrays, it results in a runtime error. Same way if the index value of a Hash is not found, it results in a runtime error.

What we do for arrays if we are not sure if the index in within range?
We can write :
TRY
result := aData[ n ]
CATCH
result := 0
END
OR
result := If( n > 0 .and. n <= Len( aData ), aData[ n ], 0 )

Same way for Hashes also:
We can either write a TRY,CATCH,END block
OR
result := If( HHasKey( hData, cKey ), hData[ cKey ], <default> )
----------------------------------------------

Re: hash with (x)harbour - knowledge base

Posted: Tue Sep 21, 2010 6:35 am
by Otto
Hash tables - What are they good for?
http://www.knowlexbase.com/en/software/ ... Table.html

Re: hash with (x)harbour - knowledge base

Posted: Tue Sep 21, 2010 7:06 am
by Maurizio
Hello Otto

I use Hash for manage the database

Function Scatter()
Local aVars := {=>}
LOcal nField := FCount()
LOcal nX := 1
FOR nX := 1 TO nField
aVars[FIELDNAME(nX)] := FieldGet(nX)
NEXT

Return aVars


Function Gather(aVars)
lOCAL Nx := 1

FOR Nx := 1 TO LEN(aVars)
FieldPut(nX,aVArs[FIELDNAME(nX)] )
NEXT


Return .T.



Regards MAurizio

Re: hash with (x)harbour - knowledge base

Posted: Tue Sep 21, 2010 11:20 pm
by James Bott
MAurizio,

I don't see where you are using a hash?

Did you know that the equivalent of scatter and gather is built into database objects. And instead of refering to aVars[1], you can refer to oCust:name. This makes the code much easier to write and read. There are lots of other good reasons to use database objects. See my articles on FW OOP programming.

http://www.gointellitech.com/program.htm

James

Re: hash with (x)harbour - knowledge base

Posted: Wed Sep 22, 2010 6:51 am
by Maurizio
James ,

With hash you cann use the name of the fields to

Code: Select all


oCust := Scatter() 
?( oCust:name) 


Function Scatter()
Local aVars := {=>}
LOcal nField := FCount()
LOcal nX := 1
FOR nX := 1 TO nField
aVars[FIELDNAME(nX)] := FieldGet(nX)
NEXT
 
Regards Maurizio

Re: hash with (x)harbour - knowledge base

Posted: Wed Sep 22, 2010 2:35 pm
by James Bott
Maurizio,

I don't understand this syntax. Please explain.

Local aVars := {=>}

What is {=>} ?

Does that preprosses into something else?

James

Re: hash with (x)harbour - knowledge base

Posted: Wed Sep 22, 2010 2:46 pm
by Enrico Maria Giordano
James Bott wrote:Maurizio,

I don't understand this syntax. Please explain.

Local aVars := {=>}

What is {=>} ?

Does that preprosses into something else?

James
No, it is the regular syntax required to initialize an empty hash (ie. similar to aVars := {} for arrays).

EMG

Re: hash with (x)harbour - knowledge base

Posted: Wed Sep 22, 2010 4:23 pm
by James Bott
Enrico,
No, it is the regular syntax required to initialize an empty hash (ie. similar to aVars := {} for arrays).
So aVars := {=>} is an array of hashes?

And can you also explain this syntax?

aVars[FIELDNAME(nX)] := FieldGet(nX)

I am guessing that it is creating a hash for the fieldname and storing the fieldvalue related to that hash?

As you can tell, I know nothing about hashes.

Regards,
James

Re: hash with (x)harbour - knowledge base

Posted: Wed Sep 22, 2010 5:19 pm
by Enrico Maria Giordano
James Bott wrote:So aVars := {=>} is an array of hashes?
No, it is a single hash, that is essentially an array indexed by strings instead of numeric values.
James Bott wrote:And can you also explain this syntax?

aVars[FIELDNAME(nX)] := FieldGet(nX)

I am guessing that it is creating a hash for the fieldname and storing the fieldvalue related to that hash?
No, it is creating an item in the hash indexed by the fieldname and storing the fieldvalue. Later you can access that value using the fieldname instead of the numeric index.

EMG

Re: hash with (x)harbour - knowledge base

Posted: Wed Sep 22, 2010 8:34 pm
by James Bott
Ok, I have done some research and reading on hash tables and I found this in Wikipedia:

Ideally, the hash function should map each possible key to a unique slot index, but this ideal is rarely achievable in practice (unless the hash keys are fixed; i.e. new entries are never added to the table after creation). Most hash table designs assume that hash collisions—the situation where different keys happen to have the same hash value—are normal occurrences and must be accommodated in some way.

Does the (x)Harbour hash function automatically handle collisions? Has anyone tested it? I don't think I would want to risk using a hash table without knowing the answer to how collisions are handled.

Also, I found that syntax used by Marizio (aVars) confusing. This normally represents an array and yet here it is holding a hash table which I have also seen refered to as an object in the literature. Using a "o" prefix would also be confusing since it not the same as objects created from classes that we are used to using. And the "h" prefix is already used to signify a handle. Is there a standard Hungarian syntax for a hash table?


Regards,
James

Re: hash with (x)harbour - knowledge base

Posted: Wed Sep 22, 2010 9:28 pm
by Enrico Maria Giordano
James Bott wrote:Does the (x)Harbour hash function automatically handle collisions?
No, as far as I know. It is the programmer responsibility to assure the uniqueness of the key.
James Bott wrote:I don't think I would want to risk using a hash table without knowing the answer to how collisions are handled.
If the key is a fieldname there is no problem as the fieldname is already unique.

EMG

Re: hash with (x)harbour - knowledge base

Posted: Wed Sep 22, 2010 11:03 pm
by James Bott
Enrico,
If the key is a fieldname there is no problem as the fieldname is already unique.
The Wikipedia article states otherwise. They show two different names mapping to the same hash "bucket." See under the "Collision Resolution" section the example that "James Smith" and "Sandra Dee" both map to the same hash number.

http://en.wikipedia.org/wiki/Hash_table ... h_function

So I do think we run the risk of two fieldnames colliding (unless the (x)Harbour hash function automatically handles collisions). I am not sure how we can test this.

Regards,
James

Re: hash with (x)harbour - knowledge base

Posted: Thu Sep 23, 2010 6:56 am
by Enrico Maria Giordano
I don't know the internals of the [x]Harbour's hash implementation but I know for sure that two different keys have no collision (or the collision is internal managed).

EMG

Re: hash with (x)harbour - knowledge base

Posted: Thu Sep 23, 2010 7:02 am
by Antonio Linares
Both Harbour and xHarbour, same as Clipper did, use internal hashes to match the function to call when a message is sent to an object.

Basically they calculate a unique number from a string. The original algorithm that we used was developed by the Standford University (as far as I remember it). Just as a curiosity :-)

Re: hash with (x)harbour - knowledge base

Posted: Thu Sep 23, 2010 2:18 pm
by James Bott
Well, it all sounds good, but I am hesitant to use hashes for any critical application since a collision could be disasterous. For an accounting app it could cost millions, for a medical app it could be fatal. Perhaps I will try to devise a test for a large number of items to see about collisions. Is there a size limit?

James