Hashtable和HashMap源码分析

Hashtable和HashMap源码分析

         JDK中自带的Hashtable和HashMap是数据结构中哈希表的实现。除了这两个，还有一个HashSet的实现，但是HashSet基本是基于HashMap实现的，因此在这里我们只讨论Hashtable和HashMap的实现细节。

         首先列出经过源码分析，得出的关于Hashtable和HashMap之间的异同点如下：

         1、Hashtable和HashMap的继承关系比较如下：

 

         其中没有列出它们两个继承的Cloneable和Serializable接口，在下面的分析也是一样，不会分析比较它们的序列化和Cloneable的实现。

 

          2、Hashtable和HashMap之间最为明显的区别：同步处理

                在Hashtable的实现中，所有的外部访问方法都进行了同步化处理，即在方法中添加synchronized关键字；

                Hashtable中的方法示例：

 

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

     //此处省略内部实现
}

public synchronized V remove(Object key) {

     //此处省略内部实现
}

                而在HashMap的实现中，没有进行同步化处理；

                HashMap中的同样两个方法示例：

 

public V put(K key, V value) {
    //此处省略内部实现
}

public V remove(Object key) {
    //此处省略内部实现
}

 

 

          3、Hashtable和HashMap关于输入的key和value的限制：

          在Hashtable的实现中，不允许添加key或是value为null的键值对，如果key为null，则在put(K key,V value)方法调用hash()方法获取hash值时会抛出空指针异常， 而如果value为null，则在刚进入put(K key, V value)是就会检查而抛出空指针异常，如下具体程序所示：

 

         如下所示为Hashtable中的实现：

 

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.
        Entry tab[] = table;
        int hash = hash(key);//在这里调用了下面的hash(Object k)方法

    //在此省略了下面的实现......
}

//在下面的方法中可以看出，只要传入的k值为null，则在下面调用时就会产生空指针异常
private int hash(Object k) {
        if (useAltHashing) {
            if (k.getClass() == String.class) {
                return sun.misc.Hashing.stringHash32((String) k);
            } else {
                int h = hashSeed ^ k.hashCode();
                h ^= (h >>> 20) ^ (h >>> 12);
                return h ^ (h >>> 7) ^ (h >>> 4);
             }
        } else  {
            return k.hashCode();
        }
}

 

          而在HashMap的实现中，指定索引位置0处用来存放key值为null的键值对，如果在put方法中传入key值为null，如果索引位置0处存在已经存储的元素，则使用现在传进来的value值替换原来的value值，如果没有存储元素，则直接放置。所以我们容易知道，在HashMap中，键值key为null的键值对只能在索引位置为0的地方存储一个，即在整个HashMap中只允许有一个键值对的key为null，后面添加的只是在修改value值。

 

         如下所示为HashMap中的实现：

public V put(K key, V value) {
      if (key == null)
          return putForNullKey(value);
    //在这里省略了后面key不为null的实现
}

//当key为null时调用
private V putForNullKey(V value) {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        //此时索引位置0处不为null，则替换原来的value值
      if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    //索引位置0处为空，则将键值对放置进去
    addEntry(0, null, value, 0);
    return null;
}

        

        4、在Hashtable和HashMap中，在每一次添加元素时，都会检查此时表中已有的数据个数与临界值的大小关系，当已存入的数据个数大于等于threshold临界值时，Hashtable会调用rehash()方法来对数组进行扩充，HashMap会调用resize(int capacity)方法来对数组进行扩充，然后依次遍历原数组，重新计算元素的hash值，存储到新的数组中，而且两者都是将数组扩大一倍，其中的临界值threshold = loadFactor(装载因子，默认0.75) * capacity(数组大小)；

 

         5、在Hashtable和HashMap中都提供了迭代器可让外部调用。在Hashtable和HashMap中均有entrySet()、keySet()、values()方法，分别返回Set<Entry<K,V>>、Set<K>、Collection<V>这三种类型的对象引用，其中就像上面说的，Hashtable返回的对象都是经过同步处理的，举个例子如下：

public Set<Map.Entry<K,V>> entrySet() {
    if (entrySet==null)
        entrySet = Collections.synchronizedSet(new EntrySet(), this);
    return entrySet;
}

 而在HashMap中返回的对象引用，没有经过同步处理，举例如下：

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