HashMap和Hashtable之源代码详解.docVIP

HashMap和Hashtable 之源代码详解 ? HashtableJDK1.0就已经有了, 所以让我们先来看看它是怎么工作, 然后有浅入深, 来研究HashMap的原理, 以及两者的不同点. ? Hashtable有几个主要的字段, 如下, ? ??? /**???? * The hash table data.???? */??? private transient Entry[] table;??? /**???? * The total number of entries in the hash table.???? */??? private transient int count;??? /**???? * The table is rehashed when its size exceeds this threshold.?(The???? * value of this field is (int)(capacity * loadFactor).)???? *???? * @serial???? */??? private int threshold; ? 其中最重要的就是那个table数组了. 它就是整个hashtable的基本数据结构! 在来看一下这个字段 private transient Entry[] table; ? , hashtable的基本数据结构就是, 一个包涵Entry类的二维数组. 而这个Entry类是hashtable的内在类, 它其实是一个单向链, 让我们详细分析一下. ? ? ?? private static class EntryK,V implements Map.EntryK,V {??????????? int hash;??????????? K key;??????????? V value;??????????? EntryK,V next;... ... ? 看到这里有没有想到学校里教的数据结构原理这门课呢? Entry类就是定义了一个很简单的单向链结构, 它里面包括key, value和下个Entry类的对象next. 在这里我在强调一下,?hashtable的数据结构就是一个包涵单向链的二维数组. ? ? ? ? 接下来让我们来看看hashtable的构造器是长的什么样的. ? 最长用的 ? ??? 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;??????????? this.loadFactor = loadFactor;????????????table = new Entry[initialCapacity];??????????? threshold = (int)(initialCapacity * loadFactor);??? } ? 细读代码后, 我们发现这个构造器构造了table字段和threshold. Table前面已经详细讲了, 那么这个threshold又是什么东东呢? 其实这个threshold对hashtalbe的性能影响是很大的! 因为table是个数组, 如果在hashtable中保存的实体大于一定的数量后, 对数据的读写就会有很慢, 那是因为, 很多数据都保存在entry类的单向链中, 每次读写都要比对链中所有的数据, 链越长读写就越慢. 所以当数据容量大于threshold的时候, hashtable就会做rehash(),?rehash把table的容量扩大一倍, 再把从前在table里的数据统统搬回新的table. 这样的一个过程, 开销是多