package java.util;import java.io.*;public class HashMap<K,V>extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable{DEFAULT_INITIAL_CAPACITY = 16;MAXIMUM_CAPACITY = 1 << 30;DEFAULT_LOAD_FACTOR = 0.75f; Entry[] table; size; threshold; loadFactor; modCount;HashMap(int initialCapacity, float loadFactor) {(initialCapacity < 0)throw new IllegalArgumentException(“Illegal initial capacity: ” +initialCapacity);(initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;(loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException(“Illegal load factor: ” +loadFactor);capacity = 1;while (capacity < initialCapacity)capacity <<= 1;.loadFactor = loadFactor;// 设置阈值为capacity * loadFactor，实际上当HashMap当前size到达这个阈值时，HashMap就需要扩大一倍了。threshold = (int)(capacity * loadFactor);// 创建一个capacity长度的数组用于保存数据table = new Entry[capacity];// 开始初始化init();}HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);} HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR;threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);table = new Entry[DEFAULT_INITIAL_CAPACITY];init();}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);}// 内部公用工具 init() {}hash(int h) {h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);}indexFor(int h, int length) {/****************** 由于length是2的n次幂，所以h & (length-1)相当于h % length。* 对于length，其2进制表示为1000…0，那么length-1为0111…1。* 那么对于任何小于length的数h，该式结果都是其本身h。* 对于h = length，该式结果等于0。* 对于大于length的数h，则和0111…1位与运算后，* 比0111…1高或者长度相同的位都变成0，香港虚拟主机，* 相当于减去j个length，该式结果是h-j*length，* 所以相当于h % length。* 其中一个很常用的特例就是h & 1相当于h % 2。* 这也是为什么length只能是2的n次幂的原因，为了优化。*/return h & (length-1);} size() {return size;} isEmpty() {return size == 0;} V get(Object key) {(key == null)return getForNullKey();hash = hash(key.hashCode());(Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) {Object k;(e.hash == hash && ((k = e.key) == key || key.equals(k)))return e.value;};} V getForNullKey() {(Entry<K,V> e = table[0]; e != null; e = e.next) {(e.key == null)return e.value;};} containsKey(Object key) {return getEntry(key) != null;}Entry<K,V> getEntry(Object key) {hash = (key == null) ? 0 : hash(key.hashCode());(Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) {Object k;(e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;};} V put(K key, V value) {(key == null)return putForNullKey(value);hash = hash(key.hashCode());i = indexFor(hash, table.length);(Entry<K,V> e = table[i]; e != null; e = e.next) {Object k;(e.hash == hash && ((k = e.key) == key || key.equals(k))) {// 获取当前的valueV oldValue = e.value;// 将要存储的value存进去e.value = value;e.recordAccess(this); oldValue;}}modCount++;addEntry(hash, key, value, i);return null;} V putForNullKey(V value) {(Entry<K,V> e = table[0]; e != null; e = e.next) {(e.key == null) {// 取出oldValue，并存入valueV oldValue = e.value;e.value = value;e.recordAccess(this); oldValue;}}modCount++;addEntry(0, null, value, 0);return null;} putForCreate(K key, V value) {hash = (key == null) ? 0 : hash(key.hashCode());i = indexFor(hash, table.length);(Entry<K,V> e = table[i]; e != null; e = e.next) {Object k;(e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) {e.value = value;return;}}// 否则需要创建新的桶createEntry(hash, key, value, i);}putAllForCreate(Map<? extends K, ? extends V> m) {for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {Map.Entry<? extends K, ? extends V> e = i.next();putForCreate(e.getKey(), e.getValue());}}resize(int newCapacity) {// 保存oldTableEntry[] oldTable = table;oldCapacity = oldTable.length;(oldCapacity == MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return;}// 根据新的容量新建一个tableEntry[] newTable = new Entry[newCapacity];// 将table转换成newTabletransfer(newTable);// 将table设置newTabletable = newTable;// 设置阈值threshold = (int)(newCapacity * loadFactor);} transfer(Entry[] newTable) {// 得到旧的tableEntry[] src = table;newCapacity = newTable.length;(int j = 0; j < src.length; j++) {// 取到格子里的桶（也就是链表）Entry<K,V> e = src[j];(e != null) {// 将当前格子设成nullsrc[j] = null; {// 取出下个桶Entry<K,V> next = e.next;i = indexFor(e.hash, newCapacity);// 设置e.next为newTable[i]保存的桶（也就是链表连接上）e.next = newTable[i];// 将e设成newTable[i]newTable[i] = e;// 设置e为下一个桶e = next;} while (e != null);}}}putAll(Map<? extends K, ? extends V> m) {numKeysToBeAdded = m.size();if (numKeysToBeAdded == 0)return;(numKeysToBeAdded > threshold) {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);}(Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {Map.Entry<? extends K, ? extends V> e = i.next();put(e.getKey(), e.getValue());}} V remove(Object key) {Entry<K,V> e = removeEntryForKey(key);return (e == null ? null : e.value);}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;(e != null) {Entry<K,V> next = e.next;Object k;(e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) {modCount++;// size减1size–;(prev == e)// 则table[i]等于下一个桶table[i] = next;prev.next = next;e.recordRemoval(this);return e;}prev = e;e = next;}return e;}Entry<K,V> removeMapping(Object o) {(!(o instanceof Map.Entry))return null;// 将o转成Map.EntryMap.Entry<K,V> entry = (Map.Entry<K,V>) o;// 得到他的keyObject key = entry.getKey();hash = (key == null) ? 0 : hash(key.hashCode());i = indexFor(hash, table.length);Entry<K,V> prev = table[i];Entry<K,V> e = prev;(e != null) {Entry<K,V> next = e.next;(e.hash == hash && e.equals(entry)) {modCount++;size–;if (prev == e)table[i] = next;elseprev.next = next;e.recordRemoval(this);return e;}prev = e;e = next;} e;} clear() {modCount++;Entry[] tab = table;(int i = 0; i < tab.length; i++)tab[i] = null;// 设置size为0size = 0;} containsValue(Object value) {(value == null)return containsNullValue();Entry[] tab = table;(int i = 0; i < tab.length ; i++)(Entry e = tab[i] ; e != null ; e = e.next) (value.equals(e.value))return true;;} 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() {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<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;} K getKey() {return key;} V getValue() {return value;} V setValue(V newValue) {V oldValue = value;value = newValue;return oldValue;} equals(Object o) {(!(o instanceof Map.Entry))return false;// 将o转成Map.EntryMap.Entry e = (Map.Entry)o;// 得到key和value对比是否相同，相同则为trueObject 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;};} hashCode() {return (key==null ? 0 : key.hashCode()) ^(value==null ? 0 : value.hashCode());} String toString() {return getKey() + “=” + getValue();}recordAccess(HashMap<K,V> m) {}recordRemoval(HashMap<K,V> m) {}}addEntry(int hash, K key, V value, int bucketIndex) {// 保存对应table的值Entry<K,V> e = table[bucketIndex];// 然后用新的桶套住旧的桶，香港虚拟主机，链表table[bucketIndex] = new Entry<K,V>(hash, key, value, e);(size++ >= threshold)// 调整容量resize(2 * table.length);}createEntry(int hash, K key, V value, int bucketIndex) {Entry<K,V> e = table[bucketIndex];table[bucketIndex] = new Entry<K,V>(hash, key, value, e);size++;}HashIterator<E> implements Iterator<E> {Entry<K,V> next; expectedModCount; index;// 当前的索引Entry<K,V> current; // 当前的桶// 构造方法HashIterator() {// 保存modCount，因为如果HashMap进行了任何操作modCount都会增加，所以如果发现modCount变化了，就可以抛出失败expectedModCount = modCount;(size > 0) {Entry[] t = table;while (index < t.length && (next = t[index++]) == null);}} hasNext() {return next != null;}Entry<K,V> nextEntry() {(modCount != expectedModCount)throw new ConcurrentModificationException();// 得到nextEntry<K,V> e = next;(e == null)throw new NoSuchElementException();((next = e.next) == null) {Entry[] t = table;while (index < t.length && (next = t[index++]) == null);}// 给current赋值current = e; e;} remove() {(current == null)throw new IllegalStateException();(modCount != expectedModCount)throw new ConcurrentModificationException();// 获得当前的keyObject k = current.key;// 设置current为nullcurrent = null;// 删除掉对应key的元素HashMap.this.removeEntryForKey(k);// 重置expectedModCountexpectedModCount = modCount;}}ValueIterator extends HashIterator<V> {public V next() {return nextEntry().value;}}KeyIterator extends HashIterator<K> {public K next() {return nextEntry().getKey();}}EntryIterator extends HashIterator<Map.Entry<K,V>> {public Map.Entry<K,V> next() {return nextEntry();}}// 定义对应的 iterator() 方法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;/*** 返回此映射中所包含的键的 Set 视图。* 该 set 受映射的支持，所以对映射的更改将反映在该 set 中，* 反之亦然。如果在对 set 进行迭代的同时修改了映射（通过迭代器自己的 remove 操作除外），* 则迭代结果是不确定的。该 set 支持元素的移除，通过* Iterator.remove、Set.remove、removeAll、retainAll 和 clear 操作* 可从该映射中移除相应的映射关系。它不支持 add 或 addAll 操作。*/public Set<K> keySet() {Set<K> ks = keySet;(ks != null ? ks : (keySet = new KeySet()));}KeySet extends AbstractSet<K> {Iterator<K> iterator() {return newKeyIterator();} size() {return size;} contains(Object o) {return containsKey(o);} remove(Object o) {return HashMap.this.removeEntryForKey(o) != null;} clear() {HashMap.this.clear();}}/*** 返回此映射所包含的值的 Collection 视图。* 该 collection 受映射的支持，所以对映射的更改将反映在该 collection 中，* 反之亦然。如果在对 collection 进行迭代的同时修改了映射（通过迭代器自己的 remove 操作除外），* 则迭代结果是不确定的。该 collection 支持元素的移除，* 通过 Iterator.remove、Collection.remove、removeAll、retainAll 和 clear 操作* 可从该映射中移除相应的映射关系。它不支持 add 或 addAll 操作。*/public Collection<V> values() {Collection<V> vs = values;return (vs != null ? vs : (values = new Values()));}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();}}/*** 返回此映射所包含的映射关系的 Set 视图。* 该 set 受映射支持，所以对映射的更改将反映在此 set 中，* 反之亦然。如果在对 set 进行迭代的同时修改了映射* （通过迭代器自己的 remove 操作，或者通过在该迭代器返回的映射项上执行 setValue 操作除外），* 则迭代结果是不确定的。该 set 支持元素的移除，* 通过 Iterator.remove、Set.remove、removeAll、retainAll 和 clear 操作* 可从该映射中移除相应的映射关系。它不支持 add 或 addAll 操作。*/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());}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();}} 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());}}}serialVersionUID = 362498820763181265L; 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; }}
，香港虚拟主机接受失败也等于给了自己从零开始的机会，
