优化 Hasmap
如果哈希映射的内部数组只包含一个元素，则所有项将映射到此数组位置，从而构成一个较长的链接列表。由于我们的更新和访问使用了对链接列表的线性搜索，而这要比 Map 中的每个数组索引只包含一个对象的情形要慢得多，因此这样做的效率很低。访问或更新链接列表的时间与列表的大小线性相关，而使用哈希函数问或更新数组中的单个元素则与数组大小无关 — 就渐进性质（Big-O 表示法）而言，前者为 O(n)，而后者为 O(1)。因此，使用一个较大的数组而不是让太多的项聚集在太少的数组位置中是有意义的。
调整 Map 实现的大小
在哈希术语中，内部数组中的每个位置称作“存储桶”(bucket)，而可用的存储桶数（即内部数组的大小）称作容量 (capacity)。为使 Map 对象有效地处理任意数目的项，Map 实现可以调整自身的大小。但调整大小的开销很大。调整大小需要将所有元素重新插入到新数组中，这是因为不同的数组大小意味着对象现在映射到不同的索引值。先前冲突的键可能不再冲突，而先前不冲突的其他键现在可能冲突。这显然表明，如果将 Map 调整得足够大，则可以减少甚至不再需要重新调整大小，这很有可能显著提高速度。
使用 1.4.2 JVM 运行一个简单的测试，即用大量的项（数目超过一百万）填充 HashMap。表 5 显示了结果，并将所有时间标准化为已预先设置大小的服务器模式（关联文件中的 。对于已预先设置大小的 JVM，客户端和服务器模式 JVM 运行时间几乎相同（在放弃 JIT 编译阶段后）。但使用 Map 的默认大小将引发多次调整大小操作，开销很大，在服务器模式下要多用 50% 的时间，而在客户端模式下几乎要多用两倍的时间！
表 5：填充已预先设置大小的 HashMap 与填充默认大小的 HashMap 所需时间的比较
| | 客户端模式 | 服务器模式 | | 预先设置的大小 | 100% | 100% | | 默认大小 | 294% | 157% |
使用负载因子
为确定何时调整大小，而不是对每个存储桶中的链接列表的深度进行记数，基于哈希的 Map 使用一个额外参数并粗略计算存储桶的密度。Map 在调整大小之前，使用名为“负载因子”的参数指示 Map 将承担的“负载”量，即它的负载程度。负载因子、项数（Map 大小）与容量之间的关系简单明了：
- 如果（负载因子）x（容量）>（Map 大小），则调整 Map 大小
例如，如果默认负载因子为 0.75，默认容量为 11，则 11 x 0.75 = 8.25，该值向下取整为 8 个元素。因此，如果将第 8 个项添加到此 Map，则该 Map 将自身的大小调整为一个更大的值。相反，要计算避免调整大小所需的初始容量，用将要添加的项数除以负载因子，并向上取整，例如，
- 对于负载因子为 0.75 的 100 个项，应将容量设置为 100/0.75 = 133.33，并将结果向上取整为 134（或取整为 135 以使用奇数）
奇数个存储桶使 map 能够通过减少冲突数来提高执行效率。虽然我所做的测试（关联文件中的 并未表明质数可以始终获得更好的效率，但理想情形是容量取质数。1.4 版后的某些 Map（如 HashMap 和 LinkedHashMap，而非 Hashtable 或 IdentityHashMap）使用需要 2 的幂容量的哈希函数，但下一个最高 2 的幂容量由这些 Map 计算，因此您不必亲自计算。
负载因子本身是空间和时间之间的调整折衷。较小的负载因子将占用更多的空间，但将降低冲突的可能性，从而将加快访问和更新的速度。使用大于 0.75 的负载因子可能是不明智的，而使用大于 1.0 的负载因子肯定是不明知的，这是因为这必定会引发一次冲突。使用小于 0.50 的负载因子好处并不大，但只要您有效地调整 Map 的大小，应不会对小负载因子造成性能开销，而只会造成内存开销。但较小的负载因子将意味着如果您未预先调整 Map 的大小，则导致更频繁的调整大小，从而降低性能，因此在调整负载因子时一定要注意这个问题。 |
