# 一、集合
# 二、Hashmap
Map的本质是键值对，key值不可重复，HashMap是最常用的Map结构。键值对与数组下标对应的关系由key值的hashcode来决定。
# Hashmap优势
查找和操作的时间复杂度都为O(1)。
# Hashmap底层实现
Jdk1.7：数组+链表实现
Jdk1.8：数组+链表+红黑树实现
Java8之前的Hashmap，底层实现是数组加链表。其核心实现是一个单项链表数组（Entry<K, V>[] table）。
# Hashmap的put方法
Hashmap的put方法的大体流程：
根据key通过哈希算法与运算，得出数组下标；
如果数组下标位置为空，则将key和value封装到Entry对象（jdk1.7）/Node对象（jdk1.8），并加入该位置。
如果数组下标位置有元素，
(1) 若是JDK1.7，先判断是否需要扩容，若需要扩容就先进行扩容，若不需要则直接生成Entry对象，使用头插法添加到当前位置的链表中。
(2) 若是JDK1.8，先判断当前位置上Node的类型，是链表Node还是红黑树TreeNode
① 若是TreeNode红黑树(p instanceof TreeNode)，则将key和value封装为一个TreeNode，并添加到红黑树中（putTreeVal方法）；若当前key已存在，则更新value；
② 若是Node链表（p.hash == hash），则将key和value封装为一个Node，并通过尾插法（p.next = newNode()）加至链表最后位置next；
在遍历链表中，判断是否存在key，若存在则更新value；
当遍历后链表后，判断当前链表的节点个数，若大于等于8if (binCount >= TREEIFY_THRESHOLD - 1)，则进行链表转换为红黑树treeifyBin(tab, hash)。
③ 当Node插入到链表或红黑树后，再判断是否需要进行扩容，if (++size > threshold){ resize(); }