深入Java集合学习系列：HashMap的实现原理

?原文章链接：http://zhangshixi.iteye.com/blog/672697，转载只为学习记录

1.??? HashMap概述：

???HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

?

2.??? HashMap的数据结构：

???在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。

?? 从上图中可以看出，HashMap底层就是一个数组结构，数组中的每一项又是一个链表。当新建一个HashMap的时候，就会初始化一个数组。

?? 源码如下：

?

?
?
?
?
?
?
?
?
?
?
final Entry<K,V> nextEntry() { if (modCount != expectedModCount) throw new ConcurrentModificationException();

?

?? 在HashMap的API中指出：

?? 由所有HashMap类的“collection 视图方法”所返回的迭代器都是快速失败的：在迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器本身的 remove 方法，其他任何时间任何方式的修改，迭代器都将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不冒在将来不确定的时间发生任意不确定行为的风险。

?? 注意，迭代器的快速失败行为不能得到保证，一般来说，存在非同步的并发修改时，不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此，编写依赖于此异常的程序的做法是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测程序错误。

?

?

参考资料：

JDK API HashMap???? HashMap 源代码???? 深入理解HashMap

通过分析 JDK 源代码研究 Hash 存储机制??? java.util.HashMap源码要点浅析