Re: Algorithm to convert unique sequences of letters,integers, and hyphens into integers under 2147483646
- From: "nightlight" <nightlight@xxxxxxxxxxxxxx>
- Date: 23 Oct 2005 00:17:45 -0700
> In the event of a collision, a data record would be replaced
> by a lookup record and the item codes sharing the same hash
> key would be stored as data records with item keys of
> 2^8 * C + 1, 2^8 * C + 2, .. and the item codes stored
> in the lookup record at corresponding positions.
To diferentiate a collision from the case of receiving the same string
as before you would need to keep all strings encoded so far. Once you
go to that trouble (of having to keep all previously encoded strings
in order to guarantee that the same string will always yield the same
hash value), the simplest hash function is just a dictionary index of
the string. Your collision proposal could still be used as a part of
hashed search for this dictionary. Or one could use any other search
method (such as maintaining the strings in a tree and doing binary
search).
The above discussion would correspond to the problem in which the
strings are _not known in advance_. If the strings are known in advance
and additionally if one doesn't want to store the full list with the
encoder & decoder (otherwise one could simply use dictionary index as
the hash value), then any "perfect hash" algorithm (numerous sources
for that exist on the web) can be used to produce unique hash codes for
this known set of strings.
The original poster unfortunately didn't provide enough detail on the
problem requirements to obtain a definite answer.
.
- References:
- Prev by Date: Re: Marble problem--put in 10 marbles, then remove 1
- Next by Date: Re: riemann vs lebesgue integrals
- Previous by thread: Re: Algorithm to convert unique sequences of letters,integers, and hyphens into integers under 2147483646
- Next by thread: Re: Algorithm to convert unique sequences of letters,integers, and hyphens into integers under 2147483646
- Index(es):
Relevant Pages
|
