Hashtable之哈希表二

开心一笑

乐乐哈

视频教程

大家好，我录制的视频《Java之优雅编程之道》已经在CSDN学院发布了，有兴趣的同学可以购买观看，相信大家一定会收获到很多知识的。谢谢大家的支持……

视频地址：http://edu.csdn.net/lecturer/994

自我介绍

这一节，主要介绍我的源码，对我有个更深的了解……

我的特长

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

在我的源码中，有几个变量：
loadFactor：加载因子
initialCapacity:初始化容量
threshold: 它的值 = initialCapacity * loadFactor，当table数量超过该阈值后，进行reash
table：是一个Entry组，哈希表的”key-value键值对”都是存储在Entry数组中

//源码
private transient Entry[] table

count：在哈希表中Entry的总的数量，并不是哈希表容量大小（The total number of entries in the hash table）
modCount：用来实现“fail-fast”机制的（也就是快速失败）。所谓快速失败就是在并发集合中，其进行迭代操作时，若有其他线程对其进行结构性的修改，这时迭代器会立马感知到，并且立即抛出ConcurrentModificationException异常，而不是等到迭代完成之后才告诉你（你已经出错了）

接下来，就看看HashTable的构造方法：

//initialCapacity初始化容量，loadFactor加载因子
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，获得大小为initialCapacity的table数组 
        table = new Entry[initialCapacity];
        //计算阀值 
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        useAltHashing = sun.misc.VM.isBooted() &&
                (initialCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    }

public synchronized V put(K key, V value) {
        //确保value不为空
        if (value == null) {
            throw new NullPointerException();
        }

        // 确保key早已存在hashtable中
        Entry tab[] = table;
        int hash = hash(key);
        // 存储槽位索引
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                V old = e.value;
                e.value = value;// 新value覆盖旧value
                return old;
            }
        }

        modCount++;
        if (count >= threshold) {
            // 是否需要rehash
            rehash();

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

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

 //该方法用于增加hashtable的容量，
 protected void rehash() {
        //旧容量
        int oldCapacity = table.length;
        Entry[] oldMap = table;

        // overflow-conscious code
        //新容量 = 旧容量 * 2 + 1
        int newCapacity = (oldCapacity <<1) + 1;
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            if (oldCapacity == MAX_ARRAY_SIZE)

                return;
            newCapacity = MAX_ARRAY_SIZE;
        }
        //
        Entry[] newMap = new Entry[newCapacity];

        modCount++;
        threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        boolean currentAltHashing = useAltHashing;
        useAltHashing = sun.misc.VM.isBooted() &&
                (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean rehash = currentAltHashing ^ useAltHashing;

        table = newMap;

        for (int i = oldCapacity ; i-- > 0 ;) {
            for (Entry old = oldMap[i] ; old != null ; ) {
                Entry e = old;
                old = old.next;

                if (rehash) {
                    e.hash = hash(e.key);
                }
                // 重新计算各个元素在新Entry[]中的槽位index
                int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                e.next = newMap[index];// 已经存在槽位中的Entry放到当前元素的next中
                newMap[index] = e;
            }
        }
    }

上面的源码注释，有参考下面的优秀文章…..

优秀文章

http://www.cnblogs.com/caca/p/java_Hashtable.html