在没有排序或额外索引的数组、链表中,按值查找最坏需要遍历全部元素。哈希表(hash table)通过哈希值定位桶,在哈希分布良好时,基本查找可以接近常数时间;这不代表所有输入下都能保证 O(1)。
HashMap是基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。(除了非同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)此类不保证映射的顺序,特别是它不保证该顺序恒久不变。
本文按源码顺序看 HashMap:数组与链表的数据结构、构造函数、put 和扩容、get,最后是迭代器如何用 modCount 检查结构修改。末尾补充后续 JDK 的变化。