开发者社区> 技术小牛人> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

Jdk源码解读

简介:
+关注继续查看

hashTable继承自dic类,同时实现了map接口和Cloneable、Serializable两个接口,代表该类是可复制、序列化的类。

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

ps:dic类和map类较为相似,是一个抽象的hash映射类,包含了一些简单的空方法和接口。

private transient Entry<?,?>[] table;

瞬时数组变量,它就是hashtable中,最核心的数据存储区域。

 

    /**
     * The total number of entries in the hash table.     */
    private transient int count;

数组长度,不知道大家发现没有,jdk非常喜欢用一个独立变量来表示容器中数据的大小,而不是每次返回核心数据的size或length。

 

阈值,这个之前专门强调过,这里简单说下,他是容积和负载因子的乘积,表示的含义是当前容器中,能表现出较好性能的数据量上限。超过这个上限时,容器的性能将会有比较大的下降。注意容积和阈值是有区别的。

threshold  ['θrhold]  n. 入口;门槛;开始;极限;临界值 

   private int threshold;

负载因子,是用来设定当前容器中,元素的填充率的。

你可以理解成容器是一个城市,这个城市中最佳入住率的一个上限是负载因子。这个城市的入住用户最佳的数目,就是他的阈值。

    /**
     * The load factor for the hashtable.
     *
     * @serial
     */
    private float loadFactor;

接下来是modCount ,这个变量的意义是,记录hashtable中,被修改的次数(包括增、删、改)三个操作的。而其用途呢,是未来被用作判定快速失败时(fail-fast)的依据数据。关于快速失败,这个我会在下边讲到。大家这里只要知道modCount这个变量的表示的含义是什么就可以。

    private transient int modCount = 0;

然后是版本序列号

    private static final long serialVersionUID = 1421746759512286392L;

接着是构造函数,参数分别为初始容积和负载因子。

函数内会首先判断初始容积和负载因子是否为正数。

接着如果初始容积为0,则赋予默认值1.也就是说,真实的容积至少都要为1。

接着对table赋予初始值,一个长度为初始容积大小的Entry数组。(防盗连接:本文首发自http://www.cnblogs.com/jilodream/ )接着计算

阈值=(初始容积和负载因子的乘积),(当前系统中最大的数组长度+1),二者的最小值。

也就是说阈值不能超过数组的最大长度+1。这里注意一个isNaN()方法,是个很有意思的方法,研究该方法的源码后,你会觉得很有意思。这个我会在以后的文章中讲到。

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)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    }

只要初始容积的构造函数,负载因子默认为0.75

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

无参的构造函数,初始容积使用为11,负载因子为0.75

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

不知道大家发现没,尽管提供了一个可能的,但是jdk的源码往往系统提供多个,应用于不同场景的接口,这些接口往往其实只是对自身其他接口的一个适配。但是对于调用者来说,这样却很舒服。

 

接着是最后一个构造函数,参数为一个map,map的k,v分别继承自hashTable中的K,V.

函数首先调用一遍通用的构造函数,负载因子为0.75。初始容积为map长度的两倍以及默认的11,二者的较大值。也就是说对于初始容积来说,最小都要取到11。

接着调用putAll方法,将map中的数据添加到HashTable中。

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

size()方法,方法采用同步机制,返回count变量。由于容器中并不是所有的元素都占满了数据,所以直接用变量返回值的速度和效率会更高点。同时由于count会随时变动,这里采用同步方法的形式进行线程保护。

    public synchronized int size() {        return count;
    }

isEmpyt,判断当前数组是否为空,与size()方法一致。

    public synchronized boolean isEmpty() {        return count == 0;
    }

keys,elements方法,分别返回返回hashTable中所有的key和value的枚举集合。

这里KEYS,VALUES为静态int常量。getEnumeration在下文中会提到。另外与前边的方法相同,这里也是对整个方法进行同步加锁。

    public synchronized Enumeration<K> keys() {        return this.<K>getEnumeration(KEYS);
    }    public synchronized Enumeration<V> elements() {        return this.<V>getEnumeration(VALUES);
    }

 接着是contains方法,方法意义不再赘述。

实现逻辑,首先判断value是否为null,如果为null则直接抛出空引用。

