HashMap用于存储键值对，键可以是null，值也可以是null。
HashMap不保证同步，其余与Hashtable一样。
因此当不同的线程对HashMap做了结构化的修改时，需要加同步：
A structural modification is any operation that adds or deletes one or more mappings; merely changing the value
associated with a key that an instance already contains is not a structural modification.
创建一个同步HashMap的方法：
Map m = Collections.synchronizedMap(new HashMap(…));
不能在迭代器中，通过map.delete删除元素：
<p>The iterators returned by all of this class’s "collection view methods"
* are <i>fail-fast</i>: if the map is structurally modified at any time after
* the iterator is created, in any way except through the iterator’s own
* <tt>remove</tt> method, the iterator will throw a
* {@link ConcurrentModificationException}. Thus, in the face of concurrent
* modification, the iterator fails quickly and cleanly, rather than risking
* arbitrary, non-deterministic behavior at an undetermined time in the
* future.
</p>
可以设置default capacity（16），每次自动increase是扩容两倍，扩容之后需要rehash，。
default load factor (.75f)
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry<K,V>[] table; 这是hash表，存储键值对的地方
MAXIMUM_CAPACITY = 1 << 30，最大容量，必须设为2的幂次
transient Entry<K,V>[] table;
transient int size，也就是在序列化的时候，不需要加入该变量。
/**
* The next size value at which to resize (capacity * load factor).
* @serial
*/
intthreshold;阈值，resize（capacity*load factor）的下一个值
transientintmodCount;记录该map被structurally modified（结构化,主要是delete，and以及修改rehash）修改的次数。
定义私有静态类Holder
/**
* holds values which can’t be initialized until after VM is booted.
*/
privatestaticclass Holder
/* Alternative hashing reduces the incidence of collisions due to weak hash code calculation for String keys. */
ALTERNATIVE_HASHING_THRESHOLD_DEFAULT对字符串进行alternative hash，减少由于weak hash code计算导致的冲突
transientbooleanuseAltHashing;是否对字符串进行alternative hash
/**
* A randomizing value associated with this instance that is applied to
* hash code of keys to make hash collisions harder to find.
*/
transientfinalinthashSeed增加hash code冲突的难度
HashMap(int initialize, int loadFactor){
//Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
table=newEntry[capacity];
threshold= (int)Math.min(capacity * loadFactor,MAXIMUM_CAPACITY+ 1);//
init();
}
拷贝构造器
public HashMap(Map<? extends K, ?extends V> m) {
this(Math.max((int) (m.size() /DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY),DEFAULT_LOAD_FACTOR);
putAllForCreate(m);
}
hash函数
/**
* Retrieve object hash code and applies a supplemental hash function to the
* result hash, which defends against poor quality hash functions. This is
* critical because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
* in lower bits. Note: Null keys always map to hash 0, thus index 0.
*/
final int hash(Object k) {
int h = 0;
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);使用stringHash32对字符串进行hash
}
h = hashSeed; 第一个种子
}
h ^= k.hashCode(); 异或上对象的hashCode
// This function ensures that hashCodes that differ only by
// constant multiples at each bit positionhave a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
—
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ?null : entry.getValue();
}
静态内部类Entry
static class Entry<K,V> implements Map.Entry<K,V> { final K key;//常量，key一旦设定就不可以改了
V value; Entry<K,V> next; //指针？指向table中的下一个元素？ int hash; //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; } public final boolean equals(Object o) {//相等，定义的是两个对象的key和value分别相等。或者都为null if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry)o; Object k1 = getKey(); Object k2 = e.getKey(); if (k1 == k2 || (k1 != null && k1.equals(k2))) { Object v1 = getValue(); Object v2 = e.getValue(); if (v1 == v2 || (v1 != null && v1.equals(v2))) return true; } return false; } public final int hashCode() {//hashCode=key的hashCode 异或 value的hashCode return (key==null ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode()); } public final String toString() { return getKey() + "=" + getValue(); } /** * This method is invoked whenever the value in an entry is * overwritten by an invocation of put(k,v) for a key k that's already * in the HashMap. */ void recordAccess(HashMap<K,V> m) { } /** * This method is invoked whenever the entry is * removed from the table. */ void recordRemoval(HashMap<K,V> m) { } }
//所有的空key都map到index=0，啥意思？
private V getForNullKey() {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key ==null)
return e.value;
}
return null;
}
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
final Entry<K,V> getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key !=null && key.equals(k))))
return e;
}
return null;
}
NOT FINISHED….
To Be Continued…
Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key); int i = indexFor(hash, table.length); 获取hashCode的在table中的下标 for (Entry<K,V> e = table[i]; e != null; e = e.next) {使用的外链的方式，解决冲突，对于hashCode相同的对象，再遍历链表，查找该元素 Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; 如果存在这个key，那么修改key所对应的值 e.recordAccess(this); return oldValue; 返回原来的旧的值 } } modCount++; addEntry(hash, key, value, i); return null; }
对于可以为null的，在table[0]维护了一个链表。key为null的，也可以对应不同的value。
/** * Offloaded version of put for null keys */ private V putForNullKey(V value) { for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(0, null, value, 0); return null; }
动态扩容：
Rehashes the contents of this map into a new array with a
* larger capacity. This method is called automatically when the
* number of keys in this map reaches its threshold.
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity];创建一个新的table boolean oldAltHashing = useAltHashing; useAltHashing |= sun.misc.VM.isBooted() && (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); boolean rehash = oldAltHashing ^ useAltHashing; 判断是否需要rehash transfer(newTable, rehash); transfer函数直接修改newTable的值 table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }
将当前table的值，传给newTable
/** * Transfers all entries from current table to newTable. */ void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) { while(null != e) { Entry<K,V> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); //如果需要重新hash，那么再次计算hashCode } int i = indexFor(e.hash, newCapacity); e.next = newTable[i];//下一个， newTable[i] = e;// e = next;// } } }
根据key删除键值对
public V remove(Object key) { Entry<K,V> e = removeEntryForKey(key); return (e == null ? null : e.value); }
删除key指向的value，并且 返回该value
/** * Removes and returns the entry associated with the specified key * in the HashMap. Returns null if the HashMap contains no mapping * for this key. */ final Entry<K,V> removeEntryForKey(Object key) { int hash = (key == null) ? 0 : hash(key); int i = indexFor(hash, table.length); Entry<K,V> prev = table[i];//两个记录指针，一个记录前一个，一个记录当前值 Entry<K,V> e = prev;// while (e != null) { Entry<K,V> next = e.next; Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { modCount++; size--; if (prev == e) table[i] = next;//如果待删除的是链表的头，首先将table[i]设为链表的第二个值 else prev.next = next; e.recordRemoval(this); return e; } prev = e; e = next; } return e; }
清空存储的键值对
/** * Removes all of the mappings from this map. * The map will be empty after this call returns. */ public void clear() { modCount++; Entry[] tab = table;//为啥要新开一个tab数组，将每个元素设为null？
//为啥不直接在table上操作？
for (int i = 0; i < tab.length; i++) tab[i] = null; size = 0; }
判断是否存在一个或多个key，对应某个value
public boolean containsValue(Object value) { if (value == null) return containsNullValue(); Entry[] tab = table; for (int i = 0; i < tab.length ; i++) for (Entry e = tab[i] ; e != null ; e = e.next) if (value.equals(e.value)) return true; return false; } /** * Special-case code for containsValue with null argument */ private boolean containsNullValue() { Entry[] tab = table; for (int i = 0; i < tab.length ; i++) for (Entry e = tab[i] ; e != null ; e = e.next) if (e.value == null) return true; return false; }
拷贝
public Object clone() { HashMap<K,V> result = null; try { result = (HashMap<K,V>)super.clone();//首先调用父类的clone } catch (CloneNotSupportedException e) { // assert false; } result.table = new Entry[table.length];//创建一个新的table result.entrySet = null; result.modCount = 0; result.size = 0; result.init(); result.putAllForCreate(this);// return result; }
/** * This method is used instead of put by constructors and * pseudoconstructors (clone, readObject). It does not resize the table, * check for comodification, etc. It calls createEntry rather than * addEntry. */ private void putForCreate(K key, V value) { int hash = null == key ? 0 : hash(key); int i = indexFor(hash, table.length); /** * Look for preexisting entry for key. This will never happen for * clone or deserialize. It will only happen for construction if the * input Map is a sorted map whose ordering is inconsistent w/ equals. */ for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { e.value = value;//将hash相同的e的value赋值为value return; } } createEntry(hash, key, value, i);//如果不存在相同的key的话， } private void putAllForCreate(Map<? extends K, ? extends V> m) { for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) putForCreate(e.getKey(), e.getValue()); }void createEntry(int hash, K key, V value,int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);//对table[index]重新赋值，将hash，key赋值为为头，e作为next （相当于是插入）
size++; }
定义抽象类HashIterator
private abstract class HashIterator<E> implements Iterator<E> { Entry<K,V> next; // next entry to return int expectedModCount; // For fast-fail int index; // current slot Entry<K,V> current; // current entry HashIterator() { expectedModCount = modCount; if (size > 0) { // advance to first entry Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } } public final boolean hasNext() { return next != null; } final Entry<K,V> nextEntry() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); Entry<K,V> e = next; if (e == null) throw new NoSuchElementException(); if ((next = e.next) == null) {//如果e.next == nullEntry[] t = table; while (index < t.length && (next = t[index++]) == null) ;//那么循环找到下一个链表为空的t[index]，这个就是当前节点的nextEntry } current = e; return e; } public void remove() { if (current == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); Object k = current.key; current = null; HashMap.this.removeEntryForKey(k);//HashMap存在一个问题，如果在遍历的过程中删除节点会报错ConCurrentModified??//但是通过Iterator删除就没有关系 expectedModCount = modCount; } }三个Iterator
private final class ValueIterator extends HashIterator<V> { public V next() { return nextEntry().value; } } private final class KeyIterator extends HashIterator<K> { public K next() { return nextEntry().getKey(); } } private final class EntryIterator extends HashIterator<Map.Entry<K,V>> { public Map.Entry<K,V> next() { return nextEntry(); } } // Subclass overrides these to alter behavior of views' iterator() method Iterator<K> newKeyIterator() { return new KeyIterator(); } Iterator<V> newValueIterator() { return new ValueIterator(); } Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }HashMap也可以看成是一个Set
Returns a Set view of the mappings contained in this map.The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. If the map is modifiedwhile an iteration over the set is in progress (except throughthe iterator's own <tt>remove</tt> operation, or through the setValue</tt> operation on a map entry returned by the iterator) the results of the iteration are undefined.
public Set<Map.Entry<K,V>> entrySet() { return entrySet0(); } private Set<Map.Entry<K,V>> entrySet0() { Set<Map.Entry<K,V>> es = entrySet; return es != null ? es : (entrySet = new EntrySet()); } private final class EntrySet extends AbstractSet<Map.Entry<K,V>> { public Iterator<Map.Entry<K,V>> iterator() { return newEntryIterator(); } public boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry<K,V> e = (Map.Entry<K,V>) o; Entry<K,V> candidate = getEntry(e.getKey()); return candidate != null && candidate.equals(e); } public boolean remove(Object o) { return removeMapping(o) != null; } public int size() { return size; } public void clear() { HashMap.this.clear(); } }HashMap可以序列化，因此定义了readObject，writeObjectUses of readObject/writeObject in Serialization
private void writeObject(java.io.ObjectOutputStream s)
throws IOException
{
Iterator<Map.Entry<K,V>> i =
(size > 0) ? entrySet0().iterator() : null;
// Write out the threshold, loadfactor, and any hidden stuff
s.defaultWriteObject();
// Write out number of buckets
s.writeInt(table.length);
// Write out size (number of Mappings)
s.writeInt(size);
// Write out keys and values (alternating)
if (size > 0) {
for(Map.Entry<K,V> e : entrySet0()) {
s.writeObject(e.getKey());
s.writeObject(e.getValue());
}
}
}
private static final long serialVersionUID = 362498820763181265L; /** * Reconstitute the {@code HashMap} instance from a stream (i.e., * deserialize it). */ private void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException { // Read in the threshold (ignored), loadfactor, and any hidden stuff s.defaultReadObject(); if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new InvalidObjectException("Illegal load factor: " + loadFactor); // set hashSeed (can only happen after VM boot) Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET, sun.misc.Hashing.randomHashSeed(this)); // Read in number of buckets and allocate the bucket array; s.readInt(); // ignored // Read number of mappings int mappings = s.readInt(); if (mappings < 0) throw new InvalidObjectException("Illegal mappings count: " + mappings); int initialCapacity = (int) Math.min( // capacity chosen by number of mappings // and desired load (if >= 0.25) mappings * Math.min(1 / loadFactor, 4.0f), // we have limits... HashMap.MAXIMUM_CAPACITY); int capacity = 1; // find smallest power of two which holds all mappings while (capacity < initialCapacity) { capacity <<= 1; } table = new Entry[capacity]; threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); useAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); init(); // Give subclass a chance to do its thing. // Read the keys and values, and put the mappings in the HashMap for (int i=0; i<mappings; i++) { K key = (K) s.readObject(); V value = (V) s.readObject(); putForCreate(key, value); } }躲在某一地点，想念一个站在来路，
