理解HashMap结构，从分析源码开始
package java.util;public interface Map<K,V> { //此方法返回的是Map中Key-Value值的个数 int size(); //此方法用于判断Map中是否存在Key-Value值，如果存在，返回false,//否则返回//true boolean isEmpty(); //此方法用于判断Map中是否包含Key = key的对象，存在返回true,不存在返回//false boolean containsKey(Object key); //此方法用于判断Map中是否存在Value = value的对象，存在返回true,不存在返//回false boolean containsValue(Object value); //向Map添加对象的方法,传入Key和Value的方法 V put(K key, V value); //移除Map中Key = key的对象 V remove (Object key); //将Map对象m中的所有值复制到新的Map中 void put All(Map<? extends K, ? extends V> m); //移除Map中的所有对象 void clear (); //获取Map所有的Key值,并将所有的Key值放入Set中的方法,返回的是存放Key值的//Set集合 Set<K> keySet (); //返回Map中所有Value值，并将其存入Collection集合中 Collection<V> values(); //返回所有Map值，并将其存入Set集合中 Set<Map.Entry<K, V>> entrySet (); //Map接口中定义的Entry内部接口,Entry是Map主存放的对象 interface Entry<K,V> { //返回Entry对象的Key值 K getKey();
//返回Entry对象的Value值 V getValue();
//替换Entry对象的Value值 V setValue(V value); //比较Entry对象是否相等的方法 boolean equals(Object o); //获取Entry对象哈希吗的方法 int hashCode(); } //比较Map对象是否相等的方法 boolean equals(Object o); //获取Map对象哈希吗的方法 int hashCode();
}?
package java.util;import java.io.*;public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable{ //HashMap的默认容量 static final int DEFAULT_INITIAL_CAPACITY = 16; //HashMap的最大容量 static final int MAXIMUM_CAPACITY = 1 << 30; //HashMap的默认装载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; //存放Entry的数组 transient Entry[] table; //Map中Key-Value值个数 transient int size; //数组扩容时Key-Value要达到的容量大小:capacity * load factor int threshold; //装载因子 final float loadFactor; //HashMap重构的次数 transient int modCount; //构造器1，传入两个参数，依次为容量和装载因子 public HashMap(int initialCapacity, float loadFactor) { //如果容量小于0,就抛出非法初始化异常 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); //如果容量大于最大容量,就将最大容量赋给当前容量，也就是不能超出最大容量 if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY; //如果装载因子不大于0，就抛出装载因子异常 if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); //容量初始化为1 int capacity = 1; //当容量小于传入的参数容量时，容量数不停左移，直至容量大于传入的参数容量，这样做容量便以2的幂递增，便于控制 while (capacity < initialCapacity) capacity <<= 1; //装载因子传入 this.loadFactor = loadFactor; //数组扩容时Key-Value要达到的容量大小 threshold = (int)(capacity * loadFactor); //创建指定容量大小的对象数组 table = new Entry[capacity]; init(); } //构造器2,只需传入容量大小，装载因此默认为0.75 public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } //构造器3，容量和装载因子均采取默认值 public HashMap(){ this.loadFactor = DEFAULT_LOAD_FACTOR; //数组扩容时Key-Value要达到的容量大小 threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); //创建默认容量大小的对象数组 table = new Entry[DEFAULT_INITIAL_CAPACITY]; init(); } //构造器4，传入Map对象 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); } //初始化的方法，里面没有做任何操作 void init() { } //hash函数，HashMap中的核心,此方法采用移位和异或操作来实现，由于计算机最终处理数据的方式是逻辑运算，这里直接采用逻辑运算进行hash运算，速度较快 static int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } //Key经过hash后,再调用此方法，根据数组长度，产生Key-Value值对在数组中的位 //置 static int indexFor(int hash, int length) { return h & (length-1); } //返回Map中Key-Value对的数目 public int size() { return size; } //判断Map里面是否有Key-Value对,如果没有返回true public boolean isEmpty() { return size == 0; } //根据Key值，返回对应的Value值 public V get(Object key) { if (key == null) return getForNullKey(); //对Key的哈希吗进行hash运算 int hash = hash(key.hashCode()); 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.equals(k))) return e.value; } return null; } //返回Key = null的Value的值 private V getForNullKey() { for (Entry<K,V> e = table[0]; e != null; e = e.next){ if (e.key == null) return e.value; } return null; } //判断是否存在Key值 public boolean containsKey(Object key) { return getEntry(key) != null; } //获取Key对应的Key-Value值对,即Entry对象 final Entry<K,V> getEntry(Object key) { int hash = (key == null) ? 0 : hash(key.hashCode()); 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; } //向Map中添加Key-Value值对 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; } //向Map中放入元素，其中Key为Null 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; } //创建已有Key – Value值对的方法,相当于将原Map中Key-Value值的Key-Value值一对一对复制到新的Map中的方法 private void putForCreate(K key, V value) { int hash = (key == null) ? 0 : 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 != null && key.equals(k)))) { e.value = value; return; } } createEntry(hash, key, value, i); } //将原Map中所有Key-Value对象全部放入新Map中的方法 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 resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; transfer(newTable); table = newTable; threshold = (int)(newCapacity * loadFactor); } //将table中的元素放入新table void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) { Entry<K,V> e = src[j]; if (e != null) { src[j] = null; do { Entry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } } //添加所有的Map对象 public void putAll(Map<? extends K, ? extends V> m) { int numKeysToBeAdded = m.size(); if (numKeysToBeAdded == 0) return; if (numKeysToBeAdded > threshold) { int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1); if (targetCapacity > MAXIMUM_CAPACITY) targetCapacity = MAXIMUM_CAPACITY; int newCapacity = table.length; while (newCapacity < targetCapacity) newCapacity <<= 1; if (newCapacity > table.length) resize(newCapacity); } for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) put(e.getKey(), e.getValue()); } //移除Map中Key对应的值 public V remove(Object key) { Entry<K,V> e = removeEntryForKey(key); return (e == null ? null : e.value); } final Entry<K,V> removeEntryForKey(Object key) { int hash = (key == null) ? 0 : hash(key.hashCode()); 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; else prev.next = next; e.recordRemoval(this); return e; } prev = e; e = next; } return e; } //移除整个Map对象 final Entry<K,V> removeMapping(Object o) { if (!(o instanceof Map.Entry)) return null; Map.Entry<K,V> entry = (Map.Entry<K,V>) o; Object key = entry.getKey(); int hash = (key == null) ? 0 : hash(key.hashCode()); 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; if (e.hash == hash && e.equals(entry)) { modCount++; size--; if (prev == e) table[i] = next; else prev.next = next; e.recordRemoval(this); return e; } prev = e; e = next; } return e; } //清空所有内容 public void clear() { modCount++; Entry[] tab = table; for (int i = 0; i < tab.length; i++) tab[i] = null; size = 0; } //判断Map是否包含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; } 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; } //复写的Object类的clone()方法 public Object clone() { HashMap<K,V> result = null; try { result = (HashMap<K,V>)super.clone(); } catch (CloneNotSupportedException e) { // assert false; } result.table = new Entry[table.length]; result.entrySet = null; result.modCount = 0; result.size = 0; result.init(); result.putAllForCreate(this); return result; } //内部静态类Entry static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value;//下一节点 Entry<K,V> next; final int hash;//构造器，传入四个参数 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; } //复写的Object类的equals方法 public final boolean equals(Object o) { 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; } //复写的Object类的hashCode()方法 public final int hashCode() { return (key==null ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode()); } public final String toString() { return getKey() + "=" + getValue(); } void recordAccess(HashMap<K,V> m) { } void recordRemoval(HashMap<K,V> m) { } } //添加Entry实体，即Key-Value值的方法 void addEntry(int hash, K key, V value, int bucketIndex){ Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<>(hash, key, value, e); if (size++ >= threshold) resize(2 * table.length); } //创建Entry实体的方法 void createEntry(int hash, K key, V value, int bucketIndex{ Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<>(hash, key, value, e); size++; } private abstract class HashIterator<E> implements Iterator<E> { Entry<K,V> next; int expectedModCount; int index; Entry<K,V> current; HashIterator() { expectedModCount = modCount; if (size > 0) { Entry[] t = table; while (index < t.length && (next = t[index++]) == null); } } //判断下一个是否为空 public final boolean hasNext() { return next != null; } //返回下一个Entry对象 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) { Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } 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); expectedModCount = modCount; } } 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(); } } Iterator<K> newKeyIterator() { return new KeyIterator(); } Iterator<V> newValueIterator() { return new ValueIterator(); } Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); } private transient Set<Map.Entry<K,V>> entrySet = null; public Set<K> keySet() { Set<K> ks = keySet; return (ks != null ? ks : (keySet = new KeySet())); } private final class KeySet extends AbstractSet<K> { public Iterator<K> iterator() { return newKeyIterator(); } public int size() { return size; } public boolean contains(Object o) { return containsKey(o); } public boolean remove(Object o) { return HashMap.this.removeEntryForKey(o) != null; } //清空HashMap public void clear() { HashMap.this.clear(); } } public Collection<V> values() { Collection<V> vs = values; return (vs != null ? vs : (values = new Values())); } private final class Values extends AbstractCollection<V>{ public Iterator<V> iterator() { return newValueIterator(); } public int size() { return size; } public boolean contains(Object o) { return containsValue(o); } public void clear() { HashMap.this.clear(); } } //返回存在Entry实体的Set集合 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(); } } private void writeObject(java.io.ObjectOutputStream s) throws IOException { Iterator<Map.Entry<K,V>> i = (size > 0) ? entrySet0().iterator() : null; s.defaultWriteObject(); s.writeInt(table.length); s.writeInt(size); if (i != null) { while (i.hasNext()) { Map.Entry<K,V> e = i.next(); s.writeObject(e.getKey()); s.writeObject(e.getValue()); } } } private static final long serialVersionUID = 362498820763181265L; private void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException { s.defaultReadObject(); int numBuckets = s.readInt(); table = new Entry[numBuckets]; init(); int size = s.readInt(); for (int i=0; i<size; i++) { K key = (K) s.readObject(); V value = (V) s.readObject(); putForCreate(key, value); } } int capacity() { return table.length; } float loadFactor() { return loadFactor; }}?
?
?
?
?