接着将table变量赋值给tab临时变量。然后循环tab,依次取出tab中的entry,以及entry的后继元素。(防盗连接:本文首发自http://www.cnblogs.com/jilodream/ )如果元素的value equals()判断等于参数value,则直接返回true。整个方法结束后,为发现,则会返回false。同时方法本身也是加同步锁进行线程安全保护。

    public synchronized boolean contains(Object value) {        if (value == null) {            throw new NullPointerException();
        }

        Entry<?,?> tab[] = table;        for (int i = tab.length ; i-- > 0 ;) {            for (Entry<?,?> e = tab[i] ; e != null ; e = e.next) {                if (e.value.equals(value)) {                    return true;
                }
            }
        }        return false;
    }

接着是实现map接口的抽象方法,只是对contains方法进行了一层封装。

    public boolean containsValue(Object value) {        return contains(value);
    }

接着是线程同步方法:containsKey,方法含义不赘述,逻辑如下:

设定临时变量并赋值table。取出key的hashCode。注意这里并没有判定key是否为null。

而前文中的value则是判定的。这是由于value是作为equals方法的参数的。即使是null也无法被发现,但是判定一个映射的value为null表示的真的为null还是没有映射到,这很歧义,所以干脆直接抛出异常。回到正文,根据hashCode计算出其在table数组中的索引。其实就是取低8位数字然后除以数组length取余数。(防盗连接:本文首发自http://www.cnblogs.com/jilodream/ )

接着依次循环table该索引的后继元素,判定是否equals()相等。如果有则返回true。如果始终没有找到,则返回false。

    public synchronized boolean containsKey(Object key) {
        Entry<?,?> tab[] = table;        int hash = key.hashCode();        int index = (hash & 0x7FFFFFFF) % tab.length;        for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {            if ((e.hash == hash) && e.key.equals(key)) {                return true;
            }
        }        return false;
    }

get()方法,与containsKey方法的逻辑是一致的。不同点是,在返回结果是,如果确实存在该key,则返回对应的value,否则返回null。

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

接着是前文提到的数组最大数字常亮。这里注意看参数的注释。部分虚拟机是设定数组的长度限制的。如果超出,可能会导致OOM异常

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

接着是rehash方法。这个方法是一个受保护方法。会在接下来的,hashtable添加元素的场景中被调用。他的作用呢,就是重新申请一块大小合适的内存。然后将键值元素重新安置到这块元素中。

那么就需要两个步骤。

1、计算新内存的大小。

2、计算元素在新table中的位置。

    先看代码:

 1     protected void rehash() { 2         int oldCapacity = table.length; 3         Entry<?,?>[] oldMap = table; 4  5         // overflow-conscious code 6         int newCapacity = (oldCapacity << 1) + 1; 7         if (newCapacity - MAX_ARRAY_SIZE > 0) { 8             if (oldCapacity == MAX_ARRAY_SIZE) 9                 // Keep running with MAX_ARRAY_SIZE buckets10                 return;11             newCapacity = MAX_ARRAY_SIZE;12         }13         Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];14 15         modCount++;16         threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);17         table = newMap;18 19         for (int i = oldCapacity ; i-- > 0 ;) {20             for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {21                 Entry<K,V> e = old;22                 old = old.next;23 24                 int index = (e.hash & 0x7FFFFFFF) % newCapacity;25                 e.next = (Entry<K,V>)newMap[index];26                 newMap[index] = e;27             }28         }29     }

代码中会首先获取旧table的长度oldCapacity 。然后oldCapacity 乘以2再加1.算出新table的长度newCapacity 。

接着判断newCapacity 是否超出了hashtable所能设定的最大值:MAX_ARRAY_SIZE。如果超出,则判断oldCapacity 是否已经等于最大值。如果已经等于,则认定,当前hashtable的长度已经到达所允许的上限。无法再继续扩容。则直接返回。

否则将MAX_ARRAY_SIZE赋值给newCapacity 。作为新的长度。也就是说rehash在大小允许的情况下,一般会翻倍扩容。但是如果翻倍后长度超出上限,则以上限大小作为扩容后新的大小。

接着以newCapacity 作为长度,new出一个Entry数组,作为新的table元素存放容器。

modCount自加1。

接着计算阈值:newCapacity 乘以负载因子和MAX_ARRAY_SIZE+1 取较小值。注意这里负载因子是可以大于1的。因此newCapacity 乘以负载因子,式可以大于MAX_ARRAY_SIZE的。

接着就是计算旧有table中的键值元素在新table中的位置了:这里使用的是双层循环,外层依次遍历Entry主数组上的元素。如果entry[i]不等于null值,则将该元素及其后继元素依次计算出新的位置,然后插入到主数组上的对应位置。同时将主数组中原来位置的元素。作为新放置元素的后继。也就是每个新元素,插在每个对应位置的链表最前侧。至于为什么不放在这个对应链表的最后位置。其实很简单,因为这是一个链式存储结构,需要依次遍历每个元素,才能找到队尾的元素。

接着是添加元素的私有方法addEntry。(防盗连接:本文首发自http://www.cnblogs.com/jilodream/ )

首先是modCount自加1.

接着如果当前table的数量已经超过了阈值,那么就进行一次rehash,接着根据key的hashCode计算出当前键值对的输入索引。接着取出table对应索引位置的元素一同做出一个新的Entry元素放在这个对应索引的位置上。(这里要注意后续的entry 的构造方法)同时count数目自加1。这里需要注意的是,当前数目如果已经超过阈值,前边讲到的rehash是不一定会重新做出新数组的(length超过了MAX_ARRAY_SIZE的限制时)很多人在理解这里的时候,就认定只要count超过阈值就一定会重新分配table内存的地址,这个理解是存在问题的。

 1     private void addEntry(int hash, K key, V value, int index) { 2         modCount++; 3  4         Entry<?,?> tab[] = table; 5         if (count >= threshold) { 6             // Rehash the table if the threshold is exceeded 7             rehash(); 8  9             tab = table;10             hash = key.hashCode();11             index = (hash & 0x7FFFFFFF) % tab.length;12         }13 14         // Creates the new entry.15         @SuppressWarnings("unchecked")16         Entry<K,V> e = (Entry<K,V>) tab[index];17         tab[index] = new Entry<>(hash, key, value, e);18         count++;19     }

接着是put方法。这个方法是hashtable非常常用的一个public方法。方法本身是一个同方法。在方法中对于参数value和key有逻辑:如果为null时,均会报出空引用异常。

 1     public synchronized V put(K key, V value) { 2         // Make sure the value is not null 3         if (value == null) { 4             throw new NullPointerException(); 5         } 6  7         // Makes sure the key is not already in the hashtable. 8         Entry<?,?> tab[] = table; 9         int hash = key.hashCode();10         int index = (hash & 0x7FFFFFFF) % tab.length;11         @SuppressWarnings("unchecked")12         Entry<K,V> entry = (Entry<K,V>)tab[index];13         for(; entry != null ; entry = entry.next) {14             if ((entry.hash == hash) && entry.key.equals(key)) {15                 V old = entry.value;16                 entry.value = value;17                 return old;18             }19         }20 21         addEntry(hash, key, value, index);22         return null;23     }

接着算出key所应该对应的主数组的索引。循环遍历出该数组元素所对应的队列(tab[index]),如果元素的hash值等于新添加元素的hash,同时entry的key等于(equals)key方法。则直接替换这个entry的value为参数传入的value,与此同时返回旧old。

如果整个循环都发现没有,则说明当前hashtable其实并不存在该参数key,则调用刚才说的addEntry方法,将参数key value,及对应的索引传进去。这里注意put方法为同步公有方法,而addEntry为私有非同步方法,这里是否存在线程安全问题呢?(防盗连接:本文首发自http://www.cnblogs.com/jilodream/ )其实并不存在,这是由于addEntry尽管会操作全局变量主数组,但是addEntry方法只会被put方法调用。而凡是调用put方法的线程均需要先拿到this变量锁。尽管再次进去无同步的addEntry的方法区,当前线程仍然持有this变量锁,其他线程若想操作全局变量主数组,仍然需要等待全局锁的释放才可以。

接着是remove方法。该方法逻辑如下:首选根据key值计算出元素所对应主数组中的索引位置。然后依次循环主数组下该索引对应元素的后继元素。判断该元素的hash是否等于key参数的hash,以及元素是否equels参数key。如果相等,则将该元素从队列中抹除。同时hashtable的长度count 减1,同时modCount值也自加1。如果循环结束仍未找到合适的元素与参数key相等,则返回null

 

 1     public synchronized V remove(Object key) { 2         Entry<?,?> tab[] = table; 3         int hash = key.hashCode(); 4         int index = (hash & 0x7FFFFFFF) % tab.length; 5         @SuppressWarnings("unchecked") 6         Entry<K,V> e = (Entry<K,V>)tab[index]; 7         for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) { 8             if ((e.hash == hash) && e.key.equals(key)) { 9                 modCount++;10                 if (prev != null) {11                     prev.next = e.next;12                 } else {13                     tab[index] = e.next;14                 }15                 count--;16                 V oldValue = e.value;17                 e.value = null;18                 return oldValue;19             }20         }21         return null;22     }

接着是putAll方法,该方法会将map集合中的对象,采用foreach的形式,依次调用put方法添加到hashtable集合中。

    public synchronized void putAll(Map<? extends K, ? extends V> t) {        for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
            put(e.getKey(), e.getValue());
    }

接着是clear方法。该方法首先将modCount加1.接着循环主数组中的所有元素,然后依次对这些元素置于null。然后设定count元素为0。这里有一点需要注意,即clear时,只清理了主数组中的元素。对于主数组中对应元素的后继列表,则采用不予理会的态度。等待GC来回收掉。

1     public synchronized void clear() {2         Entry<?,?> tab[] = table;3         modCount++;4         for (int index = tab.length; --index >= 0; )5             tab[index] = null;6         count = 0;7     }

接着是clone方法。该方法会克隆一个自身对象的副本。此方法会克隆出一个空的hashtable。然后将主数组中的所有元素克隆一遍,放置到克隆对象的对应位置上。注意在克隆元素的时候,会将元素的后继队列元素,依次的克隆下去。接着初始化克隆对象的其他变量:置空keyset、entryset、values对象,设置modCount为0。

 1     public synchronized Object clone() { 2         try { 3             Hashtable<?,?> t = (Hashtable<?,?>)super.clone(); 4             t.table = new Entry<?,?>[table.length]; 5             for (int i = table.length ; i-- > 0 ; ) { 6                 t.table[i] = (table[i] != null) 7                     ? (Entry<?,?>) table[i].clone() : null; 8             } 9             t.keySet = null;10             t.entrySet = null;11             t.values = null;12             t.modCount = 0;13             return t;14         } catch (CloneNotSupportedException e) {15             // this shouldn't happen, since we are Cloneable16             throw new InternalError(e);17         }18     }

然后是重写的tostring方法。这个方法逻辑也很简单,就是依次遍历元素。最后生成一个类似于{“key1”=”value1”,“key2”=”value2”}的结构。有趣的是这里需要调用key.tostring,倘若key是当前hashtable自己的话,就直接使用“(this map)”字符串。防止出现无限递归。

 1     public synchronized String toString() { 2         int max = size() - 1; 3         if (max == -1) 4             return "{}"; 5  6         StringBuilder sb = new StringBuilder(); 7         Iterator<Map.Entry<K,V>> it = entrySet().iterator(); 8  9         sb.append('{');10         for (int i = 0; ; i++) {11             Map.Entry<K,V> e = it.next();12             K key = e.getKey();13             V value = e.getValue();14             sb.append(key   == this ? "(this Map)" : key.toString());15             sb.append('=');16             sb.append(value == this ? "(this Map)" : value.toString());17 18             if (i == max)19                 return sb.append('}').toString();20             sb.append(", ");21         }22     }

到这里hashtable的主要逻辑就已经都介绍完了。其余还包括一些keyset、valueSet的内部类、以及replaceAll、putIfAbsent等封装方法。由于代码逻辑简单,数量较大,这里就不一一列举了。

总结:

1、Hashtable包括tostirng等方法在,几乎所有对外api方法都是同步保护的,这就是为什么很多人认为hashtable线程安全的原因。而在基础上,对于同步方法所调用的private方法,则大多采用非同步的形式。因为这些方法,往往只有一个public方法可以调用,这样就做到了在安全的基础上可以更快执行代码。

2、hashtable的内部结构大致如下,和早前的hashmap很像:

3、关于元素的取值,hashtable不允许key和value取值为null。所以get时,发现为null,即说明key元素不存在。同时hashtable在扩容是采用的是乘2加1的方式。这与有些容器直接乘2有所区别。

4、关于变量modCount的使用。我们可以看到这个方法中,每次在发生增删改的时候都会出现modCount++的动作。而modcount可以理解为是当前hashtable的状态。每发生一次操作,状态就向前走一步。(防盗连接:本文首发自http://www.cnblogs.com/jilodream/ )设置这个状态,主要是由于hashtable等容器类在迭代时,判断数据是否过时时使用的。尽管hashtable采用了原生的同步锁来保护数据安全。但是在出现迭代数据的时候,则无法保证边迭代,边正确操作。于是使用这个值来标记状态。一旦在迭代的过程中状态发生了改变,则会快速抛出一个异常,终止迭代行为(所以这种错误也叫做快速失败fail—fast):

hashTable继承自dic类,同时实现了map接口和Cloneable、Serializable两个接口,代表该类是可复制、序列化的类。

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

ps:dic类和map类较为相似,是一个抽象的hash映射类,包含了一些简单的空方法和接口。

private transient Entry<?,?>[] table;

瞬时数组变量,它就是hashtable中,最核心的数据存储区域。

 

    /**
     * The total number of entries in the hash table.     */
    private transient int count;

数组长度,不知道大家发现没有,jdk非常喜欢用一个独立变量来表示容器中数据的大小,而不是每次返回核心数据的size或length。

 

阈值,这个之前专门强调过,这里简单说下,他是容积和负载因子的乘积,表示的含义是当前容器中,能表现出较好性能的数据量上限。超过这个上限时,容器的性能将会有比较大的下降。注意容积和阈值是有区别的。

threshold  ['θrhold]  n. 入口;门槛;开始;极限;临界值 

   private int threshold;

负载因子,是用来设定当前容器中,元素的填充率的。

你可以理解成容器是一个城市,这个城市中最佳入住率的一个上限是负载因子。这个城市的入住用户最佳的数目,就是他的阈值。

    /**
     * The load factor for the hashtable.
     *
     * @serial
     */
    private float loadFactor;

接下来是modCount ,这个变量的意义是,记录hashtable中,被修改的次数(包括增、删、改)三个操作的。而其用途呢,是未来被用作判定快速失败时(fail-fast)的依据数据。关于快速失败,这个我会在下边讲到。大家这里只要知道modCount这个变量的表示的含义是什么就可以。

    private transient int modCount = 0;

然后是版本序列号

    private static final long serialVersionUID = 1421746759512286392L;

接着是构造函数,参数分别为初始容积和负载因子。

函数内会首先判断初始容积和负载因子是否为正数。

接着如果初始容积为0,则赋予默认值1.也就是说,真实的容积至少都要为1。

接着对table赋予初始值,一个长度为初始容积大小的Entry数组。(防盗连接:本文首发自http://www.cnblogs.com/jilodream/ )接着计算

阈值=(初始容积和负载因子的乘积),(当前系统中最大的数组长度+1),二者的最小值。

也就是说阈值不能超过数组的最大长度+1。这里注意一个isNaN()方法,是个很有意思的方法,研究该方法的源码后,你会觉得很有意思。这个我会在以后的文章中讲到。

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)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    }

只要初始容积的构造函数,负载因子默认为0.75

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

无参的构造函数,初始容积使用为11,负载因子为0.75

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

不知道大家发现没,尽管提供了一个可能的,但是jdk的源码往往系统提供多个,应用于不同场景的接口,这些接口往往其实只是对自身其他接口的一个适配。但是对于调用者来说,这样却很舒服。

 

接着是最后一个构造函数,参数为一个map,map的k,v分别继承自hashTable中的K,V.

函数首先调用一遍通用的构造函数,负载因子为0.75。初始容积为map长度的两倍以及默认的11,二者的较大值。也就是说对于初始容积来说,最小都要取到11。

接着调用putAll方法,将map中的数据添加到HashTable中。

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

size()方法,方法采用同步机制,返回count变量。由于容器中并不是所有的元素都占满了数据,所以直接用变量返回值的速度和效率会更高点。同时由于count会随时变动,这里采用同步方法的形式进行线程保护。

    public synchronized int size() {        return count;
    }

isEmpyt,判断当前数组是否为空,与size()方法一致。

    public synchronized boolean isEmpty() {        return count == 0;
    }

keys,elements方法,分别返回返回hashTable中所有的key和value的枚举集合。

这里KEYS,VALUES为静态int常量。getEnumeration在下文中会提到。另外与前边的方法相同,这里也是对整个方法进行同步加锁。

    public synchronized Enumeration<K> keys() {        return this.<K>getEnumeration(KEYS);
    }    public synchronized Enumeration<V> elements() {        return this.<V>getEnumeration(VALUES);
    }

 接着是contains方法,方法意义不再赘述。

实现逻辑,首先判断value是否为null,如果为null则直接抛出空引用。

接着将table变量赋值给tab临时变量。然后循环tab,依次取出tab中的entry,以及entry的后继元素。(防盗连接:本文首发自http://www.cnblogs.com/jilodream/ )如果元素的value equals()判断等于参数value,则直接返回true。整个方法结束后,为发现,则会返回false。同时方法本身也是加同步锁进行线程安全保护。

    public synchronized boolean contains(Object value) {        if (value == null) {            throw new NullPointerException();
        }

        Entry<?,?> tab[] = table;        for (int i = tab.length ; i-- > 0 ;) {            for (Entry<?,?> e = tab[i] ; e != null ; e = e.next) {                if (e.value.equals(value)) {                    return true;
                }
            }
        }        return false;
    }

接着是实现map接口的抽象方法,只是对contains方法进行了一层封装。

    public boolean containsValue(Object value) {        return contains(value);
    }

接着是线程同步方法:containsKey,方法含义不赘述,逻辑如下:

设定临时变量并赋值table。取出key的hashCode。注意这里并没有判定key是否为null。

而前文中的value则是判定的。这是由于value是作为equals方法的参数的。即使是null也无法被发现,但是判定一个映射的value为null表示的真的为null还是没有映射到,这很歧义,所以干脆直接抛出异常。回到正文,根据hashCode计算出其在table数组中的索引。其实就是取低8位数字然后除以数组length取余数。(防盗连接:本文首发自http://www.cnblogs.com/jilodream/ )

接着依次循环table该索引的后继元素,判定是否equals()相等。如果有则返回true。如果始终没有找到,则返回false。

    public synchronized boolean containsKey(Object key) {
        Entry<?,?> tab[] = table;        int hash = key.hashCode();        int index = (hash & 0x7FFFFFFF) % tab.length;        for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {            if ((e.hash == hash) && e.key.equals(key)) {                return true;
            }
        }        return false;
    }

get()方法,与containsKey方法的逻辑是一致的。不同点是,在返回结果是,如果确实存在该key,则返回对应的value,否则返回null。

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

接着是前文提到的数组最大数字常亮。这里注意看参数的注释。部分虚拟机是设定数组的长度限制的。如果超出,可能会导致OOM异常

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

接着是rehash方法。这个方法是一个受保护方法。会在接下来的,hashtable添加元素的场景中被调用。他的作用呢,就是重新申请一块大小合适的内存。然后将键值元素重新安置到这块元素中。

那么就需要两个步骤。

1、计算新内存的大小。

2、计算元素在新table中的位置。

    先看代码:

 1     protected void rehash() { 2         int oldCapacity = table.length; 3         Entry<?,?>[] oldMap = table; 4  5         // overflow-conscious code 6         int newCapacity = (oldCapacity << 1) + 1; 7         if (newCapacity - MAX_ARRAY_SIZE > 0) { 8             if (oldCapacity == MAX_ARRAY_SIZE) 9                 // Keep running with MAX_ARRAY_SIZE buckets10                 return;11             newCapacity = MAX_ARRAY_SIZE;12         }13         Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];14 15         modCount++;16         threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);17         table = newMap;18 19         for (int i = oldCapacity ; i-- > 0 ;) {20             for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {21                 Entry<K,V> e = old;22                 old = old.next;23 24                 int index = (e.hash & 0x7FFFFFFF) % newCapacity;25                 e.next = (Entry<K,V>)newMap[index];26                 newMap[index] = e;27             }28         }29     }

代码中会首先获取旧table的长度oldCapacity 。然后oldCapacity 乘以2再加1.算出新table的长度newCapacity 。

接着判断newCapacity 是否超出了hashtable所能设定的最大值:MAX_ARRAY_SIZE。如果超出,则判断oldCapacity 是否已经等于最大值。如果已经等于,则认定,当前hashtable的长度已经到达所允许的上限。无法再继续扩容。则直接返回。

否则将MAX_ARRAY_SIZE赋值给newCapacity 。作为新的长度。也就是说rehash在大小允许的情况下,一般会翻倍扩容。但是如果翻倍后长度超出上限,则以上限大小作为扩容后新的大小。

接着以newCapacity 作为长度,new出一个Entry数组,作为新的table元素存放容器。

modCount自加1。

接着计算阈值:newCapacity 乘以负载因子和MAX_ARRAY_SIZE+1 取较小值。注意这里负载因子是可以大于1的。因此newCapacity 乘以负载因子,式可以大于MAX_ARRAY_SIZE的。

接着就是计算旧有table中的键值元素在新table中的位置了:这里使用的是双层循环,外层依次遍历Entry主数组上的元素。如果entry[i]不等于null值,则将该元素及其后继元素依次计算出新的位置,然后插入到主数组上的对应位置。同时将主数组中原来位置的元素。作为新放置元素的后继。也就是每个新元素,插在每个对应位置的链表最前侧。至于为什么不放在这个对应链表的最后位置。其实很简单,因为这是一个链式存储结构,需要依次遍历每个元素,才能找到队尾的元素。

接着是添加元素的私有方法addEntry。(防盗连接:本文首发自http://www.cnblogs.com/jilodream/ )

首先是modCount自加1.

接着如果当前table的数量已经超过了阈值,那么就进行一次rehash,接着根据key的hashCode计算出当前键值对的输入索引。接着取出table对应索引位置的元素一同做出一个新的Entry元素放在这个对应索引的位置上。(这里要注意后续的entry 的构造方法)同时count数目自加1。这里需要注意的是,当前数目如果已经超过阈值,前边讲到的rehash是不一定会重新做出新数组的(length超过了MAX_ARRAY_SIZE的限制时)很多人在理解这里的时候,就认定只要count超过阈值就一定会重新分配table内存的地址,这个理解是存在问题的。

 1     private void addEntry(int hash, K key, V value, int index) { 2         modCount++; 3  4         Entry<?,?> tab[] = table; 5         if (count >= threshold) { 6             // Rehash the table if the threshold is exceeded 7             rehash(); 8  9             tab = table;10             hash = key.hashCode();11             index = (hash & 0x7FFFFFFF) % tab.length;12         }13 14         // Creates the new entry.15         @SuppressWarnings("unchecked")16         Entry<K,V> e = (Entry<K,V>) tab[index];17         tab[index] = new Entry<>(hash, key, value, e);18         count++;19     }

接着是put方法。这个方法是hashtable非常常用的一个public方法。方法本身是一个同方法。在方法中对于参数value和key有逻辑:如果为null时,均会报出空引用异常。

 1     public synchronized V put(K key, V value) { 2         // Make sure the value is not null 3         if (value == null) { 4             throw new NullPointerException(); 5         } 6  7         // Makes sure the key is not already in the hashtable. 8         Entry<?,?> tab[] = table; 9         int hash = key.hashCode();10         int index = (hash & 0x7FFFFFFF) % tab.length;11         @SuppressWarnings("unchecked")12         Entry<K,V> entry = (Entry<K,V>)tab[index];13         for(; entry != null ; entry = entry.next) {14             if ((entry.hash == hash) && entry.key.equals(key)) {15                 V old = entry.value;16                 entry.value = value;17                 return old;18             }19         }20 21         addEntry(hash, key, value, index);22         return null;23     }

接着算出key所应该对应的主数组的索引。循环遍历出该数组元素所对应的队列(tab[index]),如果元素的hash值等于新添加元素的hash,同时entry的key等于(equals)key方法。则直接替换这个entry的value为参数传入的value,与此同时返回旧old。

如果整个循环都发现没有,则说明当前hashtable其实并不存在该参数key,则调用刚才说的addEntry方法,将参数key value,及对应的索引传进去。这里注意put方法为同步公有方法,而addEntry为私有非同步方法,这里是否存在线程安全问题呢?(防盗连接:本文首发自http://www.cnblogs.com/jilodream/ )其实并不存在,这是由于addEntry尽管会操作全局变量主数组,但是addEntry方法只会被put方法调用。而凡是调用put方法的线程均需要先拿到this变量锁。尽管再次进去无同步的addEntry的方法区,当前线程仍然持有this变量锁,其他线程若想操作全局变量主数组,仍然需要等待全局锁的释放才可以。

接着是remove方法。该方法逻辑如下:首选根据key值计算出元素所对应主数组中的索引位置。然后依次循环主数组下该索引对应元素的后继元素。判断该元素的hash是否等于key参数的hash,以及元素是否equels参数key。如果相等,则将该元素从队列中抹除。同时hashtable的长度count 减1,同时modCount值也自加1。如果循环结束仍未找到合适的元素与参数key相等,则返回null

 

 1     public synchronized V remove(Object key) { 2         Entry<?,?> tab[] = table; 3         int hash = key.hashCode(); 4         int index = (hash & 0x7FFFFFFF) % tab.length; 5         @SuppressWarnings("unchecked") 6         Entry<K,V> e = (Entry<K,V>)tab[index]; 7         for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) { 8             if ((e.hash == hash) && e.key.equals(key)) { 9                 modCount++;10                 if (prev != null) {11                     prev.next = e.next;12                 } else {13                     tab[index] = e.next;14                 }15                 count--;16                 V oldValue = e.value;17                 e.value = null;18                 return oldValue;19             }20         }21         return null;22     }

接着是putAll方法,该方法会将map集合中的对象,采用foreach的形式,依次调用put方法添加到hashtable集合中。

    public synchronized void putAll(Map<? extends K, ? extends V> t) {        for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
            put(e.getKey(), e.getValue());
    }

接着是clear方法。该方法首先将modCount加1.接着循环主数组中的所有元素,然后依次对这些元素置于null。然后设定count元素为0。这里有一点需要注意,即clear时,只清理了主数组中的元素。对于主数组中对应元素的后继列表,则采用不予理会的态度。等待GC来回收掉。

1     public synchronized void clear() {2         Entry<?,?> tab[] = table;3         modCount++;4         for (int index = tab.length; --index >= 0; )5             tab[index] = null;6         count = 0;7     }

接着是clone方法。该方法会克隆一个自身对象的副本。此方法会克隆出一个空的hashtable。然后将主数组中的所有元素克隆一遍,放置到克隆对象的对应位置上。注意在克隆元素的时候,会将元素的后继队列元素,依次的克隆下去。接着初始化克隆对象的其他变量:置空keyset、entryset、values对象,设置modCount为0。

 1     public synchronized Object clone() { 2         try { 3             Hashtable<?,?> t = (Hashtable<?,?>)super.clone(); 4             t.table = new Entry<?,?>[table.length]; 5             for (int i = table.length ; i-- > 0 ; ) { 6                 t.table[i] = (table[i] != null) 7                     ? (Entry<?,?>) table[i].clone() : null; 8             } 9             t.keySet = null;10             t.entrySet = null;11             t.values = null;12             t.modCount = 0;13             return t;14         } catch (CloneNotSupportedException e) {15             // this shouldn't happen, since we are Cloneable16             throw new InternalError(e);17         }18     }

然后是重写的tostring方法。这个方法逻辑也很简单,就是依次遍历元素。最后生成一个类似于{“key1”=”value1”,“key2”=”value2”}的结构。有趣的是这里需要调用key.tostring,倘若key是当前hashtable自己的话,就直接使用“(this map)”字符串。防止出现无限递归。

 1     public synchronized String toString() { 2         int max = size() - 1; 3         if (max == -1) 4             return "{}"; 5  6         StringBuilder sb = new StringBuilder(); 7         Iterator<Map.Entry<K,V>> it = entrySet().iterator(); 8  9         sb.append('{');10         for (int i = 0; ; i++) {11             Map.Entry<K,V> e = it.next();12             K key = e.getKey();13             V value = e.getValue();14             sb.append(key   == this ? "(this Map)" : key.toString());15             sb.append('=');16             sb.append(value == this ? "(this Map)" : value.toString());17 18             if (i == max)19                 return sb.append('}').toString();20             sb.append(", ");21         }22     }

到这里hashtable的主要逻辑就已经都介绍完了。其余还包括一些keyset、valueSet的内部类、以及replaceAll、putIfAbsent等封装方法。由于代码逻辑简单,数量较大,这里就不一一列举了。

总结:

1、Hashtable包括tostirng等方法在,几乎所有对外api方法都是同步保护的,这就是为什么很多人认为hashtable线程安全的原因。而在基础上,对于同步方法所调用的private方法,则大多采用非同步的形式。因为这些方法,往往只有一个public方法可以调用,这样就做到了在安全的基础上可以更快执行代码。

2、hashtable的内部结构大致如下,和早前的hashmap很像:

3、关于元素的取值,hashtable不允许key和value取值为null。所以get时,发现为null,即说明key元素不存在。同时hashtable在扩容是采用的是乘2加1的方式。这与有些容器直接乘2有所区别。

4、关于变量modCount的使用。我们可以看到这个方法中,每次在发生增删改的时候都会出现modCount++的动作。而modcount可以理解为是当前hashtable的状态。每发生一次操作,状态就向前走一步。(防盗连接:本文首发自http://www.cnblogs.com/jilodream/ )设置这个状态,主要是由于hashtable等容器类在迭代时,判断数据是否过时时使用的。尽管hashtable采用了原生的同步锁来保护数据安全。但是在出现迭代数据的时候,则无法保证边迭代,边正确操作。于是使用这个值来标记状态。一旦在迭代的过程中状态发生了改变,则会快速抛出一个异常,终止迭代行为(所以这种错误也叫做快速失败fail—fast):

hashTable继承自dic类,同时实现了map接口和Cloneable、Serializable两个接口,代表该类是可复制、序列化的类。

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

ps:dic类和map类较为相似,是一个抽象的hash映射类,包含了一些简单的空方法和接口。

private transient Entry<?,?>[] table;

瞬时数组变量,它就是hashtable中,最核心的数据存储区域。

 

    /**
     * The total number of entries in the hash table.     */
    private transient int count;

数组长度,不知道大家发现没有,jdk非常喜欢用一个独立变量来表示容器中数据的大小,而不是每次返回核心数据的size或length。

 

阈值,这个之前专门强调过,这里简单说下,他是容积和负载因子的乘积,表示的含义是当前容器中,能表现出较好性能的数据量上限。超过这个上限时,容器的性能将会有比较大的下降。注意容积和阈值是有区别的。

threshold  ['θrhold]  n. 入口;门槛;开始;极限;临界值 

   private int threshold;

负载因子,是用来设定当前容器中,元素的填充率的。

你可以理解成容器是一个城市,这个城市中最佳入住率的一个上限是负载因子。这个城市的入住用户最佳的数目,就是他的阈值。

    /**
     * The load factor for the hashtable.
     *
     * @serial
     */
    private float loadFactor;

接下来是modCount ,这个变量的意义是,记录hashtable中,被修改的次数(包括增、删、改)三个操作的。而其用途呢,是未来被用作判定快速失败时(fail-fast)的依据数据。关于快速失败,这个我会在下边讲到。大家这里只要知道modCount这个变量的表示的含义是什么就可以。

    private transient int modCount = 0;

然后是版本序列号

    private static final long serialVersionUID = 1421746759512286392L;

接着是构造函数,参数分别为初始容积和负载因子。

函数内会首先判断初始容积和负载因子是否为正数。

接着如果初始容积为0,则赋予默认值1.也就是说,真实的容积至少都要为1。

接着对table赋予初始值,一个长度为初始容积大小的Entry数组。(防盗连接:本文首发自http://www.cnblogs.com/jilodream/ )接着计算

阈值=(初始容积和负载因子的乘积),(当前系统中最大的数组长度+1),二者的最小值。

也就是说阈值不能超过数组的最大长度+1。这里注意一个isNaN()方法,是个很有意思的方法,研究该方法的源码后,你会觉得很有意思。这个我会在以后的文章中讲到。

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)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    }

只要初始容积的构造函数,负载因子默认为0.75

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

无参的构造函数,初始容积使用为11,负载因子为0.75

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

不知道大家发现没,尽管提供了一个可能的,但是jdk的源码往往系统提供多个,应用于不同场景的接口,这些接口往往其实只是对自身其他接口的一个适配。但是对于调用者来说,这样却很舒服。

 

接着是最后一个构造函数,参数为一个map,map的k,v分别继承自hashTable中的K,V.

函数首先调用一遍通用的构造函数,负载因子为0.75。初始容积为map长度的两倍以及默认的11,二者的较大值。也就是说对于初始容积来说,最小都要取到11。

接着调用putAll方法,将map中的数据添加到HashTable中。

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

size()方法,方法采用同步机制,返回count变量。由于容器中并不是所有的元素都占满了数据,所以直接用变量返回值的速度和效率会更高点。同时由于count会随时变动,这里采用同步方法的形式进行线程保护。

    public synchronized int size() {        return count;
    }

isEmpyt,判断当前数组是否为空,与size()方法一致。

    public synchronized boolean isEmpty() {        return count == 0;
    }

keys,elements方法,分别返回返回hashTable中所有的key和value的枚举集合。

这里KEYS,VALUES为静态int常量。getEnumeration在下文中会提到。另外与前边的方法相同,这里也是对整个方法进行同步加锁。

    public synchronized Enumeration<K> keys() {        return this.<K>getEnumeration(KEYS);
    }    public synchronized Enumeration<V> elements() {        return this.<V>getEnumeration(VALUES);
    }

 接着是contains方法,方法意义不再赘述。

实现逻辑,首先判断value是否为null,如果为null则直接抛出空引用。

接着将table变量赋值给tab临时变量。然后循环tab,依次取出tab中的entry,以及entry的后继元素。(防盗连接:本文首发自http://www.cnblogs.com/jilodream/ )如果元素的value equals()判断等于参数value,则直接返回true。整个方法结束后,为发现,则会返回false。同时方法本身也是加同步锁进行线程安全保护。

    public synchronized boolean contains(Object value) {        if (value == null) {            throw new NullPointerException();
        }

        Entry<?,?> tab[] = table;        for (int i = tab.length ; i-- > 0 ;) {            for (Entry<?,?> e = tab[i] ; e != null ; e = e.next) {                if (e.value.equals(value)) {                    return true;
                }
            }
        }        return false;
    }

接着是实现map接口的抽象方法,只是对contains方法进行了一层封装。

    public boolean containsValue(Object value) {        return contains(value);
    }

接着是线程同步方法:containsKey,方法含义不赘述,逻辑如下:

设定临时变量并赋值table。取出key的hashCode。注意这里并没有判定key是否为null。

而前文中的value则是判定的。这是由于value是作为equals方法的参数的。即使是null也无法被发现,但是判定一个映射的value为null表示的真的为null还是没有映射到,这很歧义,所以干脆直接抛出异常。回到正文,根据hashCode计算出其在table数组中的索引。其实就是取低8位数字然后除以数组length取余数。(防盗连接:本文首发自http://www.cnblogs.com/jilodream/ )

接着依次循环table该索引的后继元素,判定是否equals()相等。如果有则返回true。如果始终没有找到,则返回false。

    public synchronized boolean containsKey(Object key) {
        Entry<?,?> tab[] = table;        int hash = key.hashCode();        int index = (hash & 0x7FFFFFFF) % tab.length;        for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {            if ((e.hash == hash) && e.key.equals(key)) {                return true;
            }
        }        return false;
    }

get()方法,与containsKey方法的逻辑是一致的。不同点是,在返回结果是,如果确实存在该key,则返回对应的value,否则返回null。

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

接着是前文提到的数组最大数字常亮。这里注意看参数的注释。部分虚拟机是设定数组的长度限制的。如果超出,可能会导致OOM异常

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

接着是rehash方法。这个方法是一个受保护方法。会在接下来的,hashtable添加元素的场景中被调用。他的作用呢,就是重新申请一块大小合适的内存。然后将键值元素重新安置到这块元素中。

那么就需要两个步骤。

1、计算新内存的大小。

2、计算元素在新table中的位置。

    先看代码:

 1     protected void rehash() { 2         int oldCapacity = table.length; 3         Entry<?,?>[] oldMap = table; 4  5         // overflow-conscious code 6         int newCapacity = (oldCapacity << 1) + 1; 7         if (newCapacity - MAX_ARRAY_SIZE > 0) { 8             if (oldCapacity == MAX_ARRAY_SIZE) 9                 // Keep running with MAX_ARRAY_SIZE buckets10                 return;11             newCapacity = MAX_ARRAY_SIZE;12         }13         Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];14 15         modCount++;16         threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);17         table = newMap;18 19         for (int i = oldCapacity ; i-- > 0 ;) {20             for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {21                 Entry<K,V> e = old;22                 old = old.next;23 24                 int index = (e.hash & 0x7FFFFFFF) % newCapacity;25                 e.next = (Entry<K,V>)newMap[index];26                 newMap[index] = e;27             }28         }29     }

代码中会首先获取旧table的长度oldCapacity 。然后oldCapacity 乘以2再加1.算出新table的长度newCapacity 。

接着判断newCapacity 是否超出了hashtable所能设定的最大值:MAX_ARRAY_SIZE。如果超出,则判断oldCapacity 是否已经等于最大值。如果已经等于,则认定,当前hashtable的长度已经到达所允许的上限。无法再继续扩容。则直接返回。

否则将MAX_ARRAY_SIZE赋值给newCapacity 。作为新的长度。也就是说rehash在大小允许的情况下,一般会翻倍扩容。但是如果翻倍后长度超出上限,则以上限大小作为扩容后新的大小。

接着以newCapacity 作为长度,new出一个Entry数组,作为新的table元素存放容器。

modCount自加1。

接着计算阈值:newCapacity 乘以负载因子和MAX_ARRAY_SIZE+1 取较小值。注意这里负载因子是可以大于1的。因此newCapacity 乘以负载因子,式可以大于MAX_ARRAY_SIZE的。

接着就是计算旧有table中的键值元素在新table中的位置了:这里使用的是双层循环,外层依次遍历Entry主数组上的元素。如果entry[i]不等于null值,则将该元素及其后继元素依次计算出新的位置,然后插入到主数组上的对应位置。同时将主数组中原来位置的元素。作为新放置元素的后继。也就是每个新元素,插在每个对应位置的链表最前侧。至于为什么不放在这个对应链表的最后位置。其实很简单,因为这是一个链式存储结构,需要依次遍历每个元素,才能找到队尾的元素。

接着是添加元素的私有方法addEntry。(防盗连接:本文首发自http://www.cnblogs.com/jilodream/ )

首先是modCount自加1.

接着如果当前table的数量已经超过了阈值,那么就进行一次rehash,接着根据key的hashCode计算出当前键值对的输入索引。接着取出table对应索引位置的元素一同做出一个新的Entry元素放在这个对应索引的位置上。(这里要注意后续的entry 的构造方法)同时count数目自加1。这里需要注意的是,当前数目如果已经超过阈值,前边讲到的rehash是不一定会重新做出新数组的(length超过了MAX_ARRAY_SIZE的限制时)很多人在理解这里的时候,就认定只要count超过阈值就一定会重新分配table内存的地址,这个理解是存在问题的。

 1     private void addEntry(int hash, K key, V value, int index) { 2         modCount++; 3  4         Entry<?,?> tab[] = table; 5         if (count >= threshold) { 6             // Rehash the table if the threshold is exceeded 7             rehash(); 8  9             tab = table;10             hash = key.hashCode();11             index = (hash & 0x7FFFFFFF) % tab.length;12         }13 14         // Creates the new entry.15         @SuppressWarnings("unchecked")16         Entry<K,V> e = (Entry<K,V>) tab[index];17         tab[index] = new Entry<>(hash, key, value, e);18         count++;19     }

接着是put方法。这个方法是hashtable非常常用的一个public方法。方法本身是一个同方法。在方法中对于参数value和key有逻辑:如果为null时,均会报出空引用异常。

 1     public synchronized V put(K key, V value) { 2         // Make sure the value is not null 3         if (value == null) { 4             throw new NullPointerException(); 5         } 6  7         // Makes sure the key is not already in the hashtable. 8         Entry<?,?> tab[] = table; 9         int hash = key.hashCode();10         int index = (hash & 0x7FFFFFFF) % tab.length;11         @SuppressWarnings("unchecked")12         Entry<K,V> entry = (Entry<K,V>)tab[index];13         for(; entry != null ; entry = entry.next) {14             if ((entry.hash == hash) && entry.key.equals(key)) {15                 V old = entry.value;16                 entry.value = value;17                 return old;18             }19         }20 21         addEntry(hash, key, value, index);22         return null;23     }

接着算出key所应该对应的主数组的索引。循环遍历出该数组元素所对应的队列(tab[index]),如果元素的hash值等于新添加元素的hash,同时entry的key等于(equals)key方法。则直接替换这个entry的value为参数传入的value,与此同时返回旧old。

如果整个循环都发现没有,则说明当前hashtable其实并不存在该参数key,则调用刚才说的addEntry方法,将参数key value,及对应的索引传进去。这里注意put方法为同步公有方法,而addEntry为私有非同步方法,这里是否存在线程安全问题呢?(防盗连接:本文首发自http://www.cnblogs.com/jilodream/ )其实并不存在,这是由于addEntry尽管会操作全局变量主数组,但是addEntry方法只会被put方法调用。而凡是调用put方法的线程均需要先拿到this变量锁。尽管再次进去无同步的addEntry的方法区,当前线程仍然持有this变量锁,其他线程若想操作全局变量主数组,仍然需要等待全局锁的释放才可以。

接着是remove方法。该方法逻辑如下:首选根据key值计算出元素所对应主数组中的索引位置。然后依次循环主数组下该索引对应元素的后继元素。判断该元素的hash是否等于key参数的hash,以及元素是否equels参数key。如果相等,则将该元素从队列中抹除。同时hashtable的长度count 减1,同时modCount值也自加1。如果循环结束仍未找到合适的元素与参数key相等,则返回null

 

 1     public synchronized V remove(Object key) { 2         Entry<?,?> tab[] = table; 3         int hash = key.hashCode(); 4         int index = (hash & 0x7FFFFFFF) % tab.length; 5         @SuppressWarnings("unchecked") 6         Entry<K,V> e = (Entry<K,V>)tab[index]; 7         for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) { 8             if ((e.hash == hash) && e.key.equals(key)) { 9                 modCount++;10                 if (prev != null) {11                     prev.next = e.next;12                 } else {13                     tab[index] = e.next;14                 }15                 count--;16                 V oldValue = e.value;17                 e.value = null;18                 return oldValue;19             }20         }21         return null;22     }

接着是putAll方法,该方法会将map集合中的对象,采用foreach的形式,依次调用put方法添加到hashtable集合中。

    public synchronized void putAll(Map<? extends K, ? extends V> t) {        for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
            put(e.getKey(), e.getValue());
    }

接着是clear方法。该方法首先将modCount加1.接着循环主数组中的所有元素,然后依次对这些元素置于null。然后设定count元素为0。这里有一点需要注意,即clear时,只清理了主数组中的元素。对于主数组中对应元素的后继列表,则采用不予理会的态度。等待GC来回收掉。

1     public synchronized void clear() {2         Entry<?,?> tab[] = table;3         modCount++;4         for (int index = tab.length; --index >= 0; )5             tab[index] = null;6         count = 0;7     }

接着是clone方法。该方法会克隆一个自身对象的副本。此方法会克隆出一个空的hashtable。然后将主数组中的所有元素克隆一遍,放置到克隆对象的对应位置上。注意在克隆元素的时候,会将元素的后继队列元素,依次的克隆下去。接着初始化克隆对象的其他变量:置空keyset、entryset、values对象,设置modCount为0。

 1     public synchronized Object clone() { 2         try { 3             Hashtable<?,?> t = (Hashtable<?,?>)super.clone(); 4             t.table = new Entry<?,?>[table.length]; 5             for (int i = table.length ; i-- > 0 ; ) { 6                 t.table[i] = (table[i] != null) 7                     ? (Entry<?,?>) table[i].clone() : null; 8             } 9             t.keySet = null;10             t.entrySet = null;11             t.values = null;12             t.modCount = 0;13             return t;14         } catch (CloneNotSupportedException e) {15             // this shouldn't happen, since we are Cloneable16             throw new InternalError(e);17         }18     }

然后是重写的tostring方法。这个方法逻辑也很简单,就是依次遍历元素。最后生成一个类似于{“key1”=”value1”,“key2”=”value2”}的结构。有趣的是这里需要调用key.tostring,倘若key是当前hashtable自己的话,就直接使用“(this map)”字符串。防止出现无限递归。

 1     public synchronized String toString() { 2         int max = size() - 1; 3         if (max == -1) 4             return "{}"; 5  6         StringBuilder sb = new StringBuilder(); 7         Iterator<Map.Entry<K,V>> it = entrySet().iterator(); 8  9         sb.append('{');10         for (int i = 0; ; i++) {11             Map.Entry<K,V> e = it.next();12             K key = e.getKey();13             V value = e.getValue();14             sb.append(key   == this ? "(this Map)" : key.toString());15             sb.append('=');16             sb.append(value == this ? "(this Map)" : value.toString());17 18             if (i == max)19                 return sb.append('}').toString();20             sb.append(", ");21         }22     }

到这里hashtable的主要逻辑就已经都介绍完了。其余还包括一些keyset、valueSet的内部类、以及replaceAll、putIfAbsent等封装方法。由于代码逻辑简单,数量较大,这里就不一一列举了。

总结:

1、Hashtable包括tostirng等方法在,几乎所有对外api方法都是同步保护的,这就是为什么很多人认为hashtable线程安全的原因。而在基础上,对于同步方法所调用的private方法,则大多采用非同步的形式。因为这些方法,往往只有一个public方法可以调用,这样就做到了在安全的基础上可以更快执行代码。

2、hashtable的内部结构大致如下,和早前的hashmap很像:

3、关于元素的取值,hashtable不允许key和value取值为null。所以get时,发现为null,即说明key元素不存在。同时hashtable在扩容是采用的是乘2加1的方式。这与有些容器直接乘2有所区别。

4、关于变量modCount的使用。我们可以看到这个方法中,每次在发生增删改的时候都会出现modCount++的动作。而modcount可以理解为是当前hashtable的状态。每发生一次操作,状态就向前走一步。(防盗连接:本文首发自http://www.cnblogs.com/jilodream/ )设置这个状态,主要是由于hashtable等容器类在迭代时,判断数据是否过时时使用的。尽管hashtable采用了原生的同步锁来保护数据安全。但是在出现迭代数据的时候,则无法保证边迭代,边正确操作。于是使用这个值来标记状态。一旦在迭代的过程中状态发生了改变,则会快速抛出一个异常,终止迭代行为(所以这种错误也叫做快速失败fail—fast):

本文转自  zddnd   51CTO博客,原文链接:http://blog.51cto.com/13013666/1949239

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【Java原理探索】「ConcurrentHashMap」深入浅出的源码分析(JDK1.7版本)
【Java原理探索】「ConcurrentHashMap」深入浅出的源码分析(JDK1.7版本)
0 0
【Java原理探索】「ConcurrentHashMap」深入浅出的源码分析(JDK1.8版本)
【Java原理探索】「ConcurrentHashMap」深入浅出的源码分析(JDK1.8版本)
0 0
jdk太神奇了 (StandardCharsets 源码)
jdk太神奇了 我们不再需要自行定义字符集常量。 直接调用java.nio.charset包下的 StandardCharsets 类,指定对应的字符集即可。 以前发现了apache的FileUtils包里面有几个这样的常量,还沾沾自喜, 现在才发现jdk已经为我们提供了这些字符编码的静态常量,不得不说jdk太神奇了
0 0
2022 最新 JDK 17 HashMap 源码解读 (一)
2022 最新 JDK 17 HashMap 源码解读 (一)
0 0
【JUC】JDK1.8源码分析之ConcurrentSkipListMap(二)
 最近在做项目的同时也在修复之前项目的一些Bug,所以忙得没有时间看源代码,今天都完成得差不多了,所以又开始源码分析之路,也着笔记录下ConcurrentSkipListMap的源码的分析过程。
0 0
【JUC】JDK1.8源码分析之CopyOnWriteArraySet(七)
分析完了CopyOnWriteArrayList后,下面接着分析CopyOnWriteArraySet,CopyOnWriteArraySet与CopyOnWriteArrayList有莫大的联系,因为CopyOnWriteArraySet的底层是由CopyOnWriteArrayList提供支持,并且将对其的操作转发至对CopyOnWriteArrayList的操作。但是,CopyOnWriteArraySet的元素不允许重复,这是和CopyOnWriteArrayList不相同的地方,下面开始分析。
0 0
浩哥带你学习JDK1.1源码——第2天
JDK1.1源码阅读第二天,带你阅读源码文档那些事和源码的结构。
0 0
浩哥带你学习JDK1.1源码——第1天
1996年1月,第一个JDK1.0诞生,从此Java开疆拓土,终成一个参与、制定新世界不可分割的伟大帝国。而远在1990年代初它的名字叫Oak,本想在电视机、电话、闹钟、烤面包机等家用电器的智能控制上大展拳手(这就是为啥Java支持跨平台了),但由于当时的市场需求没有预期的高,Sun公司于是就放弃了该计划。1992年 Joe Palrang创作出来了Java的吉祥物:Duke。随着互联网的发展,1995年5月 Oak正式改名为Java(看来起个好名字真的很重要),混的那叫一个风生水起。这一切还得靠1994年6月詹姆斯·高斯林等人的头脑风暴将技术应用于新兴的万维网的决定。
0 0
JDK11 | 第一篇 : JDK11 介绍
Java11 是 Java 大版本周期变化后的第一个长期支持版本,非常值得关注。从官网即可下载, 最新发布的 Java11 将带来 ZGC、Http Client 等重要特性。
1740 0
22.源码阅读(jdk1.6 HashMap源码和原理分析)
HashMap 底层采用数组 + 链表的的实现方式来降低数据插入和查询的时间复杂度,理想状态下可以实现时间复杂度位O(1),今天就从源码的角度看一下它是如何实现的。
631 0
文章
问答
文章排行榜
最热
最新
相关电子书
更多
《Java开发手册》2019最新版发布!
立即下载
《阿里巴巴Java开发手册》1.3.0版本【非最新版】
立即下载
JDK8新特性与生产
立即下载