totalcross.util

Class Hashtable4D<K,V>

java.lang.Object

java.util.Dictionary<K,V>

totalcross.util.Hashtable4D<K,V>

All Implemented Interfaces:

java.lang.Cloneable, java.util.Map<K,V>

public class Hashtable4D<K,V>
extends java.util.Dictionary<K,V>
implements java.util.Map<K,V>, java.lang.Cloneable

A class which implements a hashtable data structure.

This implementation of Hashtable uses a hash-bucket approach. That is: linear probing and rehashing is avoided; instead, each hashed value maps to a simple linked-list which, in the best case, only has one node. Assuming a large enough table, low enough load factor, and / or well implemented hashCode() methods, Hashtable should provide O(1) insertion, deletion, and searching of keys. Hashtable is O(n) in the worst case for all of these (if all keys hash to the same bucket).

This is a JDK-1.2 compliant implementation of Hashtable. As such, it belongs, partially, to the Collections framework (in that it implements Map). For backwards compatibility, it inherits from the obsolete and utterly useless Dictionary class.

Being a hybrid of old and new, Hashtable has methods which provide redundant capability, but with subtle and even crucial differences. For example, one can iterate over various aspects of a Hashtable with either an Iterator (which is the JDK-1.2 way of doing things) or with an Enumeration. The latter can end up in an undefined state if the Hashtable changes while the Enumeration is open.

Unlike HashMap, Hashtable does not accept `null' as a key value. Also, all accesses are synchronized: in a single thread environment, this is expensive, but in a multi-thread environment, this saves you the effort of extra synchronization. However, the old-style enumerators are not synchronized, because they can lead to unspecified behavior even if they were synchronized. You have been warned.

The iterators are fail-fast, meaning that any structural modification, except for remove() called on the iterator itself, cause the iterator to throw a ConcurrentModificationException rather than exhibit non-deterministic behavior.

Since:

1.0

See Also:

HashMap, TreeMap, IdentityHashMap, LinkedHashMap

Nested Class Summary

Nested classes/interfaces inherited from interface java.util.Map

java.util.Map.Entry<K,V>

Constructor Summary

Constructors

Constructor and Description
Hashtable4D() Construct a new Hashtable with the default capacity (11) and the default load factor (0.75).
Hashtable4D(int initialCapacity) Construct a new Hashtable with a specific inital capacity and default load factor of 0.75.
Hashtable4D(int initialCapacity, float loadFactor) Construct a new Hashtable with a specific initial capacity and load factor.
Hashtable4D(java.util.Map<? extends K,? extends V> m) Construct a new Hashtable from the given Map, with initial capacity the greater of the size of m or the default of 11.

Method Summary

Modifier and Type	Method and Description
void	clear() Clears the hashtable so it has no keys.
java.lang.Object	clone() Returns a shallow clone of this Hashtable.
boolean	contains(java.lang.Object value) Returns true if this Hashtable contains a value o, such that o.equals(value).
boolean	containsKey(java.lang.Object key) Returns true if the supplied object equals() a key in this Hashtable.
boolean	containsValue(java.lang.Object value) Returns true if this Hashtable contains a value o, such that o.equals(value).
java.util.Enumeration<V>	elements() Return an enumeration of the values of this table.
java.util.Set<java.util.Map.Entry<K,V>>	entrySet() Returns a "set view" of this Hashtable's entries.
boolean	equals(java.lang.Object o) Returns true if this Hashtable equals the supplied Object o.
V	get(java.lang.Object key) Return the value in this Hashtable associated with the supplied key, or null if the key maps to nothing.
int	hashCode() Returns the hashCode for this Hashtable.
boolean	isEmpty() Returns true if there are no key-value mappings currently in this table.
java.util.Enumeration<K>	keys() Return an enumeration of the keys of this table.
java.util.Set<K>	keySet() Returns a "set view" of this Hashtable's keys.
V	put(K key, V value) Puts the supplied value into the Map, mapped by the supplied key.
void	putAll(java.util.Map<? extends K,? extends V> m) Copies all elements of the given map into this hashtable.
protected void	rehash() Increases the size of the Hashtable and rehashes all keys to new array indices; this is called when the addition of a new value would cause size() > threshold.
V	remove(java.lang.Object key) Removes from the table and returns the value which is mapped by the supplied key.
int	size() Returns the number of key-value mappings currently in this hashtable.
java.lang.String	toString() Converts this Hashtable to a String, surrounded by braces, and with key/value pairs listed with an equals sign between, separated by a comma and space.
java.util.Collection<V>	values() Returns a "collection view" (or "bag view") of this Hashtable's values.

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Map

compute, computeIfAbsent, computeIfPresent, forEach, getOrDefault, merge, putIfAbsent, remove, replace, replace, replaceAll

Constructor Detail

Hashtable4D

public Hashtable4D()

Construct a new Hashtable with the default capacity (11) and the default load factor (0.75).

Hashtable4D

public Hashtable4D(java.util.Map<? extends K,? extends V> m)

Construct a new Hashtable from the given Map, with initial capacity the greater of the size of m or the default of 11.

Every element in Map m will be put into this new Hashtable.

Parameters:

m - a Map whose key / value pairs will be put into the new Hashtable. NOTE: key / value pairs are not cloned in this constructor.

Throws:

java.lang.NullPointerException - if m is null, or if m contains a mapping to or from `null'.

Since:

1.2

Hashtable4D

public Hashtable4D(int initialCapacity)

Construct a new Hashtable with a specific inital capacity and default load factor of 0.75.

Parameters:

initialCapacity - the initial capacity of this Hashtable (>= 0)

Throws:

java.lang.IllegalArgumentException - if (initialCapacity < 0)

Hashtable4D

public Hashtable4D(int initialCapacity,
                   float loadFactor)

Construct a new Hashtable with a specific initial capacity and load factor.

Parameters:

initialCapacity - the initial capacity (>= 0)

loadFactor - the load factor (> 0, not NaN)

Throws:

java.lang.IllegalArgumentException - if (initialCapacity < 0) || ! (loadFactor > 0.0)

Method Detail

size

public int size()

Returns the number of key-value mappings currently in this hashtable.

Specified by:

size in interface java.util.Map<K,V>

Specified by:

size in class java.util.Dictionary<K,V>

Returns:

the size

isEmpty

public boolean isEmpty()

Returns true if there are no key-value mappings currently in this table.

Specified by:

isEmpty in interface java.util.Map<K,V>

Specified by:

isEmpty in class java.util.Dictionary<K,V>

Returns:

size() == 0

keys

public java.util.Enumeration<K> keys()

Return an enumeration of the keys of this table. There's no point in synchronizing this, as you have already been warned that the enumeration is not specified to be thread-safe.

Specified by:

keys in class java.util.Dictionary<K,V>

Returns:

the keys

See Also:

elements(), keySet()

elements

public java.util.Enumeration<V> elements()

Return an enumeration of the values of this table. There's no point in synchronizing this, as you have already been warned that the enumeration is not specified to be thread-safe.

Specified by:

elements in class java.util.Dictionary<K,V>

Returns:

the values

See Also:

keys(), values()

contains

public boolean contains(java.lang.Object value)

Returns true if this Hashtable contains a value o, such that o.equals(value). This is the same as containsValue(), and is O(n).

Parameters:

value - the value to search for in this Hashtable

Returns:

true if at least one key maps to the value

Throws:

java.lang.NullPointerException - if value is null

See Also:

containsValue(Object), containsKey(Object)

containsValue

public boolean containsValue(java.lang.Object value)

Returns true if this Hashtable contains a value o, such that o.equals(value). This is the new API for the old contains().

Specified by:

containsValue in interface java.util.Map<K,V>

Parameters:

value - the value to search for in this Hashtable

Returns:

true if at least one key maps to the value

Throws:

java.lang.NullPointerException - if value is null

Since:

1.2

See Also:

contains(Object), containsKey(Object)

containsKey

public boolean containsKey(java.lang.Object key)

Returns true if the supplied object equals() a key in this Hashtable.

Specified by:

containsKey in interface java.util.Map<K,V>

Parameters:

key - the key to search for in this Hashtable

Returns:

true if the key is in the table

Throws:

java.lang.NullPointerException - if key is null

See Also:

containsValue(Object)

get

public V get(java.lang.Object key)

Return the value in this Hashtable associated with the supplied key, or null if the key maps to nothing.

Specified by:

get in interface java.util.Map<K,V>

Specified by:

get in class java.util.Dictionary<K,V>

Parameters:

key - the key for which to fetch an associated value

Returns:

what the key maps to, if present

Throws:

java.lang.NullPointerException - if key is null

See Also:

put(Object, Object), containsKey(Object)

put

public V put(K key,
             V value)

Puts the supplied value into the Map, mapped by the supplied key. Neither parameter may be null. The value may be retrieved by any object which equals() this key.

Specified by:

put in interface java.util.Map<K,V>

Specified by:

put in class java.util.Dictionary<K,V>

Parameters:

key - the key used to locate the value

value - the value to be stored in the table

Returns:

the prior mapping of the key, or null if there was none

Throws:

java.lang.NullPointerException - if key or value is null

See Also:

get(Object), Object.equals(Object)

remove

