一、概述

Map是一种集合类，Java的集合类定义在Java.util包中。

 Map是一种键值对（key-value）映射表的数据结构，作用远远能高效的通过key快速查找value（元素）。
1

二、基本操作

Map是一种键-值映射表。
1

当我们调用V get（K key）时，就可以通过key获取到对应的value。如果key不存在，则返回的时null。
重复放入key—value并不会有任何问题，一个kay只能对应一个value，当重复对一个key映射value时，最新的value会覆盖旧的value，旧的value会被删掉，否则，返回null。
Map是一个接口，最常用的实现类是HashMap。

三、HashMap

一、HashMap概述

HashMap之所以能够根据key直接拿到value，原因是它内部通过空间换时间的方法，用一个大数组存储所有的value，并根据key直接计算出value应该存储在那个索引上。

相同的key每次取出的value就不一定对。通过key计算索引的方式就是每次调用key对象的hashcode()方法，它返回一个int整数。HashMap正是通过这个方法直接定位key对应的value的索引，继而直接返回value。

二、HashMap源码分析

HashMap内部的数据结构使用数组+链表+红黑树进行存储。数据类型为Node[]，每个Node都保存了某个KV键值对元素的kay、value、hash、nexy等值。由于next的存在，所有每个Node对象都是一个单向链表中的组成节点。
当新添加一个KV键值对元素时，通过该元素的key的hash值，计算该元素在数组中应该保存的下标位置。如果该下标位置如果已经存在其他Node对象（产生哈希冲突），则采用链地址法处理，即将新添加的KV键值对元素将以链表的形式存储。将元素封装成一个新的Node对象，插入到该下标位置的来链表尾部（尾插法）。当链表的长度超过8并且长度大于64时，为了避免查找搜索性下降，该链表会转换成一个红黑树。

三、HashMap初始容量

HashMap通过key的hashCode()得出一个hash值，并且通过这个hash值计算数组位置下标。
HashMap初始化的时候默认的数组大小只有16，通过位运算1<<4计算得出。并且，数组的长度必须为2^n.因为数组长度为2的n次幂时，可以使用户&与运算符，结合hash值，快速计算该元素在数组中的下标位置，提高HashMap的使用效率。

四、HasnMap的扩容

HasnMap底层采用数组+链表+红黑树，扩容过程中需要按照数组容量和加载因子来进行判断。
1

数组容量：基础数组Node[] table的长度。如果没有指定容量，添加第一个元素时，该数组按照默认值16进行初始化。
加载因子：用来表示HasnMap集合中的元素的填满程度，默认为0.75f。越大则表示允许填满的元素越多，集合的空间利用率就越高，但是冲突的机会增加。反之，越小则冲突的机会就会越少，但是空间很多就会浪费。

什么时候扩容？

HashMap的扩容方法是resize()方法，发生以下两种情况会发生扩容：
情况一：
HashMap中的元素个数超过扩容阈值时，就会进行数组扩容（扩容阈值=数组容量*加载因子）。
情况二：
HashMap假如新的元素时，如果链表长度大于8时，会将当前链表转换成红黑树。在转换成红黑树之前，会判断数组长度，如果小于64，会产生数组扩容。如果数组长度大于64，才会将链表转换成红黑树。

最大容量：
HashMap每次扩容时，都会检查当前容量是否超过常量值MAXIMUM_CAPACITY,如果超出，则不扩容。常量值MAXIMUM_CAPACITY通过1<<30，计算结果为1073741824。所以，HashMap集合数组的最大容量为1073741824。