首页 > 代码库 > HashTable源代码剖析

HashTable源代码剖析

2024-10-31 01:54:02 204人阅读

<span style="font-size:14px;font-weight: normal;">public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {

    //transient不能被序列化  数据部分
    private transient Entry[] table;

  // 元素个数
    private transient int count;

//当HashTable的大小超过这个阈值时重Hash
    private int threshold;

//装载因子 过大会导致冲突机会变大  过小会导致空间浪费
    private float loadFactor;

  //fail-fast机制  保证迭代时，其它线程不干扰
    private transient int modCount = 0;

//构造函数 初始容量仅仅要大于0即可，不同于HashMap（系统优化为2的幂次）
    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)(initialCapacity * loadFactor);
    }

     //默认0.75的装载因子
    public Hashtable(int initialCapacity) {
	this(initialCapacity, 0.75f);
    }

   //默认的构造函数
    public Hashtable() {
	this(11, 0.75f);
    }

  //map的初始容量必须大于等于11
    public Hashtable(Map<? extends K, ? extends V> t) {
	this(Math.max(2*t.size(), 11), 0.75f);
	putAll(t);
    }
  //synchronized线程安全的原因
    public synchronized int size() {
	return count;
    }

  //是否为空
    public synchronized boolean isEmpty() {
	return count == 0;
    }

   //返回枚举迭代器 keys
    public synchronized Enumeration<K> keys() {
	return this.<K>getEnumeration(KEYS);
    }

      //返回枚举迭代器 values
    public synchronized Enumeration<V> elements() {
	return this.<V>getEnumeration(VALUES);
    }

    //是否包括此元素 从最后一列循环
    public synchronized boolean contains(Object value) {
	if (value =http://www.mamicode.com/= null) {> 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<K,V> t = (Hashtable<K,V>) super.clone();
	    t.table = new Entry[table.length];
	    for (int i = table.length ; i-- > 0 ; ) {
		t.table[i] = (table[i] != null)
		    ? (Entry<K,V>) 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();
	}
    }


    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 = http://www.mamicode.com/e.getValue();>
 "(this Map)" : value.toString());

	    if (i == max)
		return sb.append('}').toString();
	    sb.append(", ");
	}
    }


    private <T> Enumeration<T> getEnumeration(int type) {
	if (count == 0) {
	    return (Enumeration<T>)emptyEnumerator;
	} else {
	    return new Enumerator<T>(type, false);
	}
    }

    private <T> Iterator<T> getIterator(int type) {
	if (count == 0) {
	    return (Iterator<T>) emptyIterator;
	} else {
	    return new Enumerator<T>(type, true);
	}
    }

 
    private transient volatile Set<K> keySet = null;
    private transient volatile Set<Map.Entry<K,V>> entrySet = null;
    private transient volatile Collection<V> values = null;

   //得到set集合
    public Set<K> keySet() {
	if (keySet == null)
	    keySet = Collections.synchronizedSet(new KeySet(), this);
	return keySet;
    }
   //KeySet类  key的集合
    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;
    }
