本文共 16014 字，大约阅读时间需要 53 分钟。
首先给出关于此类的一些概括性的知识点：
1.这个类实现了一个哈希表，在这个哈希表中将键与值形成映射关系；任何非null对象都可以用来作为一个键或值；
2.为了成功地从一个哈希表中存储和检索对象，哈希表中被用来作为键的对象必须实现hashCode和equals方法；
3.影响Hashtable性能的两个参数：初始化容量（initial capacity）和装载因子（load factor）；
3.1.容量指的是哈希表中桶的数目，初始容量就是在创建Hashtable时的容量；
注意：Hashtable采用开放地址法来处理哈希冲突；即在“哈希冲突”的情况下，单个桶存储多个条目（以链表的形式存放），对于这种情况下的桶必须按顺序查找指定的值。
3.2.装载因子是在Hashtable容量自动增加之前，用来衡量Hashtable存储饱和度的标准。
3.3.初始容量和装载因子仅仅是实现的提示.何时调用哈希重构方法的具体细节是依赖于实现的；
4.一般来说,默认的负载因子0.75，该值在时间和空间消耗上提供了一个很好的折中;
虽然该值的增大,减小了空间开销;但是,增加了查找一个条目的时间,在Hashtable的大多数操作中都存在着查找条目,包括添加和获取条目;
5.初始容量用来调节空间浪费与rehash操作需求之间的平衡;这些rehash操作是耗费时间的;如果初始容量大于哈希表中存放的最大条目数量和装载因子的商，rehash操作将不会执行；但是,设置过大的初始容量会导致空间的浪费;
6.如果有许多条目将要被放入哈希表中，相比让哈希表自动增加表的容量，则在创建哈希表的时候采用一个足够大的容量，将会使得插入条目会更加地有效；
7.使用示例:
Hashtable numbers = new Hashtable (); numbers.put("one", 1); numbers.put("two", 2); numbers.put("three", 3); Integer n = numbers.get("two"); if (n != null) { System.out.println("two = " + n); }
8.在JDK 2.0中，这个类被调整从而实现了Map接口，使得这个类成为了Java集合框架中的一员；Hashtable是同步的;
如果不需要一个线程安全的实现,推荐使用HashMap来代替Hashtable;如果需要一个线程安全并且适应高并发的实现,推荐使用java.util.concurrent下的ConcurrentHashMap代替Hashtable;
public class Hashtable extends Dictionary implements Map , Cloneable, java.io.Serializable { private transient Entry [] table; //哈希表的底层数据结构为Entry类型的数组 private transient int count;//哈希表中已有的条目数量 private int threshold;//当哈希表中的条目数目超过这个threshold值，哈希表将会进行rehash；其中，threshold=capacity * loadFactor private float loadFactor; //哈希表的负载因子 //结构上的调整是指那些改变哈希表中条目数量的操作或者调整哈希表内部结构（如rehash） //modCount被应用到集合视图的迭代器中的快速失败的实现中； private transient int modCount = 0;//modCount用来记录哈希表结构上调整的次数； /** use serialVersionUID from JDK 1.0.2 for interoperability */ private static final long serialVersionUID = 1421746759512286392L;
哈希表的构造器
①含参构造器（两个参数） //构建一个指定初始容量、指定装载因子的新的、空的哈希表 * @param initialCapacity 哈希表的初始容量. * @param loadFactor 哈希表的装载因子. * @exception 如果初始容量小于0 或 装载因子非正数，将会抛出IllegalArgumentException. 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);//调用第一个构造器 } //构建一个与给定Map相同映射的新的哈希表，新的哈希表的初始容量应该足够存放指定Map中所有的映射； //负载因子为默认值（0.75） public Hashtable(Map t) { this(Math.max(2*t.size(), 11), 0.75f);//调用第一个构造器 putAll(t);//将Map中的所有条目放入新建的哈希表中 } 使用synchronized关键字，进行方法的同步
//返回哈希表中键值对的数目（此方法加上synchronized关键字，为同步方法） public synchronized int size() { return count; } //判断当前哈希表中是否没有键值对（同步方法） public synchronized boolean isEmpty() { return count == 0; } //返回一个哈希表中键的枚举（同步方法） public synchronized Enumeration keys() { return this. getEnumeration(KEYS); } //返回一个哈希表中值的枚举（同步方法） public synchronized Enumeration elements() { return this. getEnumeration(VALUES); }Comparison and hashing（比较和哈希操作）=============================== //比较当前map对象是否与指定对象相等，按照Map接口中定义的那样 public synchronized boolean equals(Object o) { if (o == this) return true; if (!(o instanceof Map)) return false; Map t = (Map ) o; if (t.size() != size()) return false; try { Iterator > i = entrySet().iterator(); while (i.hasNext()) { Map.Entry e = i.next(); K key = e.getKey(); V value = e.getValue(); if (value == null) { if (!(t.get(key)==null && t.containsKey(key))) return false; } else { if (!value.equals(t.get(key))) return false; } } } catch (ClassCastException unused) { return false; } catch (NullPointerException unused) { return false; } return true; } //返回当前Map对象的哈希值，按照Map接口中定义的那样 public synchronized int hashCode() { /* * This code detects the recursion caused by computing the hash code * of a self-referential hash table and prevents the stack overflow * that would otherwise result. This allows certain 1.1-era * applets with self-referential hash tables to work. This code * abuses the loadFactor field to do double-duty as a hashCode * in progress flag, so as not to worsen the space performance. * A negative load factor indicates that hash code computation is * in progress. */ int h = 0; if (count == 0 || loadFactor < 0) return h; // Returns zero loadFactor = -loadFactor; // Mark hashCode computation in progress Entry [] tab = table; for (Entry entry : tab) { while (entry != null) { h += entry.hashCode(); entry = entry.next; } } loadFactor = -loadFactor; // Mark hashCode computation complete return h; } contains方法
哈希表的查询方法是需要着重理解的地方！可以看到contains方法是通过遍历哈希表的底层数组中的元素来确定是否存在给定的值；哈希表的底层数组中的数组元素是在本类中定义的私有内部类Entry ，该类实现了java.util.Map接口中定义的子接口Entry ，通过实现已有的接口并添加自己所需的实例字段，设计符合应用情境的类；通过分析该类的数据域，可以得知，每一个私有内部类Entry 的对象拥有一个指向下一个Entry 的对象的引用，因此，可以得知，哈希表的底层数组中存放的是元素是一个链表的头结点；那么也就不难理解下面的for循环中的执行过程以及作用了！
//判断哈希表中有没有键映射到给定的值，此方法比containsKey方法开销大； //注意，此方法与集合框架中的Map接口中的containsValue方法具有相同的功能（同步方法） 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) {//使用equals方法进行相等的判断 if (e.value.equals(value)) { return true; } } } return false; } //私有内部类，为了解决哈希冲突而设计的链表节点类 /** * Hashtable bucket collision list entry */ private static class Entry implements Map.Entry { final int hash; final K key; V value; Entry next; protected Entry(int hash, K key, V value, Entry next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } @SuppressWarnings("unchecked") protected Object clone() { return new Entry<>(hash, key, value, (next==null ? null : (Entry ) next.clone())); } // Map.Entry Ops public K getKey() { return key; } public V getValue() { return value; } public V setValue(V value) { if (value == null) throw new NullPointerException(); V oldValue = this.value; this.value = value; return oldValue; } public boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry )o; return (key==null ? e.getKey()==null : key.equals(e.getKey())) && (value==null ? e.getValue()==null : value.equals(e.getValue())); } public int hashCode() { return hash ^ Objects.hashCode(value); } public String toString() { return key.toString()+"="+value.toString(); } } //如果此哈希表中存在一个或多个键映射到指定参数对应的值，则返回true；（同步方法） //注意，此方法早于Map接口中的contains方法 public boolean containsValue(Object value) { return contains(value);//调用上面的同步方法contains(Object value)，因此此方法为同步方法 } ``` containsKey方法也值得研究，因为该方法中，涉及到了哈希表中如何确定一个键的位置的实现细节！先利用Object类中的hashCode方法求出哈希值，再将该哈希值进行(hash & 0x7FFFFFFF) % tab.length的处理，得到该键在数组中的对应索引！接着就是，进行for循环确定对应索引处的链表中是否存在以给定参数作为键的键值对。 //如果所给参数是哈希表中的一个键，则返回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) { //采用equals方法进行相等的比较，如果对应索引处的链表中存在满足键值对的哈希值（键值对中键的哈希值为整个键值对的哈希值）等于给定参数key的哈希值并且该键值对的键与给定参数可以相等，那么该参数对应的键存在于当前的哈希表中 if ((e.hash == hash) && e.key.equals(key)) { return true; } } return false;}//返回指定键映射的值，如果存在，返回对应的值；否则，返回false；（同步方法）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;} rehash操作======下面是哈希表中实现中，相当重要的一个操作rehash；为了更加有效地容纳和存取其中的条目，使用rehash操作增加当前哈希表的容量并且进行内部重新组织；当哈希表中键的数量超过了哈希表的容量，这一方法将会被自动调用；
//可以分配的数组长度最大值private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;protected void rehash() { int oldCapacity = table.length;//保留rehash之前的底层数组的长度 Entry [] oldMap = table;//保留原有的底层数组的引用 // overflow-conscious code，下面的if语句块对新容量进行自动调整，判断是否需要更换数组，以及更换数组后的新数组最合适的长度 int newCapacity = (oldCapacity << 1) + 1;//一开始将新容量设置旧容量的两倍再加1 if (newCapacity - MAX_ARRAY_SIZE > 0) { //如果新容量大于规定的最大的数组长度，且原来的数组长度为最大的数组长度，就不能再扩大数组的长度，只能使用原来的数组， //因此直接返回，不对底层数组进行替换 if (oldCapacity == MAX_ARRAY_SIZE) // Keep running with MAX_ARRAY_SIZE buckets return; newCapacity = MAX_ARRAY_SIZE;//如果新容量大于规定的最大的数组长度，而原来的数组长度小于最大的数组长度，则将新容量设为允许的最大值 } //按照此时的新容量进行创建新的数组，并将原来的底层数组中的键值对，按照新数组的长度重新进行索引位置的计算并在新的索引位置存放键值对 Entry [] newMap = new Entry [newCapacity]; modCount++;//rehash操作次数加1 threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);//更新threshold table = newMap;//更新底层的数组变量指向新的地址 //进行键值对的拷贝（这里需要注意新数组的长度与原来的数组长度不同，因此需要重新计算索引位置） for (int i = oldCapacity ; i-- > 0 ;) { //下面的for循环用于将当前索引处的链表中的元素一次取出，进行重新定位，插入 for (Entry old = (Entry )oldMap[i] ; old != null ; ) { Entry e = old; old = old.next; int index = (e.hash & 0x7FFFFFFF) % newCapacity; e.next = (Entry )newMap[index];//此时newMap[index]为null，因此，这里的操作是将e从原来的链表中分割出来 newMap[index] = e;//再将e放入索引位置处 } }} 添加条目方法（新加入的条目称为对应对应索引处的链表的头结点）------------------------------
private void addEntry(int hash, K key, V value, int index) { modCount++;//插入条目会导致结构上的改变，所以将modCount加一 Entry tab[] = table; //判断是否需要进行rehash if (count >= threshold) { rehash(); // Rehash the table if the threshold is exceeded tab = table; hash = key.hashCode(); index = (hash & 0x7FFFFFFF) % tab.length; } // Creates the new entry. @SuppressWarnings("unchecked") Entry e = (Entry ) tab[index]; tab[index] = new Entry<>(hash, key, value, e); count++;} ``` //将指定的值映射到指定的键上，键和值都不可以为空 * @param key the hashtable key * @param value the value * @return 返回哈希表中指定键对应的旧值，如果没有的话，返回null * @exception NullPointerException if the key or value is null public synchronized V put(K key, V value) { // Make sure the value is not null if (value == null) { throw new NullPointerException(); } // Makes sure the key is not already in the hashtable. Entry tab[] = table; int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length;//散列函数 @SuppressWarnings("unchecked") Entry entry = (Entry )tab[index]; //检查链表中是否已存在key对应的键值对，如果已存在，则将原来的值返回，并将value设为键值对的新值 for(; entry != null ; entry = entry.next) { if ((entry.hash == hash) && entry.key.equals(key)) { V old = entry.value; entry.value = value; return old; } } addEntry(hash, key, value, index);//如果没有，就将此条目插入链表头部，使之成为新的链表头结点 return null; } //从这个哈希表中移除键和其对应的值；如果该键不在哈希表中，此方法将不作为 * @param key the key that needs to be removed * @return the value to which the key had been mapped in this hashtable, or null if the key did not have a mapping * @throws NullPointerException if the key is null public synchronized V remove(Object key) { Entry tab[] = table; int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; @SuppressWarnings("unchecked") Entry e = (Entry )tab[index]; for(Entry prev = null ; e != null ; prev = e, e = e.next) { if ((e.hash == hash) && e.key.equals(key)) { modCount++; if (prev != null) { prev.next = e.next; } else { tab[index] = e.next; } count--; V oldValue = e.value; e.value = null; return oldValue; } } return null; } //拷贝指定的Map对象中的所有映射到当前的哈希表中，本方法将会把当前哈希表中的映射替换为指定参数中的映射 * @param t mappings to be stored in this map * @throws NullPointerException if the specified map is null * @since 1.2 public synchronized void putAll(Map t) { for (Map.Entry e : t.entrySet()) put(e.getKey(), e.getValue()); } //清空哈希表，使得当前哈希表中不含有任何键 public synchronized void clear() { Entry tab[] = table; modCount++;//本方法属于会改变哈希表结构的方法 for (int index = tab.length; --index >= 0; ) tab[index] = null;//帮助虚拟机进行GC count = 0; } /** * Creates a shallow copy of this hashtable. All the structure of the * hashtable itself is copied, but the keys and values are not cloned. * This is a relatively expensive operation * @return a clone of the hashtable */ //对当前哈希表进行浅拷贝。哈希表自身的结构被拷贝，但是键和值没有被拷贝；这个操作开销很大 public synchronized Object clone() { try { Hashtable t = (Hashtable )super.clone(); t.table = new Entry [table.length]; for (int i = table.length ; i-- > 0 ; ) { t.table[i] = (table[i] != null) ? (Entry ) table[i].clone() : null; } t.keySet = null; t.entrySet = null; t.values = null; t.modCount = 0; return t; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(e); } } //返回当前哈希表对象的一个字符串表达式，该字符串以括号包含起来的一个条目集合的形式， //元素之间采用空格分开，键与值之间以等号连接 public synchronized String toString() { int max = size() - 1; if (max == -1) return "{}"; StringBuilder sb = new StringBuilder(); Iterator > it = entrySet().iterator(); sb.append('{'); for (int i = 0; ; i++) { Map.Entry e = it.next(); K key = e.getKey(); V value = e.getValue(); sb.append(key == this ? "(this Map)" : key.toString()); sb.append('='); sb.append(value == this ? "(this Map)" : value.toString()); if (i == max) return sb.append('}').toString(); sb.append(", "); } }
转载地址：http://rtsvb.baihongyu.com/