HashMap
Implementation
Bucket is an array of entry in which
index is based on hashing of keys.
In every index Bucket maintain linkedlist
of entry.
/**
* The default initial
capacity - MUST be a power of two.
*/
static final int
DEFAULT_INITIAL_CAPACITY = 16;
/**
* 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.
*/
static final int
MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified
in constructor.
*/
static final float
DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The table, resized as
necessary. Length MUST Always be a power of two.
*/
transient Entry[] table;
/**
* The number of
key-value mappings contained in this map.
*/
transient int size;
/**
* Constructs an empty
<tt>HashMap</tt> with the default initial capacity
* (16) and the default
load factor (0.75).
*/
public HashMap() {
this.loadFactor =
DEFAULT_LOAD_FACTOR;
threshold =
(int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
public V put(K key, V value) {
if (key == null)
return
putForNullKey(value);
int hash =
hash(key.hashCode());
int i =
indexFor(hash, table.length);
for
(Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash ==
hash && ((k = e.key) == key || key.equals(k))) {
V oldValue =
e.value;
e.value =
value;
e.recordAccess(this);
return
oldValue;
}
}
modCount++;
addEntry(hash, key,
value, i);
return null;
}
/**
* Adds a new entry with
the specified key, value and hash code to
* the specified
bucket. It is the responsibility of this
* method to resize the
table if appropriate.
*
* Subclass overrides
this to alter the behavior of put method.
*/
void addEntry(int hash,
K key, V value, int bucketIndex) {
Entry<K,V> e =
table[bucketIndex];
table[bucketIndex] =
new Entry<K,V>(hash, key, value, e);// here its //maintaining linkedlist of entry
if (size++ >=
threshold)
resize(2 *
table.length);
}
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V>
next;
final int hash;
/**
* Creates new
entry.
*/
Entry(int h, K k, V
v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K
getKey() {
return key;
}
public final V
getValue() {
return value;
}
public final V
setValue(V newValue) {
V oldValue =
value;
value =
newValue;
return oldValue;
}