Home.... | log in.... | Pub my question! | Sign-up....

Java-index >> Administration Tools >> Sun Connection

Hashtable alternatives

I need to store a key-value index for fast lookup, is there an alternative to the Hashtable class that does not have the overwrite problem?Is HashSet a viable alternative or does this class have the same problem?And help appreciated, thanks.

[262 byte] By [Znorka] at [2007-10-2 4:06:31]

«« NetBeans 4.1 and projects with existing sources: NoSuchMethodError
»» trying to use javah -jni

# 1

Just wanted to clarify that by overwrite problem I ment the problem where two different hash values generates the same table index.

An example for clarity:

The index of a key is calculated as follows:

int index = (hash & 0x7FFFFFFF) % tab.length;

This means that a Hashtable with 10 slots you can have two hashkeys result in the same index as follows:

int index = (-1812862863 & 0x7FFFFFFF) % 10) = 4

int index = (1261919223 & 0x7FFFFFFF) % 10) = 4

Since the Hashtable.put() method does not chech if the index is empty before inserting, this will result in the loss of the first inserted value.

My question is; Is there any standard key-index Java functionality that does not have this problem, or will I have to overwrite the put() method for Hashtable?

Znorka at 2007-7-15 23:29:23 >

top of Java-index,Administration Tools,Sun Connection...

# 2

Each slot of a Hashtable is a linklist of items with the same hash. If two items hash to the same value but are not equal() then they will go to the same "slot".

Caffeine0001a at 2007-7-15 23:29:23 >

# 3

> Since the Hashtable.put() method does not chech if

> the index is empty before inserting, this will result

> in the loss of the first inserted value.

In general this is false according to your example: This statement is only true if the hashed key and the two objects are equal(). Since this is true for only "equal" objects you have no problem. Test it for self. Have two different objects return the same Hashcode and are not equal to each other. They will both exist in the Hashtable.

Caffeine0001a at 2007-7-15 23:29:23 >

# 4

as far as i understand, you want to make shure, that ANY non-equal object has its own key?

then, you should use the object's hashcode.

without casting, you'll get it with:

System.identityHashCode(Object x);

but you'll have to write additional code that uses this hashcode, i guess.

look what the api says:

Returns the same hash code for the given object as would be returned by the default method hashCode(), whether or not the given object's class overrides hashCode(). The hash code for the null reference is zero.

/meta

metaa at 2007-7-15 23:29:23 >

# 5

It is an inherent property of hashing. You should use some appropriate hashing function, that is, which does not produce too much collisions on the given range of objects.

BIJ001a at 2007-7-15 23:29:23 >

# 6

> It is an inherent property of hashing. You should use

> some appropriate hashing function, that is, which

> does not produce too much collisions on the given

> range of objects.

that's an interesting field........

what happens if i try to generate as many objects (of the very same class!) as Integer.MAX_VALUE?

will the identityHashCode guarantee that there will be no collsions?

if NOT, how object (and by saying this we mean it's reference"value") equality is assured? there must be something unique about any object that the VM knows to find the right one? which value IS that?

i thought the hash would - in conjunction with the class information - provide a 100% sure match?

if we use a long for hashing, the first 32 bits for the classes hash and the last 32 bits for the object's hash, would this definitely be unique?

that would of course limit the total amount of live objects at a time.... to 2^32 per class.... even with 4 GB ram that should be enough ;)

metaa at 2007-7-15 23:29:23 >

# 7

It all depends on your hashing algorithm.

If the hashcode is identical, objects are placed in the same bucket.

If on retrieval a bucket is found to contain more than one item the actual object to get is determined based on which of the ones in the bucket compares using equals()

For insertion the reverse is true.

First hashcode is used to determine the bucket, then the object is inserted into the bucket.

If the key is already used, the object that used to use that key is replaced in the hashtable with the new one.

jwentinga at 2007-7-15 23:29:23 >

# 8

hm. i just stumbled over that looking at the api again:

( Object.hashCode() )

As much as is reasonably practical, the hashCode method defined by class Object does return distinct integers for distinct objects. (This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the JavaTM programming language.)

huh ?!

i'd rather like to, but i can't rely on that?

just wondering

/meta

metaa at 2007-7-15 23:29:23 >

Sun Connection

Java programming resources: FAQs, tutorials, compiler and browser download sites, documentation, books lists, IDEs, etc.

Hashtable alternatives

Administration Tools New Topic

Administration Tools Hot Topic

Administration Tools

All Classified