| Methods Summary |
|---|
| public boolean | contains(int key)
// index into the corresponding hash bucket:
final Entry [] buckets = m_buckets;
final int bucketIndex = (key & 0x7FFFFFFF) % buckets.length;
// traverse the singly-linked list of entries in the bucket:
for (Entry entry = buckets [bucketIndex]; entry != null; entry = entry.m_next)
{
if (key == entry.m_key) return true;
}
return false;
|
| void | debugDump(java.lang.StringBuffer out)
if (out != null)
{
out.append (super.toString ()); out.append (EOL);
out.append ("size = " + m_size + ", bucket table size = " + m_buckets.length + ", load factor = " + m_loadFactor + EOL);
out.append ("size threshold = " + m_sizeThreshold + EOL);
}
|
| public boolean | get(int key, int[] out)Returns the value that is mapped to a given 'key'. Returns
false if this key has never been mapped.
// index into the corresponding hash bucket:
final Entry [] buckets = m_buckets;
final int bucketIndex = (key & 0x7FFFFFFF) % buckets.length;
// traverse the singly-linked list of entries in the bucket:
for (Entry entry = buckets [bucketIndex]; entry != null; entry = entry.m_next)
{
if (key == entry.m_key)
{
out [0] = entry.m_value;
return true;
}
}
return false;
|
| public boolean | get(int key, int[] out, int index)
// index into the corresponding hash bucket:
final Entry [] buckets = m_buckets;
final int bucketIndex = (key & 0x7FFFFFFF) % buckets.length;
// traverse the singly-linked list of entries in the bucket:
for (Entry entry = buckets [bucketIndex]; entry != null; entry = entry.m_next)
{
if (key == entry.m_key)
{
out [index] = entry.m_value;
return true;
}
}
return false;
|
| public int[] | keys()
final int [] result = new int [m_size];
int scan = 0;
for (int b = 0; b < m_buckets.length; ++ b)
{
for (Entry entry = m_buckets [b]; entry != null; entry = entry.m_next)
{
result [scan ++] = entry.m_key;
}
}
return result;
|
| public void | put(int key, int value)Updates the table to map 'key' to 'value'. Any existing mapping is overwritten.
Entry currentKeyEntry = null;
// detect if 'key' is already in the table [in which case, set 'currentKeyEntry' to point to its entry]:
// index into the corresponding hash bucket:
int bucketIndex = (key & 0x7FFFFFFF) % m_buckets.length;
// traverse the singly-linked list of entries in the bucket:
Entry [] buckets = m_buckets;
for (Entry entry = buckets [bucketIndex]; entry != null; entry = entry.m_next)
{
if (key == entry.m_key)
{
currentKeyEntry = entry;
break;
}
}
if (currentKeyEntry != null)
{
// replace the current value:
currentKeyEntry.m_value = value;
}
else
{
// add a new entry:
if (m_size >= m_sizeThreshold) rehash ();
buckets = m_buckets;
bucketIndex = (key & 0x7FFFFFFF) % buckets.length;
final Entry bucketListHead = buckets [bucketIndex];
final Entry newEntry = new Entry (key, value, bucketListHead);
buckets [bucketIndex] = newEntry;
++ m_size;
}
|
| private void | rehash()Re-hashes the table into a new array of buckets.
// TODO: it is possible to run this method twice, first time using the 2*k+1 prime sequencer for newBucketCount
// and then with that value reduced to actually shrink capacity. As it is right now, the bucket table can
// only grow in size
final Entry [] buckets = m_buckets;
final int newBucketCount = (m_buckets.length << 1) + 1;
final Entry [] newBuckets = new Entry [newBucketCount];
// rehash all entry chains in every bucket:
for (int b = 0; b < buckets.length; ++ b)
{
for (Entry entry = buckets [b]; entry != null; )
{
final Entry next = entry.m_next; // remember next pointer because we are going to reuse this entry
final int entryKeyHash = entry.m_key & 0x7FFFFFFF;
// index into the corresponding new hash bucket:
final int newBucketIndex = entryKeyHash % newBucketCount;
final Entry bucketListHead = newBuckets [newBucketIndex];
entry.m_next = bucketListHead;
newBuckets [newBucketIndex] = entry;
entry = next;
}
}
m_sizeThreshold = (int) (newBucketCount * m_loadFactor);
m_buckets = newBuckets;
|
| public void | remove(int key)Updates the table to map 'key' to 'value'. Any existing mapping is overwritten.
// index into the corresponding hash bucket:
final int bucketIndex = (key & 0x7FFFFFFF) % m_buckets.length;
// traverse the singly-linked list of entries in the bucket:
Entry [] buckets = m_buckets;
for (Entry entry = buckets [bucketIndex], prev = entry; entry != null; )
{
final Entry next = entry.m_next;
if (key == entry.m_key)
{
if (prev == entry)
buckets [bucketIndex] = next;
else
prev.m_next = next;
-- m_size;
break;
}
prev = entry;
entry = next;
}
|
| public int | size()Returns the number of key-value mappings in this map.
return m_size;
|
| public java.lang.String | toString()Overrides Object.toString() for debug purposes.
final StringBuffer s = new StringBuffer ();
debugDump (s);
return s.toString ();
|
