继承结构
public class Hashtable<K,V> extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {
数据存储结构
数组 + 单项链表 （线程安全）
写在前面的一些方法、说明
- !!!
key和value都不可为null -
protected void rehash()扩容
protected void rehash() {
int oldCapacity = table.length;
HashtableEntry<?,?>[] oldMap = table;
// overflow-conscious code
int newCapacity = (oldCapacity << 1) + 1; // 2倍+1
if (newCapacity - MAX_ARRAY_SIZE > 0) { // 保证table桶的大小不超过 MAX_ARRAY_SIZE
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
// 实例化新容量的HashtableEntry数组
HashtableEntry<?,?>[] newMap = new HashtableEntry<?,?>[newCapacity];
modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
// 两层遍历，第一层遍历数组
for (int i = oldCapacity ; i-- > 0 ;) {
// 第二层遍历链表
for (HashtableEntry<K,V> old = (HashtableEntry<K,V>)oldMap[i] ; old != null ; ) {
HashtableEntry<K,V> e = old;
old = old.next;
// 重新计算当前元素应处于新table中的位置
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
// 如果index相同位置上插入节点，总是插在队头
e.next = (HashtableEntry<K,V>)newMap[index];
newMap[index] = e;
}
}
}
-
private void addEntry(int hash, K key, V value, int index)添加元素
private void addEntry(int hash, K key, V value, int index) {
modCount++;
HashtableEntry<?,?> tab[] = table;
if (count >= threshold) { // 存储的元素大小到达阀值，触发扩容
// Rehash the table if the threshold is exceeded
rehash();
// 扩容之后，重新key的hash值和index
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
// 新添加的元素总是插入在对头位置
@SuppressWarnings("unchecked")
HashtableEntry<K,V> e = (HashtableEntry<K,V>) tab[index];
tab[index] = new HashtableEntry<>(hash, key, value, e);
count++;
}
一、增
public synchronized V put(K key, V value)
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) { // value不可null
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
HashtableEntry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
HashtableEntry<K,V> entry = (HashtableEntry<K,V>)tab[index];
// 遍历链表查找元素，找到即修改key对应的value值
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
// 找不着即创建新对象插入
addEntry(hash, key, value, index);
return null;
}
public synchronized void putAll(Map<? extends K, ? extends V> t)
public synchronized void putAll(Map<? extends K, ? extends V> t) {
// 遍历入参map的Map.Entry,逐一put
for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
put(e.getKey(), e.getValue());
}
-
public synchronized V putIfAbsent(K key, V value)如果存在key-value键值对，且value为null，才会赋值新value
@Override
public synchronized V putIfAbsent(K key, V value) {
Objects.requireNonNull(value);
// Makes sure the key is not already in the hashtable.
HashtableEntry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
HashtableEntry<K,V> entry = (HashtableEntry<K,V>)tab[index];
for (; entry != null; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
// 如果Map中存在key对应的value值，且不为null，不会覆盖老值，为null，则赋值新value
if (old == null) {
entry.value = value;
}
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
二、删
-
public synchronized V remove(Object key)匹配key移除
public synchronized V remove(Object key) {
HashtableEntry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
HashtableEntry<K,V> e = (HashtableEntry<K,V>)tab[index];
for(HashtableEntry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
// 找到key对应存储的节点
if ((e.hash == hash) && e.key.equals(key)) {
modCount++;
if (prev != null) {
prev.next = e.next;// 移除key对应节点，链接前后节点
} else { // key对应节点在队头位置
tab[index] = e.next;
}
count--;
V oldValue = e.value;
e.value = null; // 释放资源 help gc
return oldValue;
}
}
return null;
}
-
public synchronized boolean remove(Object key, Object value)同时匹配key-value移除，也可用作查找当前Map中是否包含某对key-value
@Override
public synchronized boolean remove(Object key, Object value) {
Objects.requireNonNull(value); // value不可null
HashtableEntry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
HashtableEntry<K,V> e = (HashtableEntry<K,V>)tab[index];
for (HashtableEntry<K,V> prev = null; e != null; prev = e, e = e.next) {
// 同时比较key 和 value
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;
}
三、改
-
public synchronized V replace(K key, V value)将key对应的老value替换为入参value
@Override
public synchronized V replace(K key, V value) {
Objects.requireNonNull(value);
HashtableEntry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
HashtableEntry<K,V> e = (HashtableEntry<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;
}
-
public synchronized boolean replace(K key, V oldValue, V newValue)将key-oldValue对应的oldValue替换为newValue
@Override
public synchronized boolean replace(K key, V oldValue, V newValue) {
Objects.requireNonNull(oldValue);
Objects.requireNonNull(newValue);
HashtableEntry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
HashtableEntry<K,V> e = (HashtableEntry<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;
}
-
public synchronized void clear()清空所有
public synchronized void clear() {
HashtableEntry<?,?> tab[] = table;
modCount++;
for (int index = tab.length; --index >= 0; )
tab[index] = null;
count = 0;
}
四、查
-
public synchronized V get(Object key)key 取 value
public synchronized V get(Object key) {
HashtableEntry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (HashtableEntry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return (V)e.value;
}
}
return null;
}
-
public synchronized boolean contains(Object value)是否包含此value
public synchronized boolean contains(Object value) {
if (value == null) {
throw new NullPointerException();
}
HashtableEntry<?,?> tab[] = table;
for (int i = tab.length ; i-- > 0 ;) {
for (HashtableEntry<?,?> e = tab[i] ; e != null ; e = e.next) {
if (e.value.equals(value)) {
return true;
}
}
}
return false;
}
public boolean containsValue(Object value)
public boolean containsValue(Object value) {
return contains(value);
}
-
public synchronized boolean containsKey(Object key)是否包含此key
public synchronized boolean containsKey(Object key) {
HashtableEntry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (HashtableEntry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return true;
}
}
return false;
}
-
private <T> Enumeration<T> getEnumeration(int type)，type = KEYS、VALUES
private <T> Enumeration<T> getEnumeration(int type) {
if (count == 0) {
return Collections.emptyEnumeration();
} else {
return new Enumerator<>(type, false);
}
}
private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
·················
public boolean hasMoreElements() {
HashtableEntry<?,?> e = entry;
int i = index;
HashtableEntry<?,?>[] t = table;
/* Use locals for faster loop iteration */
while (e == null && i > 0) {
e = t[--i];
}
entry = e;
index = i;
return e != null;
}
@SuppressWarnings("unchecked")
public T nextElement() {
HashtableEntry<?,?> et = entry;
int i = index;
HashtableEntry<?,?>[] t = table;
/* Use locals for faster loop iteration */
while (et == null && i > 0) {
et = t[--i];
}
entry = et;
index = i;
if (et != null) {
HashtableEntry<?,?> e = lastReturned = entry;
entry = e.next;
return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
}
throw new NoSuchElementException("Hashtable Enumerator");
}
·····················
}
public synchronized Enumeration<K> keys()
public synchronized Enumeration<K> keys() {
return this.<K>getEnumeration(KEYS);
}
public synchronized Enumeration<V> elements()
public synchronized Enumeration<V> elements() {
return this.<V>getEnumeration(VALUES);
}
-
public Set<K> keySet()获取key的Set集合
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();
}
}
private <T> Iterator<T> getIterator(int type) {
if (count == 0) {
return Collections.emptyIterator();
} else {
return new Enumerator<>(type, true);
}
}
-
public Set<Map.Entry<K,V>> entrySet()获取存储Entry对象的Set集合
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();
HashtableEntry<?,?>[] tab = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (HashtableEntry<?,?> 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();
HashtableEntry<?,?>[] tab = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
HashtableEntry<K,V> e = (HashtableEntry<K,V>)tab[index];
for(HashtableEntry<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()获取存储所有value的集合
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();
}
}
网友评论