Java源码解读之HashTable

深藏阁楼爱情的钟 2022-11-02 00:59 217阅读 0赞

### Java源码解读之HashTable ###

*   *  1.1 前言
     *  1.2 源码解读
     *   *  1.2.1 HashTable 源码原文注释
         *  1.2.2 HashTable 源码注释原文解读

## 1.1 前言 ##

这篇博文一起来探究学习下HashTable源码。

## 1.2 源码解读 ##

### 1.2.1 HashTable 源码原文注释 ###

`HashTable.java` 源码 位于`rt.jar` 中的`java.utils` 包里。

/** * This class implements a hash table, which maps keys to values. Any * non-<code>null</code> object can be used as a key or as a value. * * To successfully store and retrieve objects from a hashtable, the * objects used as keys must implement the <code>hashCode</code> * method and the <code>equals</code> method. * * An instance of <code>Hashtable</code> has two parameters that affect its * performance: initial capacity and load factor. The * capacity is the number of buckets in the hash table, and the * initial capacity is simply the capacity at the time the hash table * is created. Note that the hash table is open: in the case of a "hash * collision", a single bucket stores multiple entries, which must be searched * sequentially. The load factor is a measure of how full the hash * table is allowed to get before its capacity is automatically increased. * The initial capacity and load factor parameters are merely hints to * the implementation. The exact details as to when and whether the rehash * method is invoked are implementation-dependent. * * Generally, the default load factor (.75) offers a good tradeoff between * time and space costs. Higher values decrease the space overhead but * increase the time cost to look up an entry (which is reflected in most * <tt>Hashtable</tt> operations, including <tt>get</tt> and <tt>put</tt>). * * The initial capacity controls a tradeoff between wasted space and the * need for <code>rehash</code> operations, which are time-consuming. * No <code>rehash</code> operations will ever occur if the initial * capacity is greater than the maximum number of entries the * <tt>Hashtable</tt> will contain divided by its load factor. However, * setting the initial capacity too high can waste space. * * If many entries are to be made into a <code>Hashtable</code>, * creating it with a sufficiently large capacity may allow the * entries to be inserted more efficiently than letting it perform * automatic rehashing as needed to grow the table. * * This example creates a hashtable of numbers. It uses the names of * the numbers as keys: * <pre> {@code * Hashtable<String, Integer> numbers * = new Hashtable<String, Integer>(); * numbers.put("one", 1); * numbers.put("two", 2); * numbers.put("three", 3);}</pre> * * To retrieve a number, use the following code: * <pre> {@code * Integer n = numbers.get("two"); * if (n != null) { * System.out.println("two = " + n); * }}</pre> * * The iterators returned by the <tt>iterator</tt> method of the collections * returned by all of this class's "collection view methods" are * fail-fast: if the Hashtable is structurally modified at any time * after the iterator is created, in any way except through the iterator's own * <tt>remove</tt> method, the iterator will throw a {@link * ConcurrentModificationException}. Thus, in the face of concurrent * modification, the iterator fails quickly and cleanly, rather than risking * arbitrary, non-deterministic behavior at an undetermined time in the future. * The Enumerations returned by Hashtable's keys and elements methods are * not fail-fast. * * Note that the fail-fast behavior of an iterator cannot be guaranteed * as it is, generally speaking, impossible to make any hard guarantees in the * presence of unsynchronized concurrent modification. Fail-fast iterators * throw <tt>ConcurrentModificationException</tt> on a best-effort basis. * Therefore, it would be wrong to write a program that depended on this * exception for its correctness: the fail-fast behavior of iterators * should be used only to detect bugs. * * As of the Java 2 platform v1.2, this class was retrofitted to * implement the {@link Map} interface, making it a member of the * <a href="{@docRoot}/../technotes/guides/collections/index.html"> * * Java Collections Framework</a>. Unlike the new collection * implementations, {@code Hashtable} is synchronized. If a * thread-safe implementation is not needed, it is recommended to use * {@link HashMap} in place of {@code Hashtable}. If a thread-safe * highly-concurrent implementation is desired, then it is recommended * to use {@link java.util.concurrent.ConcurrentHashMap} in place of * {@code Hashtable}. * * @author Arthur van Hoff * @author Josh Bloch * @author Neal Gafter * @see Object#equals(java.lang.Object) * @see Object#hashCode() * @see Hashtable#rehash() * @see Collection * @see Map * @see HashMap * @see TreeMap * @since JDK1.0 */
 public class Hashtable<K,V>
 extends Dictionary<K,V>
 implements Map<K,V>, Cloneable, java.io.Serializable { 
 ...
 }

