Re: Hash tables

  C <cc-news@hermes.mirlex.com> schreibt:


>Well, closed hashing does use less memory, but this is only a matter
>of between one and three pointers -- I doubt anyone would quibble over
>a few bytes on a modern PC.


I'm not sure about all the theory, so let me present my recent
"invention" of a hash table. The goal is a symbol table with the
ability of pushing/popping symbols (scopes) during parsing, so that
duplicate entries can occur. Consequently the base structure is a
stack, implemented as an array. In addition to the string, or whatever
information, every record in the array has a First and Next field. The
First field contains the index of the first record for an given hash
code, and the Next field of that record contains the index of the next
record of the same hash code. New records are added and removed in
LIFO order, both to the record list and to the hash chains, so that
the last added entry is found first. A search for true duplicates then
can follow the Next chain.


The array is initialized to a reasonable size, so that
    i = Table[hashcode mod arraysize].First
yields the index of the first record of hashcode, and
    i = Table[i].Next
is the index of the next record.


When the array must be extended, the First and Next fields are
adjusted according to the new array size, the records (data portion)
retain their old index. When memory is not of concern, the table can
be allocated once to a sufficient extent, so that a reallocation and
reorganization is unlikely. Otherwise the table can grow dynamically,
at the cost of some more reorganization.


Did I reinvent the wheel with this approach, or should I hurry up for a
software patent? <grin>


DoDi

Return to the comp.compilers page.
Search the comp.compilers archives again.