zy19982004--容器学习二：Hashtable源码分析

一.前言

1. HashMap和Hashtable大部分算法是相同的，容器学习一：HashMap源码分析 对HashMap源码进行了分析，可以先阅读它。
2. 相同的算法部分不再分析，本文主要考虑Hashtable和HashMap的不同之处。

 

二.Hashtable成员变量

private transient Entry[] table;

// 等同于HashMap里面的size
private transient int count;

private int threshold;

private float loadFactor;

private transient int modCount = 0;

 

 

 

三.Hashtable构造函数

// DEFAULT_INITIAL_CAPACITY=11，DEFAULT_LOAD_FACTOR还是0.75
public Hashtable() {
    this(11, 0.75f);
}

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;
    // 直接用initialCapacity初始化，并没有要求用2的次方指来初始化
    this.loadFactor = loadFactor;
    table = new Entry[initialCapacity];
    threshold = (int) (initialCapacity * loadFactor);
}

 

 

四.hash算法和index算法

//自己拿到key的hash值
int hash = key.hashCode();
//计算index做了求模运算。
int index = (hash & 0x7FFFFFFF) % tab.length;

 

 

五.取数据

public synchronized V get(Object key) {
    Entry tab[] = table;
    //Hashtable所有的方法都不接受null的key，所有的地方都是不判断就直接key.hashCode();
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<K, V> e = tab[index]; e != null; e = e.next) {
        //同HahsMap相比没有判断e.key==key，
        //Hahstable里面，e.key.equals(key)就够了，在key不为null的前提下e.key==key是e.key.equals(key)的充分不必要条件
        if ((e.hash == hash) && e.key.equals(key)) {
            return e.value;
        }
    }
    return null;
}

 

 

六.存数据

public synchronized V put(K key, V value) {
        if (value == null) {
            throw new NullPointerException();
        }

        Entry tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry<K, V> e = tab[index]; e != null; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                V old = e.value;
                e.value = value;
                return old;
            }
        }

        modCount++;
        //HashMap先加Entry再决定是否扩容，Hahstable再判断大小在加Entry
        //我还是喜欢这样比较：count + 1 >  threshold
        if (count >= threshold) {
            rehash();

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

        // Creates the new entry.
        Entry<K, V> e = tab[index];
        tab[index] = new Entry<K, V>(hash, key, value, e);
        count++;
        return null;
    }

    protected void rehash() {
        int oldCapacity = table.length;
        Entry[] oldMap = table;

        int newCapacity = oldCapacity * 2 + 1;
        Entry[] newMap = new Entry[newCapacity];

        modCount++;
        threshold = (int) (newCapacity * loadFactor);
        table = newMap;
                //和HashMap算法是一样的，建议看HashMap里面的写法好理解点。
        for (int i = oldCapacity; i-- > 0;) {
            for (Entry<K, V> old = oldMap[i]; old != null;) {
                Entry<K, V> e = old;
                old = old.next;

                int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                e.next = newMap[index];
                newMap[index] = e;
            }
        }
    }

 

 

七.总结

 

	HashMap	Hashtable
出现时间	JDK1.2，所以代码质量更高，更容易明白	JDK1.0
并发控制	没有考虑并发	所有方法都加了synchronized，即使有些我认为不需要的也加了
是否接受值为null的Key 或Value	接受	不接收。put等方法里面：if (value == null) {             显示throw new NullPointerException();         }；int hash=key.hashcode隐示throw NullPointerException();
初始化table	缺省容量16。初始化时可以指定initial capacity，若不是2的次方，HashMap将选取第一个大于initial capacity 的2的次方值作为其初始长度	缺省容量11。初始化时可以指定initial capacity
扩容	添加Entry后判断是否该扩容。扩容至2*oldCapacity	先判断是否扩容再添加Entry。扩容至2*oldCapacity + 1
数据遍历的方式	Iterator	Iterator 和 Enumeration
是否支持fast-fail	支持fast-fail	用Iterator遍历，支持fast-fail 用Enumeration不支持fast-fail.
hash算法和index算法	优于Hashtable，通过对Key的hash做移位运算和位的与运算，使其能更广泛地分散到数组的不同位置	当数组长度较小，并且Key的hash值低位数值分散不均匀时，不同的hash值计算得到相同下标值的几率较高
实现和继承	extends AbstractMap 骨架结构的体现，代码质量上去了	extends Dictionary implements Map 直接实现Map接口。多基础了一个已过时的经Dictionary类，就不用去管了