記路

Map就如它字面意思，是一个从键（key）到值（value）的映射。我们在Map里面存储键值对，根据键得到值，因此键是不能重复的（如果插入一个有重复键的记录，则会覆盖原有的值），但是值可以重复。

Java里面基于对Map的不同访问需求创建了它的不同实现类：

• 对键的顺序没有要求
• 取出键的顺序按照插入记录时的顺序
• 取出键的顺序按照键的升序排序

在计算机程序里，数据存储的方式无外乎两种：顺序存储和链式存储。顺序存储的结构可以称为顺序表，也可以用数组描述，链式存储的结构可以称为链表。
我们每一个学过数据结构的都知道，它们两者各自有一些鲜明的特性，比如：

• 我们可以通过数组下标去访问数组里的元素，查询、更新的效率高，时间复杂度是O(1)，但是在中间某个位置插入或删除一个元素就要挪动后面所有的元素，时间复杂度是O(n)。
• 链表里元素之间存在指针指向关联的另一个元素，我们只能通过指针挨个去遍历访问链表里的元素，查询、更新的效率低，时间复杂度是O(n)，在中间某个位置插入或删除一个元素比较方便，只需要修改相邻指针的引用就可以了，时间复杂度是O(1)。