数据结构与算法-学习笔记 Java 版.zip

/* * Copyright (c) 1997, 2017, Oracle and/or its affiliates. All rights reserved. * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. * * * * * * * * * * * * * * * * * * * * */ package java2.util; import sun.misc.SharedSecrets; import java.io.IOException; import java.io.InvalidObjectException; import java.io.Serializable; import java.lang.reflect.ParameterizedType; import java.lang.reflect.Type; import java.util.Objects; import java.util.function.BiConsumer; import java.util.function.BiFunction; import java.util.function.Consumer; import java.util.function.Function; /** * 介绍和公共方法是从 1.6 的 中文 api 来的，官方的翻译可能会好一些。 * 实现说明和非公共方法就没有官方的翻译了，是自己翻译的可能不准确。 * <p> * Hash table based implementation of the <tt>Map</tt> interface. This * implementation provides all of the optional map operations, and permits * <tt>null</tt> values and the <tt>null</tt> key. (The <tt>HashMap</tt> * class is roughly equivalent to <tt>Hashtable</tt>, except that it is * unsynchronized and permits nulls.) This class makes no guarantees as to * the order of the map; in particular, it does not guarantee that the order * will remain constant over time. * <p> * 基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。 * （除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。） * 此类不保证映射的顺序，特别是它不保证该顺序恒久不变。 * <p> * Q:为什么不能保证顺序 * 因为迭代时使用的 HashIterator ，它内部根据 index 迭代，index 是由 hash(key) 算出来的，所以与 key 没有顺序关系。 * <p> * <p>This implementation provides constant-time performance for the basic * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function * disperses the elements properly among the buckets. Iteration over * collection views requires time proportional to the "capacity" of the * <tt>HashMap</tt> instance (the number of buckets) plus its size (the number * of key-value mappings). Thus, it's very important not to set the initial * capacity too high (or the load factor too low) if iteration performance is * important. * <p> * 此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作（get 和 put）提供稳定的性能。 * 迭代 collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。 * 所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。 * <p> * Q:TODO 为什么稳定？性能是多少？ * <p> * <p>An instance of <tt>HashMap</tt> has two parameters that affect its * performance: <i>initial capacity</i> and <i>load factor</i>. The * <i>capacity</i> 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. The * <i>load factor</i> is a measure of how full the hash table is allowed to * get before its capacity is automatically increased. When the number of * entries in the hash table exceeds the product of the load factor and the * current capacity, the hash table is <i>rehashed</i> (that is, internal data * structures are rebuilt) so that the hash table has approximately twice the * number of buckets. * <p> * HashMap 的实例有两个参数影响其性能：初始容量 和加载因子。 * 容量 是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。 * 加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。 * 当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构）， * 从而哈希表将具有大约两倍的桶数。 * <p> * 这里应该是文档没有更新，在 1.8 中是没有 rehash 的操作的 * 不过翻译一下， 1.7 中的方法也是叫 resize ，然后在 transfer 中根据参数判断重新计算 hash * 在 1.6 是不判断的，直接 rehash * <p> * <p>As a general rule, the default load factor (.75) offers a good * tradeoff between time and space costs. Higher values decrease the * space overhead but increase the lookup cost (reflected in most of * the operations of the <tt>HashMap</tt> class, including * <tt>get</tt> and <tt>put</tt>). The expected number of entries in * the map and its load factor should be taken into account when * setting its initial capacity, so as to minimize the number of * rehash operations. If the initial capacity is greater than the * maximum number of entries divided by the load factor, no rehash * operations will ever occur. * <p> * 通常，默认加载因子 (.75) 在时间和空间成本上寻求一种折衷。 * 加载因子过高虽然减少了空间开销，但同时也增加了查询成本 * （在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。 * 在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。 * 如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。 * <p> * <p>If many mappings are to be stored in a <tt>HashMap</tt> * instance, creating it with a sufficiently large capacity will allow * the mappings to be stored more efficiently than letting it perform * automatic rehashing as needed to grow the table. Note that using * many keys with the same {@code hashCode()} is a sure way to slow * down performance of any hash table. To ameliorate impact, when keys * are {@link Comparable}, this class may use comparison order among * keys to help break ties. * <p> * 如果很多映射关系要存储在 HashMap 实例中，则相对于按需执行自动的 rehash 操作以增大表的容量来说， * 使用足够大的初始容量创建它将使得映射关系能更有效地存储。 * 请注意，使用具有相同 {@code hashCode()} 的多个 key 可以减慢任何哈希表的性能。 * 为了改善影响，当键是 {@link Comparable} 时，这个类可以使用键之间的比较顺序来帮助打破关系。 * <p> * <p><strong>Note that this implementation is not synchronized.</strong> * If multiple threads access a hash map concurrently, and at least one of * the threads modifies the map structurally, it <i>must</i> be * synchronized externally. (A structural modification is any operation * that adds or deletes one or more mappings; merely changing the value * associated with a key that an instance already contains is not a * structural modification.) This is typically accomplished by * synchronizing on some object that naturally encapsulates the map. * <p> * 注意，此实现不是同步的。 * 如果多个线程同时访问一个哈希映射，而其中至少一个线程从结构上修改了该映射，则它 必须 保持外部同步。 * （结构上的修改是指添加或删除一个或多个映射关系的任何操作；仅改变与实例已经包含的键关联的值不是结构上的修改。） * 这一般通过对自然封装该映射的对象进行同步操作来完成。 * <p> * If no such object exists, the map should be "wrapped" using the * {@link Collections#synchronizedMap Collections.synchronizedMap} * method. This is best done at creation time, to prevent accidental * unsynchronized access to the map:<pre> * Map m = Collections.synchronizedMap(new HashMap(...));</pre> * <p> * 如果不存在这样的对象，则应该使用 Collections.synchronizedMap 方法来“包装”该映射。 * 最好在创建时完成这一操作，以防止对映射进行意外的非同步访问，如下所示： * <p> * <p>The iterators retur