### 1.2.2 HashTable 源码注释原文解读 ###

*  `HashTable` 是一种将`keys` 映射到`values`的`hashtable`(哈希表)实现类，其中`key` 和`value` 都不可以为`null`.
 *  要想从一个`hashtable`(哈希表)中存储或取出来对象，这个对象必须重写`hashCode`和`equals` 方法
 *  一个`HashTable` 实例对象有两个影响它性能的参数,**initial capacity**（**初始容量**）和**load factor** （**负载因子**）
 *  **capacity**（**容量**）是哈希表中存储桶的数量,**initial capacity**（**初始容量**） 是哈希表被创建时候的容量
 *  值得注意的是哈希表是`open` 的,当哈希发生冲突的时候，单个存储桶存储多个`entries`,必须按顺序搜索这些`entries`
 *  **load factor** （**负载因子**） 是衡量散列表在自动增加其容量之前允许达到的满度
 *  初始容量和负载因子参数仅是实现的提示。 有关何时以及是否调用rehash方法的确切详细信息取决于具体实现。
 *  通常，默认**load factor** （**负载因子**）是`0.75`，这个值在时间和空间成本之间提供了一个很好的折衷方案。 较高的值会减少空间开销，但会增加查找条目的时间（这在大多数操作中得到了体现，包括`get`和`put`
 *  **initial capacity**（**初始容量**）控制了浪费空间和重新哈希操作需求之间的权衡，这很耗时。如果初始容量大于哈希表将包含的最大条目数除以其负载因子，则永远不会进行重新哈希操作。 但是，**将初始容量设置得太高会浪费空间**。
 *  如果要在哈希表中输入很多`entries`，创建足够大的容量可能会允许`entries`插入比根据需要自动重新哈希来增长表执行会更有效。

比如当创建一个数字类型的哈希表的时候

Hashtable<String, Integer> numbers = new Hashtable<String, Integer>();
 numbers.put("one", 1);
 numbers.put("two", 2);
 numbers.put("three", 3);

就不如下面这样执行插入更有效率。

Hashtable<String, Integer> numbers = new Hashtable<String, Integer>(3);
 numbers.put("one", 1);
 numbers.put("two", 2);
 numbers.put("three", 3);

要想从这个hashtable中取出来值，那么如下这样写即可：

Integer n = numbers.get("two");
     if (n != null) { 
       System.out.println("two = " + n);
    }

*  由此类的所有“集合视图方法”返回的集合的迭代器方法返回的迭代器为快速失败：如果在创建迭代器之后的任何时候都对`Hashtable`进行了结构修改，则除了通过迭代器自己的`remove`方法之外，该迭代器都将抛出`ConcurrentModificationException`。
 *  因此，面对并发修改后，迭代器会快速干净地失败，而不是冒风险`Hashtable`的key和elements方法返回的枚举 `not` 不会很快失败。
 *  请注意，不能保证迭代器的快速失败行为
 *  通常来说，在存在不同步的并发修改的情况下，不可能做出任何严格的保证。
 *  快速失败的迭代器会尽最大努力抛出`ConcurrentModificationException`。
 *  因此，编写依赖于此异常的程序以确保其正确性是错误的：*迭代器的快速失败行为应仅用于检测错误。*
 *  从Java 2平台v1.2开始，HashMap 已改进为实现`Map`接口，使其成为 Java Collections Framework (Java集合框架).
 *  与新的集合实现不同的是，`Hashtable`方法上已经加了`synchronized`同步锁。
 *  **如果不需要线程安全的实现，建议使用HashMap代替`Hashtable`。 如果线程安全需要高度并行的实现，然后推荐使用`java.util.concurrent.ConcurrentHashMap`代替`Hashtable`**

本篇完～