Re: Hash Code Compression

From:

Patricia Shanahan <pats@acm.org>

Newsgroups:

comp.lang.java.programmer

Date:

Sat, 12 Jan 2008 07:48:19 -0800

Message-ID:

<fmang5$1d96$1@ihnp4.ucsd.edu>

j1mb0jay wrote:

Charles wrote:

On Jan 11, 5:11 pm, j1mb0jay <n...@none.com> wrote:

I am currently working on a dictionary populating program. I currently
have a socket connection my local news server and am trawling through
all of the articles looking for new words. Java's String class has a
method that hashes strings. I was wondering if i should still be using
these even though I have over two million words in the hash table.
Although the hash table is currently Big 0(4).

I am using the Multiply Add and Divide (MAD) method for the compression
of the hash code, does Java have any built in functions(methods) that
will do this for me, or does anyone know of a more efficient way?

j1mb0jay

Hi Group:

I don't know much about the MAD method, but LZW is another useful
compression technique. I consider compression akin to folding spaces.
I also think of greatest common divisor algorithms.

I am thinking of it, but I am not showing how to use it. Sorry.

If you have time implement two solutions and continuously improve.

You could also look up compression patents.

:-)

Good luck.

I am not trying to compress a file or image so Lempel-Ziv-Welch
Compression wont work for me (or so i think), i just want to compress an
integer so i can use it as a index to a fixed size array. I seem to have
improved my current method by by simply using the % of the 2 number and
the size of the array!!!

j1mb0jay

I think the situation would be clearer if you thought of it, and
described it, as the mapping from hash code to hash table bucket number.

In the current situation, with a hash function that returns a 32 bit int
and a relatively small hash table, the mapping will be a compression
algorithm in the sense that the range is smaller than the domain, but
the important properties are different.

The main property you need is a tendency for the mapping from a String
representing a word, through the String's hash code, to the bucket
number, to distribute words as evenly as possible among buckets. That
does not correspond to any normal requirement on compression algorithms.

Patricia