java中map集合的用法

本原理，但我们还没有对其进行详细介绍。 我们的哈希函数将任意对象映射到一个数组位置，但如果两个不同的键映射到相同的位置，情况将会如何？ 这是一种必然发生的情况。 在哈希映射的术语中，这称作冲突。 Map 处理这些冲突的方法是在索引位置处插入一个链接列表，并简单地将元素添加到此链接列表。 因此，一个基于哈希的 Map 的基本 put() 方法可能如下所示 public Object put(Object key, Object value) {//我们的内部数组是一个 Entry 对象数组//Entry[] table;//获取哈希码，并映射到一个索引int hash = key.hashCode();int index = (hash & 0x7FFFFFFF) % table.length;//循环遍历位于 table[index] 处的链接列表，以查明//我们是否拥有此键项 — 如果拥有，则覆盖它for (Entry e = table[index] ; e != null ; e = e.next) {//必须检查键是否相等，原因是不同的键对象//可能拥有相同的哈希if ((e.hash == hash) && e.key.equals(key)) {//这是相同键，覆盖该值//并从该方法返回 old 值Object old = e.value;e.value = value;return old;}}//仍然在此处，因此它是一个新键，只需添加一个新 Entry//Entry 对象包含 key 对象、 value 对象、一个整型的 hash、//和一个指向列表中的下一个 Entry 的 next Entry//创建一个指向上一个列表开头的新 Entry，//并将此新 Entry 插入表中Entry e = new Entry(hash, key, value, table[index]);table[index] = e;return null;} 如果看一下各种基于哈希的 Map 的源代码，您将发现这基本上就是它们的工作原理。 此外，还有一些需要进一步考虑的事项，如处理空键和值以及调整内部数组。 此处定义的 put() 方法还包含相应 get() 的算法，这是因为插入包括搜索映射索引处的项以查明该键是否已经存在。 （即 get() 方法与 put() 方法具有相同的算法，但 get() 不包含插入和覆盖代码。） 使用链接列表并不是解决冲突的唯一方法，某些哈希映射使用另一种“开放式寻址”方案，本文对其不予介绍。 优化 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% 的时间，而在客户端模