目录

Map

Map是Key-value键值对映射的抽象接口，该映射不包括重复的键，既一个键对应一个值。

哈希表

数组：采用一段连续的存储单元来存储数据。寻址速度快（查询速度快），时间复杂度为O(1)，但是在插入、删除元素时候需要移动数组的元素，所以插入、删除时候速度慢，时间复杂度为O(n)。。
　　对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，当然，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)
　　
　　线性链表：链表的存储方式在内存上是不连续的，对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为O(n)。
　　
　　如果我们想要一个数据结构既查询速度快，插入和删除速度也要快，那我们应该怎么做呢？这时哈希(Hash)表就应时而生了，通过哈希函数计算出键在哈希表中指定的储存位置(注意这里的储存位置是在表中的位置，并不是内存的地址)，称为哈希地址，然后将值储存在这个哈希地址上，然后通过键就可以直接操作到值，查询、插入、删除等操作时间复杂度都是O(1)。
　　哈希表可以说就是数组链表，底层还是数组但是这个数组每一项就是一个链表。在这个数组中，每个元素存储的其实是一个链表的头，元素的存储位置一般情况是通过喊下函数获得。

　　 比如我们要新增或查找某个元素，我们通过把当前元素的关键字 通过某个函数映射到数组中的某个位置，通过数组下标一次定位就可完成操作。
　　存储位置 = f(key)其中，这个函数f一般称为哈希函数，这个函数的设计好坏会直接影响到哈希表的优劣。查找操作同理，先通过哈希函数计算出实际存储地址，然后从数组中对应地址取出即可。

哈希冲突

当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。
哈希冲突的解决方案有多种:开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），链地址法，。
1、链地址法(拉链法)。
采用数组和链表结合的方法，对哈希表中每个哈希地址建立一个线性表，将哈希地址相同的数据储存在线性表中，并将链表的头指针保存在数组中，哈希地址、键、值等信息一般保存在链表节点中。一般通过哈希地址计算出数组的下标，将哈希值相同的保存在下标相同的数组中的。拉链法适合经常进行插入、删除操作的情况。

HashMap

HashMap采用上述的拉链法解决哈希冲突。HashMap是非线程安全的，允许键、值为null，不保证有序(比如插入的顺序)，也不保证顺序不随时间变化(哈希表加倍扩容后，数据会有迁移)。

HashMap有几个重要的成员变量，table，size，threshold，loadFactor，modCount。

table：是一个Entry[]数组类型，而Entry实际上是一个单向链表，哈希表的键值对都是储存在Entry数组中，每个Entry对应一个哈希地址，这里的Entry即常说的桶
size：是HashMap的大小，为保存的键值对的数量
threshold：是HashMap的阈值，用于判断是否需要调整HashMap的容量。threshold=容量*负载因子，当HashMap中储存的键值对数量到达threshold时，HashMap就会将容量加倍的扩容
loadFactor：即负载因子，默认0.75。超过0.75时会以2的次幂的倍数扩容。

put方法

调用put方法的时候,方法内部会调用hash(key)方法,计算出key的hash值,然后对哈希值进一步计算出下标（存储位置）。如果这个位置上没有元素，就把元素直接存储在上面，如果这个位置上已经存在元素，这个时候才去调用equal方法与新元素进行比较，相同的话就不存了，散列到其他地址上。

get方法

get(key)方法的代码比较好理解，根据key的hash值找到对应的Entry即链表，然后在返回该key值对应的value。