|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectorg.apache.commons.math.util.OpenIntToFieldHashMap<T>
T
- the type of the field elementspublic class OpenIntToFieldHashMap<T extends FieldElement<T>>
Open addressed map from int to FieldElement.
This class provides a dedicated map from integers to FieldElements with a
much smaller memory overhead than standard java.util.Map
.
This class is not synchronized. The specialized iterators returned by
iterator()
are fail-fast: they throw a
ConcurrentModificationException
when they detect the map has been
modified during iteration.
Nested Class Summary | |
---|---|
class |
OpenIntToFieldHashMap.Iterator
Iterator class for the map. |
Field Summary | |
---|---|
private int |
count
Modifications count. |
private static int |
DEFAULT_EXPECTED_SIZE
Default starting size. |
private Field<T> |
field
Field to which the elements belong. |
protected static byte |
FREE
Status indicator for free table entries. |
protected static byte |
FULL
Status indicator for full table entries. |
private int[] |
keys
Keys table. |
private static float |
LOAD_FACTOR
Load factor for the map. |
private int |
mask
Bit mask for hash values. |
private T |
missingEntries
Return value for missing entries. |
private static int |
PERTURB_SHIFT
Number of bits to perturb the index when probing for collision resolution. |
protected static byte |
REMOVED
Status indicator for removed table entries. |
private static int |
RESIZE_MULTIPLIER
Multiplier for size growth when map fills up. |
private static long |
serialVersionUID
Serializable version identifier. |
private int |
size
Current size of the map. |
private byte[] |
states
States table. |
private T[] |
values
Values table. |
Constructor Summary | |
---|---|
OpenIntToFieldHashMap(Field<T> field)
Build an empty map with default size and using zero for missing entries. |
|
OpenIntToFieldHashMap(Field<T> field,
int expectedSize)
Build an empty map with specified size and using zero for missing entries. |
|
OpenIntToFieldHashMap(Field<T> field,
int expectedSize,
T missingEntries)
Build an empty map with specified size. |
|
OpenIntToFieldHashMap(Field<T> field,
T missingEntries)
Build an empty map with default size |
|
OpenIntToFieldHashMap(OpenIntToFieldHashMap<T> source)
Copy constructor. |
Method Summary | |
---|---|
private T[] |
buildArray(int length)
Build an array of elements. |
private static int |
changeIndexSign(int index)
Change the index sign |
private static int |
computeCapacity(int expectedSize)
Compute the capacity needed for a given size. |
boolean |
containsKey(int key)
Check if a value is associated with a key. |
private boolean |
containsKey(int key,
int index)
Check if the tables contain an element associated with specified key at specified index. |
private T |
doRemove(int index)
Remove an element at specified index. |
private int |
findInsertionIndex(int key)
Find the index at which a key should be inserted |
private static int |
findInsertionIndex(int[] keys,
byte[] states,
int key,
int mask)
Find the index at which a key should be inserted |
T |
get(int key)
Get the stored value associated with the given key |
private void |
growTable()
Grow the tables. |
private static int |
hashOf(int key)
Compute the hash value of a key |
OpenIntToFieldHashMap.Iterator |
iterator()
Get an iterator over map elements. |
private static int |
nextPowerOfTwo(int i)
Find the smallest power of two greater than the input value |
private static int |
perturb(int hash)
Perturb the hash for starting probing. |
private static int |
probe(int perturb,
int j)
Compute next probe for collision resolution |
T |
put(int key,
T value)
Put a value associated with a key in the map. |
private void |
readObject(java.io.ObjectInputStream stream)
Read a serialized object. |
T |
remove(int key)
Remove the value associated with a key. |
private boolean |
shouldGrowTable()
Check if tables should grow due to increased size. |
int |
size()
Get the number of elements stored in the map. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
---|
private static final long serialVersionUID
private static final float LOAD_FACTOR
private static final int DEFAULT_EXPECTED_SIZE
This must be a power of two for bit mask to work properly.
private static final int RESIZE_MULTIPLIER
This must be a power of two for bit mask to work properly.
private static final int PERTURB_SHIFT
protected static final byte FREE
protected static final byte FULL
protected static final byte REMOVED
private final Field<T extends FieldElement<T>> field
private int[] keys
private T extends FieldElement<T>[] values
private byte[] states
private final T extends FieldElement<T> missingEntries
private int size
private int mask
private transient int count
Constructor Detail |
---|
public OpenIntToFieldHashMap(Field<T> field)
field
- field to which the elements belongpublic OpenIntToFieldHashMap(Field<T> field, T missingEntries)
field
- field to which the elements belongmissingEntries
- value to return when a missing entry is fetchedpublic OpenIntToFieldHashMap(Field<T> field, int expectedSize)
field
- field to which the elements belongexpectedSize
- expected number of elements in the mappublic OpenIntToFieldHashMap(Field<T> field, int expectedSize, T missingEntries)
field
- field to which the elements belongexpectedSize
- expected number of elements in the mapmissingEntries
- value to return when a missing entry is fetchedpublic OpenIntToFieldHashMap(OpenIntToFieldHashMap<T> source)
source
- map to copyMethod Detail |
---|
private static int computeCapacity(int expectedSize)
expectedSize
- expected size of the map
private static int nextPowerOfTwo(int i)
i
- input value
public T get(int key)
key
- key associated with the data
public boolean containsKey(int key)
key
- key to check
public OpenIntToFieldHashMap.Iterator iterator()
The specialized iterators returned are fail-fast: they throw a
ConcurrentModificationException
when they detect the map
has been modified during iteration.
private static int perturb(int hash)
hash
- initial hash
private int findInsertionIndex(int key)
key
- key to lookup
private static int findInsertionIndex(int[] keys, byte[] states, int key, int mask)
keys
- keys tablestates
- states tablekey
- key to lookupmask
- bit mask for hash values
private static int probe(int perturb, int j)
perturb
- perturbed hashj
- previous probe
private static int changeIndexSign(int index)
index
- initial index
public int size()
public T remove(int key)
key
- key to which the value is associated
private boolean containsKey(int key, int index)
key
- key to checkindex
- index to check
private T doRemove(int index)
index
- index of the element to remove
public T put(int key, T value)
key
- key to which value is associatedvalue
- value to put in the map
private void growTable()
private boolean shouldGrowTable()
private static int hashOf(int key)
key
- key to hash
private void readObject(java.io.ObjectInputStream stream) throws java.io.IOException, java.lang.ClassNotFoundException
stream
- input stream
java.io.IOException
- if object cannot be read
java.lang.ClassNotFoundException
- if the class corresponding
to the serialized object cannot be foundprivate T[] buildArray(int length)
length
- size of the array to build
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |