function hash

function hash

[Nacho Robledo]

Hello !!!!!!

    I am a student of Computer Sciencie and i am looking for an easy  hash
function that can work with 15 o more characters... It's for working in a
table of 500-1000 elements. ANY idea?

Thanks !!!!!

--
--
 Ignacio Robledo Rosell
 mailto:rrilpm@arrakis.es
 http://zipi.fi.upm.es/~g990406
 ****************************************
 "When code matters more than comercials"
 ****************************************

Re: function hash

[James Rogers]

Nacho Robledo wrote:
> 
> Hello !!!!!!
> 
>     I am a student of Computer Sciencie and i am looking for an easy  hash
> function that can work with 15 o more characters... It's for working in a
> table of 500-1000 elements. ANY idea?
> 

You might find the package GNAT.HTable to be useful.

This package is included in the public GNAT distribution.

Jim Rogers
Colorado Springs, Colorado USA

Re: function hash

[Jeffrey Carter]

Nacho Robledo wrote:
> 
>     I am a student of Computer Sciencie and i am looking for an easy  hash
> function that can work with 15 o more characters... It's for working in a
> table of 500-1000 elements. ANY idea?

You might find the article "Fast Hashing of Variable-Length Text
Strings," by P. K. Pearson (CACM 1990 Jun) of interest. It describes a
fast "hashing function specifically tailored to variable-length text
strings."

An implementation of this function is part of the PragmAda Reusable
Components, available from

http://home.earthlink.net/~jrcarter010/pragmarc.htm

or from the mirror at www.adapower.com.

-- 
Jeff Carter
"Your mother was a hamster and your father smelt of elderberries."
Monty Python & the Holy Grail

Re: function hash

[Nacho Robledo]

Thank you very much !!!!! all the information is very
usefull ... thanks again

--
--
 Ignacio Robledo Rosell
 mailto:rrilpm@arrakis.es
 http://zipi.fi.upm.es/~g990406
 ****************************************
 "When code matters more than comercials"
 ****************************************

Re: function hash

[Florian Weimer]

Jeffrey Carter <jrcarter@acm.org> writes:

> You might find the article "Fast Hashing of Variable-Length Text
> Strings," by P. K. Pearson (CACM 1990 Jun) of interest. It describes a
> fast "hashing function specifically tailored to variable-length text
> strings."
> 
> An implementation of this function is part of the PragmAda Reusable
> Components, available from
> 
> http://home.earthlink.net/~jrcarter010/pragmarc.htm

A hash function returning only 256 different values?  Are there any
applications for it?

Re: function hash

[Jeffrey Carter]

Florian Weimer wrote:
> 
> A hash function returning only 256 different values?  Are there any
> applications for it?

Given the original poster's requirements of handling 500-1000 elements,
that's only 2-4 per bin, so it seemed suitable.

-- 
Jeff Carter
"We call your door-opening request a silly thing."
Monty Python & the Holy Grail

Re: function hash

[tmoran]

>A hash function returning only 256 different values?  Are there any
>applications for it?
  Anytime cutting the size of a search by a factor of 256 seems useful.
Or a cheap test to see whether it's worth an expensive comparison to
check for a match with one of a few objects.

Re: function hash

[Florian Weimer]

Jeffrey Carter <jrcarter@acm.org> writes:

> Florian Weimer wrote:
> > 
> > A hash function returning only 256 different values?  Are there any
> > applications for it?
> 
> Given the original poster's requirements of handling 500-1000 elements,
> that's only 2-4 per bin, so it seemed suitable.

In particular with long strings, this will result in a measurable
performance degradation in comparison to a real hash function because
of the necessity to perform additional key comparisons.

Re: function hash

[Simon Wright]

Florian Weimer <fw@deneb.enyo.de> writes:

> Jeffrey Carter <jrcarter@acm.org> writes:
> 
> > Florian Weimer wrote:
> > > 
> > > A hash function returning only 256 different values?  Are there any
> > > applications for it?
> > 
> > Given the original poster's requirements of handling 500-1000 elements,
> > that's only 2-4 per bin, so it seemed suitable.
> 
> In particular with long strings, this will result in a measurable
> performance degradation in comparison to a real hash function because
> of the necessity to perform additional key comparisons.

I don't understand. If there are only 256 bins (not unreasonable) then
there are *bound* to be collisions for a large key space (eg all the
sentences in Jane Eyre).

If you need a perfect hash (eg for the reserved words in Ada) that's
quite a different problem.