HashTable的故事
很早之前，在讲HashMap的时候，我们就说过hash是散列，把...弄碎的意思。hashtable中的hash也是这个意思，而table呢，是指数据表格，也就是说hashtable的本意是指，一份被数据被打散，分散在各处的数据表格。
HashTable，作为jdk中，极早提供的容器类（jdk1.0），同时是支持数据并发的类，其在项目中的使用却并不是很广泛。在我所经历的项目中，开发人员往往喜欢使用hashMap然后再通过锁，创造出线程安全的环境。即使是后来推出concurrentHashMap，其使用的地方也并没有特别广泛。究其原因，我觉得是由于开发人员对于其他hash容器并不熟悉。更愿意使用已有的较为熟悉的hash容器，即使他们在此处的应用比较费事。
好了，废话不多说，我们直接开始进入正题吧：
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 ['θr??hold] 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 }如果你觉得写的不错，欢迎转载和点赞。转载时请保留作者署名jilodream/王若伊_恩赐解脱（博客链接：http://www.cnblogs.com/jilodream/）Deep Think
http://www.cnblogs.com/jilodream/p/7209021.html
延伸阅读
- 我学IT的故事 2021-05-19 11:07:14.443
- [Android FrameWork 6.0源码学习] View的重绘过程之Measure 2017-07-26 16:27:03.317
- ReactiveSwift源码解析(九) SignalProducerProtocol延展中的Start、Lift系列方法的代码实现 2017-07-26 12:00:35.793
- ABP从入门到精通（1）：aspnet-zero-core项目启动及各项目源码说明 2017-07-26 11:59:44.78
- 跟我一起读postgresql源码(六)——Executor(查询执行模块之——查询执行策略) 2017-07-25 17:08:59.397
- HashMap源码分析 2017-07-25 16:46:11.977
- 总结两种动态代理jdk代理和cglib代理 2017-07-25 16:15:50.13
- 【Storm】Storm实战之频繁二项集挖掘（附源码） 2017-07-25 16:08:35.043
- 3.PO如何给开发团队讲好故事 2017-07-24 16:27:33.117
- 读Zepto源码之属性操作 2017-07-21 16:34:59.87
我学IT的故事