浅析HashTable源码

20131103          HashTable源码浅析

       

        和HashMap一样，HashTable也是一个散列表。

        HashTable继承于Dictionary，Map<K,V>, 实现了Cloneable, java.io.Serializable接口。

        通过上网查找，了解到，HashTable的函数都是同步的，也就是说，它是线程安全的。它的key、value都可以为null。另外，HashTable中的映射不是有序的。

         HashTable有两个重要的参数：容量大小和加载因子。

         哈希表采用挂链法解决冲突，被挂的主体暂且称之为“衣架”，容量指的就是哈希表中“衣架”总的数量，初始容量就是哈希表创建时的容量。加载因子，是对哈希表在其容量自动增加之前可以达到多满的一个衡量标准，就好似，衣架能够挂衣服的数量总是有限的，超过了这个限度，衣架就会发生变形，坏掉。

         HashTable的继承关系如下：

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {}

          在HashTable源码中有一个关键字常出现：transient

          假设某个类的成员变量是transient，那么当通过ObjectOutStream把这个类的某个实例保存到磁盘上时，实际上transient变量的值是不会保存的。因为当从磁盘中读出这个对象的时候，对象的该变量会没有被赋值。（这些是在网上了解到的）

           HashTable和HashMap一样，同样是采用挂链法解决冲突。

一、HashTable的数据存储：

       HashTable中的key-value都是存储在table数组中的。

private transient Entry[] table;

 以下是Entry的数据结构：

 private static class Entry<K,V> implements Map.Entry<K,V> {
	int hash;
	K key;
	V value;
	Entry<K,V> next;

	protected Entry(int hash, K key, V value, Entry<K,V> next) {
	    this.hash = hash;
	    this.key = key;
	    this.value = value;
	    this.next = next;
	}

	protected Object clone() {
	    return new Entry<K,V>(hash, key, value,
				  (next==null ? null : (Entry<K,V>) next.clone()));
	}

	public K getKey() {
	    return key;
	}

	public V getValue() {
	    return value;
	}

	public V setValue(V value) {
	    if (value == null)
		throw new NullPointerException();

	    V oldValue = this.value;
	    this.value = value;
	    return oldValue;
	}

	public boolean equals(Object o) {
	    if (!(o instanceof Map.Entry))
		return false;
	    Map.Entry e = (Map.Entry)o;

	    return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
	       (value==null ? e.getValue()==null : value.equals(e.getValue()));
	}

	public int hashCode() {
	    return hash ^ (value==null ? 0 : value.hashCode());
	}

	public String toString() {
	    return key.toString()+"="+value.toString();
	}
    }

 在Entry的数据结构中实现了getKey(),getValue(),setValue(V value),equals(Object o),hashCode()这些函数。

HashTable的特点之一是，使用HashTable不会有重复的数据出现，这一点，通过equals（）方法实现，当两个Entry的key和value都相等时，则认为它们相等。

二、构造函数

       HashTable中共有4个构造函数

1、默认构造函数

 public Hashtable() {
	this(11, 0.75f);
    }

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

2、指定容量大小的构造函数

 public Hashtable(int initialCapacity) {
	this(initialCapacity, 0.75f);
    }

 3、指定容量大小和加载因子的构造函数

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);
    }

 4、

 public Hashtable(Map<? extends K, ? extends V> t) {
	this(Math.max(2*t.size(), 11), 0.75f);
	putAll(t);
    }

 这个查找资料后了解到是包含“子Map”的构造函数。作用是将“子Map”的全部元素都添加到HashTable中。

 在这里只介绍了HashTable的存储结构和构造函数，更深层次的理解还需要实际操作才行。

 

 

 

 

 

 

 

 

 

 

 

评论

2 楼 learnworld 2013-11-04  

xphwv 写道

通过上网查找，了解到，HashTable的函数都是同步的，也就是说，它是线程安全的。它的key、value都可以为null。另外，HashTable中的映射不是有序的。

HashTable的key、value不可为null,是否写错了？

HashTable的key、value不可为null, HashMap可以, 对null key做了特殊处理。

1 楼 xphwv 2013-11-04  

通过上网查找，了解到，HashTable的函数都是同步的，也就是说，它是线程安全的。它的key、value都可以为null。另外，HashTable中的映射不是有序的。

HashTable的key、value不可为null,是否写错了？