extends Dictionary<K, V>

implements Map<K, V>, Cloneable, java.io.Serializable {

/**

private transient Entry<?, ?>[] table;

/**

private transient int count;

/**

private int threshold;

/**

private float loadFactor;

/**

private transient int modCount = 0;

/**

private static final long serialVersionUID = 1421746759512286392L;

/**

public Hashtable(int initialCapacity, float loadFactor) {

if (initialCapacity < 0)

throw new IllegalArgumentException("Illegal Capacity: " +

initialCapacity);

if (loadFactor <= 0 || Float.isNaN(loadFactor))

throw new IllegalArgumentException("Illegal Load: " + loadFactor);

if (initialCapacity == 0)

initialCapacity = 1;

this.loadFactor = loadFactor;

table = new Entry<?, ?>[initialCapacity];

threshold = (int) Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);

}

/**

public Hashtable(int initialCapacity) {

this(initialCapacity, 0.75f);

}

/**

public Hashtable() {

// 默认构造函数，指定的容量大小是11；加载因子是0.75

this(11, 0.75f);

}

/**

public Hashtable(Map<? extends K, ? extends V> t) {

this(Math.max(2 * t.size(), 11), 0.75f);

putAll(t);

}

/**

public synchronized int size() {

return count;

}

/**

public synchronized boolean isEmpty() {

return count == 0;

}

/**

public synchronized Enumeration<K> keys() {

return this.<K>getEnumeration(KEYS);

}

/**

public synchronized Enumeration<V> elements() {

return this.<V>getEnumeration(VALUES);

}

/**

public synchronized boolean contains(Object value) {

if (value == null) {

throw new NullPointerException();

}

Entry<?, ?> tab[] = table;

// 查找：遍历所有Entry链表

for (int i = tab.length; i-- > 0; ) {

for (Entry<?, ?> e = tab[i]; e != null; e = e.next) {

if (e.value.equals(value)) {

return true;

}

}

}

return false;

}

/**

public boolean containsValue(Object value) {

return contains(value);

}

/**

public synchronized boolean containsKey(Object key) {

Entry<?, ?> tab[] = table;

int hash = key.hashCode();

/**

int index = (hash & 0x7FFFFFFF) % tab.length;

for (Entry<?, ?> e = tab[index]; e != null; e = e.next) {

if ((e.hash == hash) && e.key.equals(key)) {

return true;

}

}

return false;

}

/**

@SuppressWarnings("unchecked")

public synchronized V get(Object key) {

Entry<?, ?> tab[] = table;

int hash = key.hashCode();

int index = (hash & 0x7FFFFFFF) % tab.length;

for (Entry<?, ?> e = tab[index]; e != null; e = e.next) {

if ((e.hash == hash) && e.key.equals(key)) {

return (V) e.value;

}

}

return null;

}

/**

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**

@SuppressWarnings("unchecked")

protected void rehash() {

int oldCapacity = table.length;

Entry<?, ?>[] oldMap = table;

/**

int newCapacity = (oldCapacity << 1) + 1;

if (newCapacity - MAX_ARRAY_SIZE > 0) {

if (oldCapacity == MAX_ARRAY_SIZE)

// Keep running with MAX_ARRAY_SIZE buckets

return;

newCapacity = MAX_ARRAY_SIZE;

}

Entry<?, ?>[] newMap = new Entry<?, ?>[newCapacity];

modCount++;

threshold = (int) Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);

table = newMap;

// 拷贝每个Entry链表

for (int i = oldCapacity; i-- > 0; ) {

for (Entry<K, V> old = (Entry<K, V>) oldMap[i]; old != null; ) {

Entry<K, V> e = old;

old = old.next;

// 重新计算每个Entry链表的表头索引（rehash）

int index = (e.hash & 0x7FFFFFFF) % newCapacity;

// 开辟链表节点

e.next = (Entry<K, V>) newMap[index];

// 拷贝

newMap[index] = e;

}

}

}

/**

private void addEntry(int hash, K key, V value, int index) {

modCount++;

Entry<?, ?> tab[] = table;

// 当前元素大于等于阈值，就扩容并且再计算hash值

if (count >= threshold) {

rehash();

tab = table;

hash = key.hashCode();

index = (hash & 0x7FFFFFFF) % tab.length;

}

// Creates the new entry.

@SuppressWarnings("unchecked")

Entry<K, V> e = (Entry<K, V>) tab[index];

// 和HashMap不同，Hashtable选择把新插入的元素放到链表最前边，而且没有使用红黑树

tab[index] = new Entry<>(hash, key, value, e);

count++;

}

/**

public synchronized V put(K key, V value) {

// value为空抛出空指针异常

if (value == null) {

throw new NullPointerException();

}

// Makes sure the key is not already in the hashtable.

Entry<?, ?> tab[] = table;

/**

int hash = key.hashCode();

/**

int index = (hash & 0x7FFFFFFF) % tab.length;

@SuppressWarnings("unchecked")

Entry<K, V> entry = (Entry<K, V>) tab[index];

for (; entry != null; entry = entry.next) {

if ((entry.hash == hash) && entry.key.equals(key)) {

V old = entry.value;

entry.value = value;

return old;

}

}

// 如果key对应的值不存在，就调用addEntry方法加入

addEntry(hash, key, value, index);

return null;

}

/**

public synchronized V remove(Object key) {

Entry<?, ?> tab[] = table;

int hash = key.hashCode();

int index = (hash & 0x7FFFFFFF) % tab.length;

@SuppressWarnings("unchecked")

Entry<K, V> e = (Entry<K, V>) tab[index];

for (Entry<K, V> prev = null; e != null; prev = e, e = e.next) {

if ((e.hash == hash) && e.key.equals(key)) {

modCount++;

if (prev != null) {

prev.next = e.next;

} else {

tab[index] = e.next;

}

count--;

V oldValue = e.value;

e.value = null;

return oldValue;

}

}

return null;

}

/**

public synchronized void putAll(Map<? extends K, ? extends V> t) {

//foreach 循环map数据put到hashTable中

for (Map.Entry<? extends K, ? extends V> e : t.entrySet())

put(e.getKey(), e.getValue());

}

/**

public synchronized void clear() {

Entry<?, ?> tab[] = table;

modCount++;

for (int index = tab.length; --index >= 0; )

tab[index] = null;

count = 0;

}

/**

public synchronized Object clone() {

try {

Hashtable<?, ?> t = (Hashtable<?, ?>) super.clone();

t.table = new Entry<?, ?>[table.length];

for (int i = table.length; i-- > 0; ) {

t.table[i] = (table[i] != null)

? (Entry<?, ?>) table[i].clone() : null;

}

t.keySet = null;

t.entrySet = null;

t.values = null;

t.modCount = 0;

return t;

} catch (CloneNotSupportedException e) {

// this shouldn't happen, since we are Cloneable

throw new InternalError(e);

}

}

/**

public synchronized String toString() {

int max = size() - 1;

if (max == -1)

return "{}";

StringBuilder sb = new StringBuilder();

Iterator<Map.Entry<K, V>> it = entrySet().iterator();

sb.append('{');

for (int i = 0; ; i++) {

Map.Entry<K, V> e = it.next();

K key = e.getKey();

V value = e.getValue();

sb.append(key == this ? "(this Map)" : key.toString());

sb.append('=');

sb.append(value == this ? "(this Map)" : value.toString());

if (i == max)

return sb.append('}').toString();

sb.append(", ");

}

}

private <T> Enumeration<T> getEnumeration(int type) {

if (count == 0) {

return Collections.emptyEnumeration();

} else {

return new Enumerator<>(type, false);

}

}

/**

private <T> Iterator<T> getIterator(int type) {

if (count == 0) {

return Collections.emptyIterator();

} else {

return new Enumerator<>(type, true);

}

}

// 视图

/**

private transient volatile Set<K> keySet;

private transient volatile Set<Map.Entry<K, V>> entrySet;

private transient volatile Collection<V> values;

/**

public Set<K> keySet() {

if (keySet == null)

keySet = Collections.synchronizedSet(new KeySet(), this);

return keySet;

}

/**

private class KeySet extends AbstractSet<K> {

public Iterator<K> iterator() {

return getIterator(KEYS);

}

public int size() {

return count;

}

public boolean contains(Object o) {

return containsKey(o);

}

public boolean remove(Object o) {

return Hashtable.this.remove(o) != null;

}

public void clear() {

Hashtable.this.clear();

}

}

/**

public Set<Map.Entry<K, V>> entrySet() {

if (entrySet == null)

entrySet = Collections.synchronizedSet(new EntrySet(), this);

return entrySet;

}

/**

private class EntrySet extends AbstractSet<Map.Entry<K, V>> {

public Iterator<Map.Entry<K, V>> iterator() {

return getIterator(ENTRIES);

}

public boolean add(Map.Entry<K, V> o) {

return super.add(o);

}

/**

public boolean contains(Object o) {

if (!(o instanceof Map.Entry))

return false;

Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;

Object key = entry.getKey();

Entry<?, ?>[] tab = table;

int hash = key.hashCode();

int index = (hash & 0x7FFFFFFF) % tab.length;

for (Entry<?, ?> e = tab[index]; e != null; e = e.next)

if (e.hash == hash && e.equals(entry))

return true;

return false;

}

/**

public boolean remove(Object o) {

if (!(o instanceof Map.Entry))

return false;

Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;

Object key = entry.getKey();

Entry<?, ?>[] tab = table;

int hash = key.hashCode();

int index = (hash & 0x7FFFFFFF) % tab.length;

@SuppressWarnings("unchecked")

Entry<K, V> e = (Entry<K, V>) tab[index];

for (Entry<K, V> prev = null; e != null; prev = e, e = e.next) {

if (e.hash == hash && e.equals(entry)) {

modCount++;

if (prev != null)

prev.next = e.next;

else

tab[index] = e.next;

count--;

e.value = null;

return true;

}

}

return false;

}

public int size() {

return count;

}

public void clear() {

Hashtable.this.clear();

}

}

/**

public Collection<V> values() {

if (values == null)

values = Collections.synchronizedCollection(new ValueCollection(),

this);

return values;

}

/**

private class ValueCollection extends AbstractCollection<V> {

public Iterator<V> iterator() {

return getIterator(VALUES);

}

public int size() {

return count;

}

public boolean contains(Object o) {

return containsValue(o);

}

public void clear() {

Hashtable.this.clear();

}

}

// Comparison and hashing

/**

public synchronized boolean equals(Object o) {

if (o == this)

return true;

if (!(o instanceof Map))

return false;

Map<?, ?> t = (Map<?, ?>) o;

if (t.size() != size())

return false;

try {

/**

Iterator<Map.Entry<K, V>> i = entrySet().iterator();

while (i.hasNext()) {

Map.Entry<K, V> e = i.next();

K key = e.getKey();

V value = e.getValue();

if (value == null) {

if (!(t.get(key) == null && t.containsKey(key)))

return false;

} else {

if (!value.equals(t.get(key)))

return false;

}

}

} catch (ClassCastException unused) {

return false;

} catch (NullPointerException unused) {

return false;

}

return true;

}

/**

public synchronized int hashCode() {

int h = 0;

//若 Hashtable的实际大小为0 或者 加载因子<0，则返回0

if (count == 0 || loadFactor < 0)

return h; // Returns zero

loadFactor = -loadFactor; // Mark hashCode computation in progress

Entry<?, ?>[] tab = table;

//返回Hashtable中的每个Entry的key和value的异或值的总和

for (Entry<?, ?> entry : tab) {

while (entry != null) {

h += entry.hashCode();

entry = entry.next;

}

}

loadFactor = -loadFactor; // Mark hashCode computation complete

return h;

}

@Override

public synchronized V getOrDefault(Object key, V defaultValue) {

V result = get(key);

return (null == result) ? defaultValue : result;

}

@SuppressWarnings("unchecked")

@Override

public synchronized void forEach(BiConsumer<? super K, ? super V> action) {

Objects.requireNonNull(action); // explicit check required in case

// table is empty.

final int expectedModCount = modCount;

Entry<?, ?>[] tab = table;

for (Entry<?, ?> entry : tab) {

while (entry != null) {

action.accept((K) entry.key, (V) entry.value);

entry = entry.next;

if (expectedModCount != modCount) {

throw new ConcurrentModificationException();

}

}

}

}

@SuppressWarnings("unchecked")

@Override

public synchronized void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {

Objects.requireNonNull(function); // explicit check required in case

// table is empty.

final int expectedModCount = modCount;

Entry<K, V>[] tab = (Entry<K, V>[]) table;

for (Entry<K, V> entry : tab) {

while (entry != null) {

entry.value = Objects.requireNonNull(

function.apply(entry.key, entry.value));

entry = entry.next;

if (expectedModCount != modCount) {

throw new ConcurrentModificationException();

}

}

}

}

@Override

public synchronized V putIfAbsent(K key, V value) {

Objects.requireNonNull(value);

// Makes sure the key is not already in the hashtable.

Entry<?, ?> tab[] = table;

int hash = key.hashCode();

int index = (hash & 0x7FFFFFFF) % tab.length;

@SuppressWarnings("unchecked")

Entry<K, V> entry = (Entry<K, V>) tab[index];

for (; entry != null; entry = entry.next) {

if ((entry.hash == hash) && entry.key.equals(key)) {

V old = entry.value;

if (old == null) {

entry.value = value;

}

return old;

}

}

addEntry(hash, key, value, index);

return null;

}

@Override

public synchronized boolean remove(Object key, Object value) {

Objects.requireNonNull(value);

Entry<?, ?> tab[] = table;

int hash = key.hashCode();

int index = (hash & 0x7FFFFFFF) % tab.length;

@SuppressWarnings("unchecked")

Entry<K, V> e = (Entry<K, V>) tab[index];

for (Entry<K, V> prev = null; e != null; prev = e, e = e.next) {

if ((e.hash == hash) && e.key.equals(key) && e.value.equals(value)) {

modCount++;

if (prev != null) {

prev.next = e.next;

} else {

tab[index] = e.next;

}

count--;

e.value = null;

return true;

}

}

return false;

}

@Override

public synchronized boolean replace(K key, V oldValue, V newValue) {

Objects.requireNonNull(oldValue);

Objects.requireNonNull(newValue);

Entry<?, ?> tab[] = table;

int hash = key.hashCode();

int index = (hash & 0x7FFFFFFF) % tab.length;

@SuppressWarnings("unchecked")

Entry<K, V> e = (Entry<K, V>) tab[index];

for (; e != null; e = e.next) {

if ((e.hash == hash) && e.key.equals(key)) {

if (e.value.equals(oldValue)) {

e.value = newValue;

return true;

} else {

return false;

}

}

}

return false;

}

/**

@Override

public synchronized V replace(K key, V value) {

Objects.requireNonNull(value);

Entry<?, ?> tab[] = table;

int hash = key.hashCode();

int index = (hash & 0x7FFFFFFF) % tab.length;

@SuppressWarnings("unchecked")

Entry<K, V> e = (Entry<K, V>) tab[index];

for (; e != null; e = e.next) {

if ((e.hash == hash) && e.key.equals(key)) {

V oldValue = e.value;

e.value = value;

return oldValue;

}

}

return null;

}

@Override

public synchronized V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {

Objects.requireNonNull(mappingFunction);

Entry<?, ?> tab[] = table;

int hash = key.hashCode();

int index = (hash & 0x7FFFFFFF) % tab.length;

@SuppressWarnings("unchecked")

Entry<K, V> e = (Entry<K, V>) tab[index];

for (; e != null; e = e.next) {

if (e.hash == hash && e.key.equals(key)) {

// Hashtable not accept null value

return e.value;

}

}

V newValue = mappingFunction.apply(key);

if (newValue != null) {

addEntry(hash, key, newValue, index);

}

return newValue;

}

@Override

public synchronized V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {

Objects.requireNonNull(remappingFunction);

Entry<?, ?> tab[] = table;

int hash = key.hashCode();

int index = (hash & 0x7FFFFFFF) % tab.length;

@SuppressWarnings("unchecked")

Entry<K, V> e = (Entry<K, V>) tab[index];

for (Entry<K, V> prev = null; e != null; prev = e, e = e.next) {

if (e.hash == hash && e.key.equals(key)) {

V newValue = remappingFunction.apply(key, e.value);

if (newValue == null) {

modCount++;

if (prev != null) {

prev.next = e.next;

} else {

tab[index] = e.next;

}

count--;

} else {

e.value = newValue;

}

return newValue;

}

}

return null;

}

@Override

public synchronized V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {

Objects.requireNonNull(remappingFunction);

Entry<?, ?> tab[] = table;

int hash = key.hashCode();

int index = (hash & 0x7FFFFFFF) % tab.length;

@SuppressWarnings("unchecked")

Entry<K, V> e = (Entry<K, V>) tab[index];

for (Entry<K, V> prev = null; e != null; prev = e, e = e.next) {

if (e.hash == hash && Objects.equals(e.key, key)) {

V newValue = remappingFunction.apply(key, e.value);

if (newValue == null) {

modCount++;

if (prev != null) {

prev.next = e.next;

} else {

tab[index] = e.next;

}

count--;

} else {

e.value = newValue;

}

return newValue;

}

}

V newValue = remappingFunction.apply(key, null);

if (newValue != null) {

addEntry(hash, key, newValue, index);

}

return newValue;

}

@Override

public synchronized V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {

Objects.requireNonNull(remappingFunction);

Entry<?, ?> tab[] = table;

int hash = key.hashCode();

int index = (hash & 0x7FFFFFFF) % tab.length;

@SuppressWarnings("unchecked")

Entry<K, V> e = (Entry<K, V>) tab[index];

for (Entry<K, V> prev = null; e != null; prev = e, e = e.next) {

if (e.hash == hash && e.key.equals(key)) {

V newValue = remappingFunction.apply(e.value, value);

if (newValue == null) {

modCount++;

if (prev != null) {

prev.next = e.next;

} else {

tab[index] = e.next;

}

count--;

} else {

e.value = newValue;

}

return newValue;

}

}

if (value != null) {

addEntry(hash, key, value, index);

}

return value;

}

/**

private void writeObject(java.io.ObjectOutputStream s)

throws IOException {

Entry<Object, Object> entryStack = null;

synchronized (this) {