Browse Prior Art Database

Self-Contained Hashed Symbol Tables

IP.com Disclosure Number: IPCOM000099559D
Original Publication Date: 1990-Feb-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 4 page(s) / 171K

Publishing Venue

IBM

Related People

Hendrickson, OK: AUTHOR

Abstract

Most languages provide only numerically indexed arrays. To match a symbolic name with data requires a search coded by the programmer, which is often implemented as a (slow) linear search. Self-contained hashed symbol tables provide easy, fast, and direct access to data using a symbolic name index instead of a numeric index.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 32% of the total text.

Self-Contained Hashed Symbol Tables

       Most languages provide only numerically indexed arrays.
To match a symbolic name with data requires a search coded by the
programmer, which is often implemented as a (slow) linear search.
Self-contained hashed symbol tables provide easy, fast, and direct
access to data using a symbolic name index instead of a numeric
index.

      Each record in a self-contained hashed symbol table (hereafter
referred to as "table") contains:
      -    Hash chain index--A chain link connecting all symbols that
hash to the same location.
      -    Sort chain index--A chain link connecting all symbols in
the table.
      -    Symbol name--The name of the data.
      -    Data value--The data.
      Five functions access the table:
      -    Allocate a table--Create an empty table.  Specify the
number of records in the table.  This returns the table identifier
for the new table.
      -    Write a data value associated with a symbol name--Enter a
symbol and data in the table.  If the symbol already exists, write
over the old data.  Splice new symbols into the sorted chain link
(the program is written to sort either alphabetically, first-in,
first-out, or last-in, first-out). Table overflow is checked for.
      -    Read the data value associated with a symbol name. Symbol
not found is indicated to the user.
      -    Read each symbol and data value sequentially--A special
sym     bol indicates that a wish to start at the beginning.  There
  after, each read returns the data value associated with the current
symbol and sets the symbol to the next symbol name. Symbol not found
and end of table reached are indicated to the user.
      -    Delete a symbol name and associated data--Symbol not found
is indicated to the user.
      -    Deallocate a table--Checking for table not allocated is
the responsibility of the user.
      The first record in the table is used for a header record.  It
contains the following:
      -    The hash chain index field in the header record is used
for an entry that hashes to the location of the header record.
      -    The sort chain index field in the header record points to
the first entry in the sorted chain link.
      -    The symbol field in the header record contains a special
value indicating that it is the header. 'FFFFFFFFFFFFFFFF'X is used.
This value must be known to the user in order to start reading the
entries in sequential order.
      -    The data field in the header record is not required to
hold any specific information.  It is used to hold the number of
entries in use in the table and a count of the number of entries that
hash to a location that already has an entry. This indicates how full
a table is and how well distributed the hash function is.  These data
are maintained by the "write" function.

      A single table...