| java.lang.Object
 com.hp.hpl.jena.mem.HashCommon
All known Subclasses: com.hp.hpl.jena.mem.HashedBunchMap, com.hp.hpl.jena.mem.HashedTripleBunch,
| HashCommon | | abstract public class HashCommon (Code) | | Shared stuff for our hashing implementations: does the base work for
hashing and growth sizes.
author:
kers |
| Inner Class :public static interface NotifyEmpty | |
| Inner Class :final protected class MovedKeysIterator extends NiceIterator | |
| Inner Class :final protected class BasicKeyIterator extends NiceIterator | |
| Field Summary | |
| public int | capacity
The capacity (length) of the key array. | | protected int | changes
A count of the number of changes applied to this Hash object, used for
detecting concurrent modifications. | | protected Object[] | keys
The keys of whatever table it is we're implementing. | | final protected static double | loadFactor
Jeremy suggests, from his experiments, that load factors more than
0.6 leave the table too dense, and little advantage is gained below 0.4.
Although that was with a quadratic probe, I'm borrowing the same
plausible range, and use 0.5 by default. | | final static int[] | primes
| | protected int | size
The number of active elements in the table, maintained incrementally. | | protected int | threshold
The threshold number of elements above which we resize the table;
equal to the capacity times the load factor. |
| Constructor Summary | |
| protected | HashCommon(int initialCapacity)
Initialise this hashed thingy to have initialCapacity as its
capacity and the corresponding threshold. |
| Method Summary | |
| final protected int | findSlot(Object key)
Search for the slot in which key is found. | | public Object | getItemForTestingAt(int i)
Answer the item at index i of keys. | | protected void | growCapacityAndThreshold()
Work out the capacity and threshold sizes for a new improved bigger
table (bigger by a factor of two, at present). | | protected int | improveHashCode(int hashCode)
Answer the transformed hash code, intended to be an improvement
on the objects own hashcode. | | final protected int | initialIndexFor(Object key)
Answer the initial index for the object key in the table.
With luck, this will be the final position for that object. | | public ExtendedIterator | keyIterator()
| | public ExtendedIterator | keyIterator(NotifyEmpty container)
| | protected void | moveAssociatedValues(int here, int scan)
When removeFrom [or remove] moves a key, it calls this method to move
any associated values, passing in the index of the slot here
to move to and the index of the slot scan to move from. | | protected static int | nextSize(int atLeast)
| | public void | remove(Object key)
Remove the object key from this hash's keys if it
is present (if it's absent, do nothing). | | protected void | removeAssociatedValues(int here)
When removeFrom [or remove] removes a key, it calls this method to
remove any associated values, passing in the index of the key's slot. | | protected Object | removeFrom(int here)
Remove the triple at element i of contents.
This is an implementation of Knuth's Algorithm R from tAoCP vol3, p 527,
with exchanging of the roles of i and j so that they can be usefully renamed
to here and scan.
It relies on linear probing but doesn't require a distinguished REMOVED
value. | | void | showkeys()
|
| capacity | | public int capacity(Code) | | The capacity (length) of the key array.
|
| changes | | protected int changes(Code) | | A count of the number of changes applied to this Hash object, used for
detecting concurrent modifications.
|
| keys | | protected Object[] keys(Code) | | The keys of whatever table it is we're implementing. Since we share code
for triple sets and for node->bunch maps, it has to be an Object array; we
take the casting hit.
|
| loadFactor | | final protected static double loadFactor(Code) | | Jeremy suggests, from his experiments, that load factors more than
0.6 leave the table too dense, and little advantage is gained below 0.4.
Although that was with a quadratic probe, I'm borrowing the same
plausible range, and use 0.5 by default.
|
| primes | | final static int[] primes(Code) | | |
| size | | protected int size(Code) | | The number of active elements in the table, maintained incrementally.
|
| threshold | | protected int threshold(Code) | | The threshold number of elements above which we resize the table;
equal to the capacity times the load factor.
|
| HashCommon | | protected HashCommon(int initialCapacity)(Code) | | Initialise this hashed thingy to have initialCapacity as its
capacity and the corresponding threshold. All the key elements start out
null.
|
| findSlot | | final protected int findSlot(Object key)(Code) | | Search for the slot in which key is found. If it is absent,
return the index of the free slot in which it could be placed. If it is present,
return the bitwise complement of the index of the slot it appears in. Hence
negative values imply present, positive absent, and there's no confusion
around 0.
|
| getItemForTestingAt | | public Object getItemForTestingAt(int i)(Code) | | Answer the item at index i of keys. This
method is for testing purposes only.
|
| growCapacityAndThreshold | | protected void growCapacityAndThreshold()(Code) | | Work out the capacity and threshold sizes for a new improved bigger
table (bigger by a factor of two, at present).
|
| improveHashCode | | protected int improveHashCode(int hashCode)(Code) | | Answer the transformed hash code, intended to be an improvement
on the objects own hashcode. The magic number 127 is performance
voodoo to (try to) eliminate problems experienced by Wolfgang.
|
| initialIndexFor | | final protected int initialIndexFor(Object key)(Code) | | Answer the initial index for the object key in the table.
With luck, this will be the final position for that object. The initial index
will always be non-negative and less than capacity.
Implementation note: do not use Math.abs to turn a
hashcode into a positive value; there is a single specific integer on which
it does not work. (Hence, here, the use of bitmasks.)
|
| moveAssociatedValues | | protected void moveAssociatedValues(int here, int scan)(Code) | | When removeFrom [or remove] moves a key, it calls this method to move
any associated values, passing in the index of the slot here
to move to and the index of the slot scan to move from.
Subclasses override if they have any associated values.
|
| nextSize | | protected static int nextSize(int atLeast)(Code) | | |
| remove | | public void remove(Object key)(Code) | | Remove the object key from this hash's keys if it
is present (if it's absent, do nothing). If a key is removed, the
removeAssociatedValues will be removed. If a key
is moved, the moveAssociatedValues method will
be called.
|
| removeAssociatedValues | | protected void removeAssociatedValues(int here)(Code) | | When removeFrom [or remove] removes a key, it calls this method to
remove any associated values, passing in the index of the key's slot.
Subclasses override if they have any associated values.
|
| removeFrom | | protected Object removeFrom(int here)(Code) | | Remove the triple at element i of contents.
This is an implementation of Knuth's Algorithm R from tAoCP vol3, p 527,
with exchanging of the roles of i and j so that they can be usefully renamed
to here and scan.
It relies on linear probing but doesn't require a distinguished REMOVED
value. Since we resize the table when it gets fullish, we don't worry [much]
about the overhead of the linear probing.
Iterators running over the keys may miss elements that are moved from the
top of the table to the bottom because of Iterator::remove. removeFrom
returns such a moved key as its result, and null otherwise.
|
| showkeys | | void showkeys()(Code) | | |
|
|