public V remove(java.lang.Object key)

Removes from the table and returns the value which is mapped by the supplied key. If the key maps to nothing, then the table remains unchanged, and null is returned.

Specified by:

remove in interface java.util.Map<K,V>

Specified by:

remove in class java.util.Dictionary<K,V>

Parameters:

key - the key used to locate the value to remove

Returns:

whatever the key mapped to, if present

putAll

public void putAll(java.util.Map<? extends K,? extends V> m)

Copies all elements of the given map into this hashtable. However, no mapping can contain null as key or value. If this table already has a mapping for a key, the new mapping replaces the current one.

Specified by:

putAll in interface java.util.Map<K,V>

Parameters:

m - the map to be hashed into this

Throws:

java.lang.NullPointerException - if m is null, or contains null keys or values

clear

public void clear()

Clears the hashtable so it has no keys. This is O(1).

Specified by:

clear in interface java.util.Map<K,V>

clone

public java.lang.Object clone()

Returns a shallow clone of this Hashtable. The Map itself is cloned, but its contents are not. This is O(n).

Overrides:

clone in class java.lang.Object

Returns:

the clone

toString

public java.lang.String toString()

Converts this Hashtable to a String, surrounded by braces, and with key/value pairs listed with an equals sign between, separated by a comma and space. For example, "{a=1, b=2}".

NOTE: if the toString() method of any key or value throws an exception, this will fail for the same reason.

Overrides:

toString in class java.lang.Object

Returns:

the string representation

keySet

public java.util.Set<K> keySet()

Returns a "set view" of this Hashtable's keys. The set is backed by the hashtable, so changes in one show up in the other. The set supports element removal, but not element addition. The set is properly synchronized on the original hashtable. Sun has not documented the proper interaction of null with this set, but has inconsistent behavior in the JDK. Therefore, in this implementation, contains, remove, containsAll, retainAll, removeAll, and equals just ignore a null key rather than throwing a NullPointerException.

Specified by:

keySet in interface java.util.Map<K,V>

Returns:

a set view of the keys

Since:

1.2

See Also:

values(), entrySet()

values

public java.util.Collection<V> values()

Returns a "collection view" (or "bag view") of this Hashtable's values. The collection is backed by the hashtable, so changes in one show up in the other. The collection supports element removal, but not element addition. The collection is properly synchronized on the original hashtable. Sun has not documented the proper interaction of null with this set, but has inconsistent behavior in the JDK. Therefore, in this implementation, contains, remove, containsAll, retainAll, removeAll, and equals just ignore a null value rather than throwing a NullPointerException.

Specified by:

values in interface java.util.Map<K,V>

Returns:

a bag view of the values

Since:

1.2

See Also:

keySet(), entrySet()

entrySet

public java.util.Set<java.util.Map.Entry<K,V>> entrySet()

Returns a "set view" of this Hashtable's entries. The set is backed by the hashtable, so changes in one show up in the other. The set supports element removal, but not element addition. The set is properly synchronized on the original hashtable. Sun has not documented the proper interaction of null with this set, but has inconsistent behavior in the JDK. Therefore, in this implementation, contains, remove, containsAll, retainAll, removeAll, and equals just ignore a null entry, or an entry with a null key or value, rather than throwing a NullPointerException. However, calling entry.setValue(null) will fail.

Note that the iterators for all three views, from keySet(), entrySet(), and values(), traverse the hashtable in the same sequence.

Specified by:

entrySet in interface java.util.Map<K,V>

Returns:

a set view of the entries

Since:

1.2

See Also:

keySet(), values(), Map.Entry

equals

public boolean equals(java.lang.Object o)

Returns true if this Hashtable equals the supplied Object o. As specified by Map, this is: (o instanceof Map) && entrySet().equals(((Map) o).entrySet());

Specified by:

equals in interface java.util.Map<K,V>

Overrides:

equals in class java.lang.Object

Parameters:

o - the object to compare to

Returns:

true if o is an equal map

Since:

1.2

hashCode

public int hashCode()

Returns the hashCode for this Hashtable. As specified by Map, this is the sum of the hashCodes of all of its Map.Entry objects

Specified by:

hashCode in interface java.util.Map<K,V>

Overrides:

hashCode in class java.lang.Object

Returns:

the sum of the hashcodes of the entries

Since:

1.2

rehash

protected void rehash()

Increases the size of the Hashtable and rehashes all keys to new array indices; this is called when the addition of a new value would cause size() > threshold. Note that the existing Entry objects are reused in the new hash table.

This is not specified, but the new size is twice the current size plus one; this number is not always prime, unfortunately. This implementation is not synchronized, as it is only invoked from synchronized methods.