From 0caade1b544071ecef4601f2dbe786496677ead8 Mon Sep 17 00:00:00 2001
From: Tom Tromey <tromey@redhat.com>
Date: Thu, 27 Sep 2001 16:49:13 +0000
Subject: IdentityHashMap.java (containsKey): Use getHash.
* java/util/IdentityHashMap.java (containsKey): Use getHash.
(get): Likewise.
(put): Likewise.
(remove): Likewise.
(getHash): New method.
(tombstone, emptyslot): Now static final.
(put): Correctly determine when to rehash, and correctly rehash.
(containsKey, remove): Test against table length with `>='.
From-SVN: r45841
---
libjava/java/util/IdentityHashMap.java | 29 ++++++++++++++++++-----------
1 file changed, 18 insertions(+), 11 deletions(-)
(limited to 'libjava/java/util/IdentityHashMap.java')
diff --git a/libjava/java/util/IdentityHashMap.java b/libjava/java/util/IdentityHashMap.java
index c23f8ac..da028ed 100644
--- a/libjava/java/util/IdentityHashMap.java
+++ b/libjava/java/util/IdentityHashMap.java
@@ -103,7 +103,7 @@ public class IdentityHashMap extends AbstractMap
public boolean containsKey (Object key)
{
- int h = Math.abs (2 * System.identityHashCode (key) % table.length);
+ int h = getHash (key);
int save = h;
while (true)
{
@@ -112,7 +112,7 @@ public class IdentityHashMap extends AbstractMap
if (table[h] == emptyslot)
return false;
h += 2;
- if (h > table.length)
+ if (h >= table.length)
h = 0;
if (h == save)
return false;
@@ -174,7 +174,7 @@ public class IdentityHashMap extends AbstractMap
public Object get (Object key)
{
- int h = Math.abs (2 * System.identityHashCode (key) % table.length);
+ int h = getHash (key);
int save = h;
while (true)
{
@@ -230,14 +230,15 @@ public class IdentityHashMap extends AbstractMap
public Object put (Object key, Object value)
{
- // Rehash is the load factor is too high.
- if (size * 3 / 2 > table.length)
+ // Rehash if the load factor is too high. We use a factor of 1.5
+ // -- the division by 2 is implicit on both sides.
+ if (size * 3 > table.length)
{
Object[] old = table;
table = new Object[old.length * 2];
Arrays.fill (table, emptyslot);
size = 0;
- for (int i = 0; i < old.length; ++i)
+ for (int i = 0; i < old.length; i += 2)
{
if (old[i] != tombstone && old[i] != emptyslot)
{
@@ -248,7 +249,7 @@ public class IdentityHashMap extends AbstractMap
}
}
- int h = Math.abs (2 * System.identityHashCode (key) % table.length);
+ int h = getHash (key);
int save = h;
int del = -1;
while (true)
@@ -288,7 +289,7 @@ public class IdentityHashMap extends AbstractMap
public Object remove (Object key)
{
- int h = Math.abs (2 * System.identityHashCode (key) % table.length);
+ int h = getHash (key);
int save = h;
while (true)
{
@@ -301,7 +302,7 @@ public class IdentityHashMap extends AbstractMap
return r;
}
h += 2;
- if (h > table.length)
+ if (h >= table.length)
h = 0;
if (h == save)
break;
@@ -413,14 +414,20 @@ public class IdentityHashMap extends AbstractMap
}
}
+ // Compute the hash value we will use for an object.
+ private int getHash (Object o)
+ {
+ return 2 * Math.abs (System.identityHashCode (o) % (table.length / 2));
+ }
+
// Number of items in hash table.
private int size;
// The table itself.
private Object[] table;
// This object is used to mark deleted items.
- private Object tombstone = new Object ();
+ private static final Object tombstone = new Object ();
// This object is used to mark empty slots. We need this because
// using null is ambiguous.
- private Object emptyslot = new Object ();
+ private static final Object emptyslot = new Object ();
}
--
cgit v1.1