Public Types | |
typedef void[] | K |
typedef Object | V |
typedef jhash | hash |
Private Member Functions | |
final Segment | segmentFor (uint hash) |
this (uint initialCapacity, float loadFactor, uint concurrencyLevel) | |
this (uint initialCapacity) | |
this () | |
V | get (K key) |
bool | containsKey (K key) |
V | put (K key, V value) |
V | putIfAbsent (K key, V value) |
V | remove (K key) |
bool | remove (K key, V value) |
V | replace (K key, V value) |
void | clear () |
KeyIterator | keys () |
ValueIterator | elements () |
int | opApply (int(*dg)(inout char[])) |
int | opApply (int(*dg)(inout char[], inout Object)) |
Static Private Member Functions | |
uint | walter (K x) |
uint | fnv (K x) |
uint | jhash (K x) |
Private Attributes | |
const uint | DEFAULT_INITIAL_CAPACITY = 16 |
const uint | MAXIMUM_CAPACITY = 1 << 30 |
const float | DEFAULT_LOAD_FACTOR = 0.75f |
const uint | DEFAULT_SEGMENTS = 16 |
const uint | MAX_SEGMENTS = 1 << 16 |
final int | segmentMask |
final int | segmentShift |
final Segment[] | segments |
Hashtable
. However, even though all operations are thread-safe, retrieval operations do not entail locking, and there is not any support for locking the entire table in a way that prevents all access. This class is fully interoperable with Hashtable
in programs that rely on its thread safety but not on its synchronization details.
Retrieval operations (including get
) generally do not block, so may overlap with update operations (including put
and remove
). Retrievals reflect the results of the most recently completed update operations holding upon their onset. For aggregate operations such as putAll
and clear
, concurrent retrievals may reflect insertion or removal of only some entries. Similarly, Iterators and Enumerations return elements reflecting the state of the hash table at some point at or since the creation of the iterator/enumeration. They do not throw ConcurrentModificationException. However, iterators are designed to be used by only one thread at a time.
The allowed concurrency among update operations is guided by the optional concurrencyLevel
constructor argument (default 16), which is used as a hint for internal sizing. The table is internally partitioned to try to permit the indicated number of concurrent updates without contention. Because placement in hash tables is essentially random, the actual concurrency will vary. Ideally, you should choose a value to accommodate as many threads as will ever concurrently modify the table. Using a significantly higher value than you need can waste space and time, and a significantly lower value can lead to thread contention. But overestimates and underestimates within an order of magnitude do not usually have much noticeable impact. A value of one is appropriate when it is known that only one thread will modify and all others will only read. Also, resizing this or any other kind of hash table is a relatively slow operation, so, when possible, it is a good idea to provide estimates of expected table sizes in constructors.
This class and its views and iterators implement all of the optional methods of the Map and Iterator interfaces.
Like java.util.Hashtable but unlike java.util.HashMap, this class does NOT allow null
to be used as a key or value.
This class is a member of the Java Collections Framework.
<K> | the type of keys maintained by this map |
<V> | the type of mapped values |
Definition at line 109 of file HashMap.d.
|
Definition at line 111 of file HashMap.d. Referenced by containsKey(), HashMap::Segment::containsKey(), fnv(), get(), HashMap::Segment::get(), jhash(), HashMap::Segment::matchKey(), HashMap::KeyIterator::next(), put(), HashMap::Segment::put(), putIfAbsent(), remove(), HashMap::Segment::remove(), replace(), HashMap::Segment::replace(), HashMap::HashEntry::this(), and walter(). |
|
Definition at line 112 of file HashMap.d. Referenced by get(), HashMap::Segment::get(), HashMap::ValueIterator::next(), put(), HashMap::Segment::put(), putIfAbsent(), remove(), HashMap::Segment::remove(), replace(), HashMap::Segment::replace(), and HashMap::HashEntry::this(). |
|
Definition at line 113 of file HashMap.d. Referenced by containsKey(), HashMap::Segment::containsKey(), fnv(), get(), HashMap::Segment::get(), HashMap::Segment::getFirst(), put(), HashMap::Segment::put(), putIfAbsent(), remove(), HashMap::Segment::remove(), replace(), HashMap::Segment::replace(), segmentFor(), and HashMap::HashEntry::this(). |
|
Returns a hash code for non-null Object x. Uses the same hash code spreader as most other java.util hash tables.
Definition at line 181 of file HashMap.d. References K. |
|
Returns a hash code for non-null Object x. uses the FNV hash function
|
|
hash() -- hash a variable-length key into a 32-bit value k : the key (the unaligned variable-length array of bytes) len : the length of the key, counting by bytes level : can be any 4-byte value Returns a 32-bit value. Every bit of the key affects every bit of the return value. Every 1-bit and 2-bit delta achieves avalanche. About 36+6len instructions. The best hash table sizes are powers of 2. There is no need to do mod a prime (mod is sooo slow!). If you need less than 32 bits, use a bitmask. For example, if you need only 10 bits, do h = (h & hashmask(10)); In which case, the hash table should have hashsize(10) elements. If you are hashing n strings (ub1 **)k, do it like this: for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h); By Bob Jenkins, 1996. bob_jenkins@burtleburtle.net. You may use this code any way you wish, private, educational, or commercial. It's free. See http://burlteburtle.net/bob/hash/evahash.html Use for hash table lookup, or anything where one collision in 2^32 is acceptable. Do NOT use for cryptographic purposes. Definition at line 237 of file HashMap.d. References K. Referenced by Cluster::getGroup(). |
|
Returns the segment that should be used for key with given hash
Definition at line 308 of file HashMap.d. References hash, segmentMask, segments, and segmentShift. Referenced by containsKey(), get(), put(), putIfAbsent(), remove(), and replace(). |
|
Creates a new, empty map with the specified initial capacity and the specified load factor.
Definition at line 701 of file HashMap.d. References MAX_SEGMENTS, MAXIMUM_CAPACITY, segmentMask, and segmentShift. |
|
Creates a new, empty map with the specified initial capacity, and with default load factor and concurrencyLevel.
Definition at line 745 of file HashMap.d. References DEFAULT_LOAD_FACTOR, and DEFAULT_SEGMENTS. |
|
Creates a new, empty map with a default initial capacity, load factor, and concurrencyLevel. Definition at line 754 of file HashMap.d. References DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, and DEFAULT_SEGMENTS. |
|
Returns the value to which the specified key is mapped in this table.
Definition at line 769 of file HashMap.d. References HashMap::Segment::get(), hash, K, segmentFor(), and V. Referenced by NodeSet::addNode(), PlainCache::extract(), PlainCache::get(), Cluster::getGroup(), ChannelCache::lockWhereInvalid(), ClusterQueue::lookup(), ClusterCache::lookup(), and ServletProvider::lookupProxy(). |
|
Tests if the specified object is a key in this table.
Definition at line 785 of file HashMap.d. References HashMap::Segment::containsKey(), hash, K, and segmentFor(). |
|
Maps the specified
The value can be retrieved by calling the
Definition at line 806 of file HashMap.d. References hash, K, HashMap::Segment::put(), segmentFor(), and V. Referenced by ClusterCache::addCache(), NodeSet::addNode(), Cluster::getGroup(), ChannelCache::lockWhereInvalid(), PlainCache::put(), ClusterQueue::put(), and testHashMap(). |
|
If the specified key is not already associated with a value, associate it with the given value. This is equivalent to
Definition at line 832 of file HashMap.d. References hash, K, HashMap::Segment::put(), segmentFor(), and V. |
|
Removes the key (and its corresponding value) from this table. This method does nothing if the key is not in the table.
Definition at line 851 of file HashMap.d. References hash, K, HashMap::Segment::remove(), segmentFor(), and V. Referenced by PlainCache::extract(), testHashMap(), and ChannelCache::unlock(). |
|
Remove entry for key only if currently mapped to given value. Acts as
Definition at line 873 of file HashMap.d. References hash, K, HashMap::Segment::remove(), segmentFor(), and V. |
|
Replace entry for key only if currently mapped to some value. Acts as
Definition at line 896 of file HashMap.d. References hash, K, HashMap::Segment::replace(), segmentFor(), and V. |
|
Removes all mappings from this map. Definition at line 908 of file HashMap.d. References HashMap::Segment::clear(), and segments. |
|
Returns an enumeration of the keys in this table.
Definition at line 921 of file HashMap.d. Referenced by opApply(). |
|
Returns an enumeration of the values in this table.
|
|
Iterate over all keys in hashmap Definition at line 943 of file HashMap.d. References HashMap::HashIterator::hasNext(), keys(), and HashMap::KeyIterator::next(). |
|
Iterate over all keys in hashmap Definition at line 963 of file HashMap.d. References HashMap::HashIterator::hasNext(), HashMap::HashEntry::key, keys(), HashMap::HashIterator::nextElement(), and HashMap::HashEntry::value. |
|
The default initial number of table slots for this table. Used when not otherwise specified in constructor. Definition at line 126 of file HashMap.d. Referenced by this(). |
|
The maximum capacity, used if a higher value is implicitly specified by either of the constructors with arguments. MUST be a power of two <= 1<<30 to ensure that entries are indexible using ints. Definition at line 134 of file HashMap.d. Referenced by this(). |
|
The default load factor for this table. Used when not otherwise specified in constructor. Definition at line 140 of file HashMap.d. Referenced by this(). |
|
The default number of concurrency control segments. Definition at line 145 of file HashMap.d. Referenced by this(). |
|
The maximum number of segments to allow; used to bound constructor arguments. Definition at line 151 of file HashMap.d. Referenced by this(). |
|
Mask value for indexing into segments. The upper bits of a key's hash code are used to choose the segment. Definition at line 160 of file HashMap.d. Referenced by segmentFor(), and this(). |
|
Shift value for indexing within segments. Definition at line 165 of file HashMap.d. Referenced by segmentFor(), and this(). |
|
The segments, each of which is a specialized hash table Definition at line 170 of file HashMap.d. Referenced by HashMap::HashIterator::advance(), clear(), segmentFor(), and HashMap::HashIterator::this(). |