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<K,V>[] 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<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;// 新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<K,V> e = tab[index];
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
return null;
    }

 //该方法用于增加hashtable的容量，
protected void rehash() {
//旧容量
int oldCapacity = table.length;
        Entry<K,V>[] 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<K,V>[] 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<K,V> old = oldMap[i] ; old != null ; ) {
                Entry<K,V> 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

秒客网