Hashing functions
pcs$...@altair.selu.edu
100-element array. I would prefer a linear probing technique, but any others
would be welcome. Thanks.
Brad Crochet
Kim
: I'm looking for hashing code. I need to hash a number between 0 and 99 to a
: 100-element array. I would prefer a linear probing technique, but any others
: would be welcome. Thanks.
Hashing works best for sparse arrays (i.e. input from 0 to 100000 and
has to be hashed to 0 to 100). I don't understand why you don't just
access the array directly using the passed value as an index. Then
again, I don't have that much experience using hashing (I learned it
about a month ago to make a spell checker) so if you do have a good
reason, I'd love to know what it is. :)
What is a "linear probing technique"?
--
Kim (OK...@max.tiac.net)
pcs$...@altair.selu.edu
> Hashing works best for sparse arrays (i.e. input from 0 to 100000 and
> has to be hashed to 0 to 100). I don't understand why you don't just
> access the array directly using the passed value as an index. Then
> again, I don't have that much experience using hashing (I learned it
> about a month ago to make a spell checker) so if you do have a good
> reason, I'd love to know what it is. :)
> What is a "linear probing technique?"
The reason I need to hash them from 0 to 99 is because there may be duplicate
indexes, therefore, a simple array won't work.
Linear probing means if something already occupies the position where the value
would be hashed to, you continue linearly until you find an empty position.
Jonathan Lawlor
>pcs$24...@altair.selu.edu wrote:
>>I'm looking for hashing code. I need to hash a number between 0 and 99 to a
>>100-element array. I would prefer a linear probing technique, but any others
>>would be welcome. Thanks.
>What kind of data do you intend to store? Is it a string, or some sort
>of record? If it is a record, what is the type of the key? Linear
>probing is not very efficient. Once you have a few collisions, the whole
>hash table degenerates into a sequential list. The reason is that when you
>try to resolve a collision, you'll need to go to another empty spot in
>your table, therefore increasing the chance of a subsequent collision.
>There are a number of ways to solve this. One way is to do something
>called double hashing. You apply the first hash function as normal. If
>there is a collision, you applied a second (different) hash function to
>determine the increment for the linear probing (simple linear probing
>uses an increment of 1).
The best function to use is a quadratic function to minimiize lumping.
>Another way to resolve collisions is to build a hash table of linked
>list. When you do get a collision, just add the item at the end (or the
>beginning) of the list. When you search for a particular item, all you
>have to do is to look at a particular list, and see if it's in the list
>or not. This technique will not increase the chance of a subsequent
>collision.
This is called open hashing. The problem with this is that it becomes a
linear search to go through the list which defeats the idea of hashing.
The best method is to use closed hashing (Rehashing collisions) with a
quadratic function to rehash.
To the orriginal poster: Why are you using a Hash Table to store numbers?
It doesn't make sense to me. It doesn't matter how many duplicates there
are. Why not use a bucket sort algorithm: Define an array of Integer, and
instead of hashing the item, use them as array indexes, then in each
spot in the array, store the amount of duplicates there are instead of storing
C
the duplicates themselves. This has the same efficiency as a perfect hash
search ( Order (1) )
Jonathan Lawlor
i
>--
>+--------------------------------------+----------------------------------+
>| Howard Cheng | hch...@gpu.srv.ualberta.ca |
>| University of Alberta | |
>+--------------------------------------+----------------------------------+
>Anyone who cannot cope with mathematics is not fully human. At best he
>is a tolerable subhuman who has learned to wear shoes, bathe and not
>make messes in the house. -- Lazarus Long, "Time Enough for Love"
Don
you're only dealing with a small number of elements like this you're much
better off to just to relative record addressing based on the element
number which I presume equates to some key somewhere....just setup a
structure and go for it.
Don
On 13 Apr 1994 pcs$24...@altair.selu.edu wrote:
> I'm looking for hashing code. I need to hash a number between 0 and 99 to a
> 100-element array. I would prefer a linear probing technique, but any others
> would be welcome. Thanks.
>
> Brad Crochet
>
> br...@indigo.awl.lsu.edu
> pcs$24...@selu.edu
>
Howard Cheng
>I'm looking for hashing code. I need to hash a number between 0 and 99 to a
>100-element array. I would prefer a linear probing technique, but any others
>would be welcome. Thanks.
What kind of data do you intend to store? Is it a string, or some sort
of record? If it is a record, what is the type of the key? Linear
probing is not very efficient. Once you have a few collisions, the whole
hash table degenerates into a sequential list. The reason is that when you
try to resolve a collision, you'll need to go to another empty spot in
your table, therefore increasing the chance of a subsequent collision.
There are a number of ways to solve this. One way is to do something
called double hashing. You apply the first hash function as normal. If
there is a collision, you applied a second (different) hash function to
determine the increment for the linear probing (simple linear probing
uses an increment of 1).
Another way to resolve collisions is to build a hash table of linked
list. When you do get a collision, just add the item at the end (or the
beginning) of the list. When you search for a particular item, all you
have to do is to look at a particular list, and see if it's in the list
or not. This technique will not increase the chance of a subsequent
collision.
--