totalcross.util

Class HashMap4D<K,V>

java.lang.Object

totalcross.util.AbstractMap4D<K,V>

totalcross.util.HashMap4D<K,V>

All Implemented Interfaces:

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

Direct Known Subclasses:

LinkedHashMap4D

public class HashMap4D<K,V>
extends AbstractMap4D<K,V>
implements java.util.Map<K,V>, java.lang.Cloneable

This class provides a hashtable-backed implementation of the Map interface.

It uses a hash-bucket approach; that is, hash collisions are handled by linking the new node off of the pre-existing node (or list of nodes). In this manner, techniques such as linear probing (which can cause primary clustering) and rehashing (which does not fit very well with Java's method of precomputing hash codes) are avoided.

Under ideal circumstances (no collisions), HashMap offers O(1) performance on most operations (containsValue() is, of course, O(n)). In the worst case (all keys map to the same hash code -- very unlikely), most operations are O(n).

HashMap is part of the JDK1.2 Collections API. It differs from Hashtable in that it accepts the null key and null values, and it does not support "Enumeration views." Also, it is not synchronized; if you plan to use it in multiple threads, consider using:
Map m = Collections.synchronizedMap(new HashMap(...));

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.2

See Also:

Object.hashCode(), Collection, Map, TreeMap, LinkedHashMap, IdentityHashMap, Hashtable

Nested Class Summary

Nested classes/interfaces inherited from class totalcross.util.AbstractMap4D

AbstractMap4D.SimpleEntry<K,V>, AbstractMap4D.SimpleImmutableEntry<K,V>

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

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

Constructor Summary

Constructors

Constructor and Description
HashMap4D() Construct a new HashMap with the default capacity (11) and the default load factor (0.75).
HashMap4D(int initialCapacity) Construct a new HashMap with a specific inital capacity and default load factor of 0.75.
HashMap4D(int initialCapacity, double loadFactor) Construct a new HashMap with a specific inital capacity and load factor.
HashMap4D(java.util.Map<? extends K,? extends V> m) Construct a new HashMap 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 Map so it has no keys.
java.lang.Object	clone() Returns a shallow clone of this HashMap.
boolean	containsKey(java.lang.Object key) Returns true if the supplied object equals() a key in this HashMap.
boolean	containsValue(java.lang.Object value) Returns true if this HashMap contains a value o, such that o.equals(value).
java.util.Set<java.util.Map.Entry<K,V>>	entrySet() Returns a "set view" of this HashMap's entries.
V	get(java.lang.Object key) Return the value in this HashMap associated with the supplied key, or null if the key maps to nothing.
V	getOrDefault(java.lang.Object key, V def)
int	hash(java.lang.Object key) Helper method that returns an index in the buckets array for `key' based on its hashCode().
boolean	isEmpty() Returns true if there are no key-value mappings currently in this Map.
java.util.Set<K>	keySet() Returns a "set view" of this HashMap'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.
V	remove(java.lang.Object key) Removes from the HashMap and returns the value which is mapped by the supplied key.
int	size() Returns the number of kay-value mappings currently in this Map.
java.util.Collection<V>	values() Returns a "collection view" (or "bag view") of this HashMap's values.

Methods inherited from class totalcross.util.AbstractMap4D

equals, equals, hashCode, hashCode, toString

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Map

compute, computeIfAbsent, computeIfPresent, equals, forEach, hashCode, merge, putIfAbsent, remove, replace, replace, replaceAll

Constructor Detail

HashMap4D

public HashMap4D()

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

HashMap4D

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

Construct a new HashMap 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 HashMap.

Parameters:

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

Throws:

java.lang.NullPointerException - if m is null

HashMap4D

public HashMap4D(int initialCapacity)

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

Parameters:

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

Throws:

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

HashMap4D

public HashMap4D(int initialCapacity,
                 double loadFactor)

Construct a new HashMap with a specific inital 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 kay-value mappings currently in this Map.

Specified by:

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

Overrides:

size in class AbstractMap4D<K,V>

Returns:

the size

See Also:

Set.size()

isEmpty

public boolean isEmpty()

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

Specified by:

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

Overrides:

isEmpty in class AbstractMap4D<K,V>

Returns:

size() == 0

See Also:

AbstractMap4D.size()

get

public V get(java.lang.Object key)

Return the value in this HashMap associated with the supplied key, or null if the key maps to nothing. NOTE: Since the value could also be null, you must use containsKey to see if this key actually maps to something.

Specified by:

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

Overrides:

get in class AbstractMap4D<K,V>

Parameters:

key - the key for which to fetch an associated value

Returns:

what the key maps to, if present

See Also:

put(Object, Object), containsKey(Object)

getOrDefault

public V getOrDefault(java.lang.Object key,
                      V def)

Specified by:

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

containsKey

public boolean containsKey(java.lang.Object key)

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

Specified by:

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

Overrides:

containsKey in class AbstractMap4D<K,V>

Parameters:

key - the key to search for in this HashMap

Returns:

true if the key is in the table

See Also:

containsValue(Object)

put

public V put(K key,
             V value)

Puts the supplied value into the Map, mapped by the supplied key. The value may be retrieved by any object which equals() this key. NOTE: Since the prior value could also be null, you must first use containsKey if you want to see if you are replacing the key's mapping.

Specified by:

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

Overrides:

put in class AbstractMap4D<K,V>

Parameters:

key - the key used to locate the value

value - the value to be stored in the HashMap

Returns:

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

See Also:

get(Object), Object.equals(Object)

putAll

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

Copies all elements of the given map into this hashtable. 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>

Overrides:

putAll in class AbstractMap4D<K,V>

Parameters:

m - the map to be hashed into this

See Also:

AbstractMap4D.put(Object, Object)

remove

public V remove(java.lang.Object key)

Removes from the HashMap and returns the value which is mapped by the supplied key. If the key maps to nothing, then the HashMap remains unchanged, and null is returned. NOTE: Since the value could also be null, you must use containsKey to see if you are actually removing a mapping.

Specified by:

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

Overrides:

remove in class AbstractMap4D<K,V>

Parameters:

key - the key used to locate the value to remove

Returns:

whatever the key mapped to, if present

See Also:

Iterator.remove()

clear

public void clear()

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

Specified by:

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

Overrides:

clear in class AbstractMap4D<K,V>

See Also:

Set.clear()

containsValue

public boolean containsValue(java.lang.Object value)

Returns true if this HashMap contains a value o, such that o.equals(value).

Specified by:

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

Overrides:

containsValue in class AbstractMap4D<K,V>

Parameters:

value - the value to search for in this HashMap

Returns:

true if at least one key maps to the value

See Also:

containsKey(Object)

clone

public java.lang.Object clone()

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

Overrides:

clone in class AbstractMap4D<K,V>

Returns:

the clone

See Also:

Cloneable, Object.clone()

keySet

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

Returns a "set view" of this HashMap's keys. The set is backed by the HashMap, so changes in one show up in the other. The set supports element removal, but not element addition.

Specified by:

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

Overrides:

keySet in class AbstractMap4D<K,V>

Returns:

a set view of the keys

See Also:

values(), entrySet()

values

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

Returns a "collection view" (or "bag view") of this HashMap's values. The collection is backed by the HashMap, so changes in one show up in the other. The collection supports element removal, but not element addition.

Specified by:

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

Overrides:

values in class AbstractMap4D<K,V>

Returns:

a bag view of the values

See Also:

keySet(), entrySet()

entrySet

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

Returns a "set view" of this HashMap's entries. The set is backed by the HashMap, so changes in one show up in the other. The set supports element removal, but not element addition.

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

Specified by:

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

Specified by:

entrySet in class AbstractMap4D<K,V>

Returns:

a set view of the entries

See Also:

keySet(), values(), Map.Entry

hash

public final int hash(java.lang.Object key)

Helper method that returns an index in the buckets array for `key' based on its hashCode(). Package visible for use by subclasses.

Parameters:

key - the key

Returns:

the bucket number