//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<K,V> entry = (Map.Entry<K,V>) o;
	    K key = entry.getKey();
            Entry[] tab = table;
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;

            for (Entry<K,V> e = tab[index], 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 = http://www.mamicode.com/null;>
 null : (Entry<K,V>) next.clone()));
	}

	// Map.Entry Ops

	public K getKey() {
	    return key;
	}

	public V getValue() {
	    return value;
	}

	public V setValue(V value) {
	    if (value =http://www.mamicode.com/= null)>
 e.getKey()==null : key.equals(e.getKey())) &&
	       (value=http://www.mamicode.com/=null ?
 e.getValue()==null : value.equals(e.getValue()));
	}
      //哈希码 通过 ^
	public int hashCode() {
	    return hash ^ (value=http://www.mamicode.com/=null ? 0 : value.hashCode());>
 (T)e.value : (T)e);
	    }
	    throw new NoSuchElementException("Hashtable Enumerator");
	}

	// Iterator methods
	public boolean hasNext() {
	    return hasMoreElements();
	}

	public T next() {
	    if (modCount != expectedModCount)
		throw new ConcurrentModificationException();
	    return nextElement();
	}

	public void remove() {
	    if (!iterator)
		throw new UnsupportedOperationException();
	    if (lastReturned == null)
		throw new IllegalStateException("Hashtable Enumerator");
	    if (modCount != expectedModCount)
		throw new ConcurrentModificationException();

	    synchronized(Hashtable.this) {
		Entry[] tab = Hashtable.this.table;
		int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;

		for (Entry<K,V> e = tab[index], prev = null; e != null;
		     prev = e, e = e.next) {
		    if (e == lastReturned) {
			modCount++;
			expectedModCount++;
			if (prev == null)
			    tab[index] = e.next;
			else
			    prev.next = e.next;
			count--;
			lastReturned = null;
			return;
		    }
		}
		throw new ConcurrentModificationException();
	    }
	}
    }


    private static class EmptyEnumerator implements Enumeration<Object> {

	EmptyEnumerator() {
	}

	public boolean hasMoreElements() {
	    return false;
	}

	public Object nextElement() {
	    throw new NoSuchElementException("Hashtable Enumerator");
	}
    }



    private static class EmptyIterator implements Iterator<Object> {

	EmptyIterator() {
	}

	public boolean hasNext() {
	    return false;
	}

	public Object next() {
	    throw new NoSuchElementException("Hashtable Iterator");
	}

	public void remove() {
	    throw new IllegalStateException("Hashtable Iterator");
	}

    }

}</span>

几点总结

针对Hashtable，我们相同给出几点比較重要的总结。但要结合与HashMap的比較来总结。

1、二者的存储结构和解决冲突的方法都是同样的。

2、HashTable在不指定容量的情况下的默认容量为11，而HashMap为16。Hashtable不要求底层数组的容量一定要为2的整数次幂，而HashMap则要求一定为2的整数次幂。

3、Hashtable中key和value都不同意为null，而HashMap中key和value都同意为null（key仅仅能有一个为null，而value则能够有多个为null）。可是假设在Hashtable中有类似put(null,null)的操作，编译相同能够通过，由于key和value都是Object类型。但执行时会抛出NullPointerException异常，这是JDK的规范规定的。

我们来看下ContainsKey方法和ContainsValue的源代码：

[java] view plaincopy

// 推断Hashtable是否包括“值(value)”
public synchronized boolean contains(Object value) {
//注意。Hashtable中的value不能是null，
// 若是null的话，抛出异常!
if (value == null) {
throw new NullPointerException();
}
// 从后向前遍历table数组中的元素(Entry)
// 对于每一个Entry(单向链表)。逐个遍历。推断节点的值是否等于value
Entry tab[] = table;
for (int i = tab.length ; i-- > 0 ;) {
for (Entry<K,V> 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);
}
// 推断Hashtable是否包括key
public synchronized boolean containsKey(Object key) {
Entry tab[] = table;
/计算hash值，直接用key的hashCode取代
int hash = key.hashCode();
// 计算在数组中的索引值
int index = (hash & 0x7FFFFFFF) % tab.length;
// 找到“key相应的Entry(链表)”，然后在链表中找出“哈希值”和“键值”与key都相等的元素
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return true;
}
}
return false;
}

非常明显。假设value为null，会直接抛出NullPointerException异常。但源代码中并没有对key是否为null推断，有点小不解。只是NullPointerException属于RuntimeException异常。是能够由JVM自己主动抛出的，或许对key的值在JVM中有所限制吧。

4、Hashtable扩容时。将容量变为原来的2倍加1。而HashMap扩容时。将容量变为原来的2倍。

5、Hashtable计算hash值。直接用key的hashCode()，而HashMap又一次计算了key的hash值。Hashtable在求hash值相应的位置索引时，用取模运算。而HashMap在求位置索引时，则用与运算。且这里一般先用hash&0x7FFFFFFF后，再对length取模。&0x7FFFFFFF的目的是为了将负的hash值转化为正值，由于hash值有可能为负数。而&0x7FFFFFFF后。仅仅有符号外改变。而后面的位都不变。

HashTable源代码剖析

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > HashTable源代码剖析

HashTable源代码剖析

几点总结

看完仍有疑问？有类似问题直接问程序猿