源码是最好的教程,它比你想象中还详细的解读的类的原理. 我就从源码注解的来看一下HashMap的底层原理。你可以在任意IDE打开HashMap.java，查看这些源码注解。此jdk版本为1.8。
翻译
以下是类外的源码注解:
HashMap是基于哈希表的Map接口实现。此实现提供了所有可选的map操作（译注：实现了Map的所有方法）, 并允许有null值和null键值。（HashMap类大致相当于Hashtable，不同之处在于它是不同步的，并允许键和值为null。）这个类不能保证map的顺序；特别是，它不能保证顺序在一段时间内保持不变。(译注:不能保证插入的顺序和输出的顺序一致, 也不能保证此输出顺序一直不变)
HashMap为基本操作（get和put）提供了恒定时间的性能，假设hash函数在桶中正确分散元素。 集合视图的迭代需要时间与HashMap实例的“容量”（桶数）加上其大小（键值对 数）成正比。因此，如果迭代性能很重要，不要将初始容量设置得太高（或负载因子太低）是非常重要的。
分析：在我理解恒定时间的性能是指方法的运行时间是恒定的. 桶是一个比喻, 数组的每个元素空间相当于一个桶, 好像链表就存放于桶中，实际上是链表的首节点存放于数组中. 当你看见文末的示意图就明白了. 键值对 数指能存放Entry的数量. 初始容量默认为16, 负载因子默认为0.75.
HashMap的一个实例有两个参数影响它的性能：初始容量和负载因子。容量是散列表中的桶数，初始容量只是创建散列表时的容量。负载因子是衡量散列表完整性的度量标准，允许在容量自动增加之前获得。当散列表中的Entry数超过了负载因子和当前容量的乘积，hash表就rehashed（即内部数据结构重建），使散列表大约有两倍buckets数。
分析: 例如，当散列表的Entry数超过0.75*16时，就rehashed。因为碰撞，此时数组中可能还没有12个桶被占用。
作为普遍规则，默认负载因子（.75）提供了时间和空间成本之间的良好折中。 更高的值会降低空间开销，但会增加查找成本（反映在HashMap类的大部分操作中，包括get 和put）。 在设置其初始容量时，应考虑map中预期的entries数及其负载因子，以尽量减少重复操作的次数。 如果初始容量大于最大entries数除以负载因子（译注：相当于entries数小于初始容量乘以负载因子），则不会发生rehash操作。
如果许多映射要存储在HashMap实例中，创建了一个足够大的容量将允许存储的映射比其按需要执行自动rehashing以增长表更加有效率。 请注意，许多key对象有相同的hashcode是降低任何hash表的性能的一个确切原因。 为了改善影响，当键为可比较时，该类可以使用键之间的比较顺序来帮助打破约束关系。（译注：hashcode相同会发生碰撞,利用在链表中依次比较后插入）.
请注意，此实现不同步。如果多个线程并发访问hashMap，并且至少有一个线程要在结构上修改map，则必须在外部进行同步。（结构修改是指添加或删除一个或多个键值对的任何操作；仅改变实例已经包含key相关联的value不是结构修改。）这通常通过对自然封装过的map的一些对象进行同步来完成。（译注：自然封装过的是直译）
如果没有这样的对象存在，应该使用Collections.synchronizedMap方法“包装”map。 这最好在创建时完成，以防止意外的不同步访问map：
Map m = Collections.synchronizedMap（new HashMap（...））;迭代器返回的所有这些类的“集合视图方法”是fail-fast：如果map 在迭代器创建之后的任何时间进行结构修改，除了通过迭代器自己的 remove 方法 ，以其他任何方式修改，迭代器将抛出一个ConcurrentModificationException异常。因此，面对并发修改，迭代器将快速而干净(fast))失败(fail)，而不是在未来不确定的时间里有冒着任意的、非确定性行为的风险。
请注意，迭代器的fail-fast无法保证像它所定义的那样，因为一般来说，在不同步并发修改的情况下，无法做出任何硬性保证。 Fail-fast的迭代器在最大努力的基础上抛出ConcurrentModificationException。 因此，编写取决于此异常的正确性的程序将是错误的：迭代器的fail-fast行为应仅用于检测错误。
该类是Java Collections Framework 的成员。
以下是类中的源码:
实施说明。
这个map通常用作为一个容器（bucketed）hash表，但是当容器变得太大时，它们被转换成TreeNodes容器，每个都与java.util.TreeMap的结构类似。大多数方法尝试使用正常的容器，但是在适用的情况下继承TreeNode的方法（只需通过检查一个节点的instanceof）。TreeNode容器可以像任何其他树一样遍历和使用树节点，但另外支持在entries过多时更快的查找。然而，由于绝大多数正常使用的容器不会entries过多，所以检查树类容器的存在可能会延迟table方法的运行过程。
总结
我们通过上面的源码翻译，可以将HashMap的底层理解为由数组加链表实现。如此图：
)
image
HashMap基于hashing（散列）原理，我们通过put和get法来存储和获取对象。transient Node<K,V>[] table;,table存放链表头结点。链表的每个Node(Node相当于Entry)有hash、key、value、next四个属性。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
网友评论