Re: Hash
- From: CBFalconer <cbfalconer@xxxxxxxxx>
- Date: Sat, 30 Dec 2006 19:03:39 -0500
Jon Harrop wrote:
.... snip ...
There isn't much point in allowing duplicate key-value pairs.
Allowing the same key to map onto different values can be useful
(e.g. to implement scope in an interpreter), as OCaml's built-in
hash table does.
hashlib [1] was designed with scoped symbol tables in mind. To use
it for such you would need openscope and closescope functions,
together with a linked list of scopes. Openscope would extend the
list after creating a new hashtable for that scope, and closescope
would destroy the table and remove the last entry in the list.
Then searching for an identifier is simply searching each table
starting at list end. (A reversed list would be handy for this.)
New entries always go into the current scope, which is at the list
end. An entry count field will enable detection of multiple
definitions in a single scope (or other flags can be used). The
auxiliary functions customizing the tables would be common to all.
That would make the symbol table search O(N), where N is the count
of scopes active. It will normally be O(1) because most entries to
be used will be in the current scope. Table entry would be O(1).
A further identical table can be used to hold the reserved words,
which is searched to classify an identifier as being reserved or
available.
[1] <http://cbfalconer.home.att.net/download/>
--
Merry Christmas, Happy Hanukah, Happy New Year
Joyeux Noel, Bonne Annee.
Chuck F (cbfalconer at maineline dot net)
<http://cbfalconer.home.att.net>
.
- References:
- Prev by Date: Re: Worst case execution time problem
- Next by Date: Re: Hash
- Previous by thread: Re: Hash
- Next by thread: Re: Hash
- Index(es):
Relevant Pages
|
|
