一、Map集合
?1、Map接口
Map用于保存具有映射关系的数据Key-Value，Map里保存着这两组数据，它们都可以使任何引用类型的数据，key和value可以是任何引用类型的数据，会封装到HashMap$Node对象中，但key不能重复，key只能有一个为null，value可以有多个null。所以通过指定的key就可以取出对应的value，常用String类作为Map的key
Map 没有继承 Collection 接口， Map 提供 key 到 value 的映射，可以通过“键”查找“值”。 Map 接口提供 3 种集合的视图， Map 的内容可以被当作一组 key 集合，一组 value 集合，或者一组 key-value 映射。
2、Map接口常用方法
实例：
public class MapTest {
? ? public static void main(String[] args) {
? ? ? ? Map map = new HashMap();
? ? ? ? map.put("张三","北京");
? ? ? ? map.put("李四","武汉");
? ? ? ? map.put("王五","上海");
? ? ? ? map.put("李二",null);
? ? ? ? map.put(null,"南京");
? ? ? ? //remove
? ? ? ? map.remove(null);
? ? ? ? System.out.println("map="+map);
? ? ? ? //get
? ? ? ? Object val = map.get("张三");
? ? ? ? System.out.println("val="+val);
? ? ? ? //size
? ? ? ? System.out.println("k-v="+map.size());
? ? ? ? //isEmpty
? ? ? ? System.out.println(map.isEmpty());
? ? ? ? //clear
? ? ? ? map.clear();
? ? ? ? System.out.println("map="+map);
? ? ? ? //containsKey
? ? ? ? System.out.println(map.containsKey("李二"));
? ? }
}3、Map遍历方式
（1）、取出所有key对应的Value
public class MapTest {
? ? public static void main(String[] args) {
? ? ? ? Map map = new HashMap();
? ? ? ? map.put("张三","北京");
? ? ? ? map.put("李四","武汉");
? ? ? ? map.put("王五","上海");
? ? ? ? map.put("李二",null);
? ? ? ? map.put(null,"南京");
? ? ? ? //先取出所有key，通过key去除对应的Value
? ? ? ? Set keyset = map.keySet();
? ? ? ? //(1)、增强for
? ? ? ? for (Object key : keyset) {
? ? ? ? ? ? System.out.println(key+"-"+map.get(key));
? ? ? ? }
? ? ? ? //(2)、迭代器
? ? ? ? Iterator iterator = keyset.iterator();
? ? ? ? while (iterator.hasNext()) {
? ? ? ? ? ? Object key =? iterator.next();
? ? ? ? ? ? System.out.println(key+"-"+map.get(key));
? ? ? ? }
? ? }
}（2）、取出所有Values
public class MapTest {
? ? public static void main(String[] args) {
? ? ? ? Map map = new HashMap();
? ? ? ? map.put("张三","北京");
? ? ? ? map.put("李四","武汉");
? ? ? ? map.put("王五","上海");
? ? ? ? map.put("李二",null);
? ? ? ? map.put(null,"南京");
? ? ? ?
? ? ? ? //把所有的Values取出
? ? ? ? Collection values = map.values();
? ? ? ? //(1)、增强for
? ? ? ? for (Object key : values) {
? ? ? ? ? ? System.out.println(values);
? ? ? ? }
? ? ? ? //(2)、迭代器
? ? ? ? Iterator iterator = values.iterator();
? ? ? ? while (iterator.hasNext()) {
? ? ? ? ? ? Object value =? iterator.next();
? ? ? ? ? ? System.out.println(value);
? ? ? ? }
? ? }
}（3）、通过EntrySet获取k-v
public class MapTest {
? ? public static void main(String[] args) {
? ? ? ? Map map = new HashMap();
? ? ? ? map.put("张三","北京");
? ? ? ? map.put("李四","武汉");
? ? ? ? map.put("王五","上海");
? ? ? ? map.put("李二",null);
? ? ? ? map.put(null,"南京");
? ? ? ? //先取出所有key，通过key去除对应的Value
? ? ? ? Set keyset = map.keySet();
? ? ? ? //通过EntrySet来获取k-v
? ? ? ? Set entrySet = map.entrySet();
? ? ? ? //(1)、增强for
? ? ? ? for (Object entry : entrySet) {
? ? ? ? ? ? //将entry对象转成Map.Entry
? ? ? ? ? ? Map.Entry m = (Map.Entry) entry;
? ? ? ? ? ? System.out.println(m.getKey()+"-"+m.getValue());
? ? ? ? }
? ? ? ? //(2)、迭代器
? ? ? ? Iterator iterator = entrySet.iterator();
? ? ? ? while (iterator.hasNext()) {
? ? ? ? ? ? Object entry =? iterator.next();
? ? ? ? ? ? Map.Entry m = (Map.Entry) entry;
? ? ? ? ? ? System.out.println(m.getKey()+"-"+m.getValue());
? ? ? ? }
? ? }
}4、HashMap
执行Put()，该方法会执行hash(key)方法，得到key对应的hash值，但此hash值并不完全等价于hashcode值
如果key==null那么就将键值对存入索引为0的桶内，如果不为空则计算key的hashcode值，将h无符号右移16位进行异或运算得到hash值（>>(带符号右移) & >>>(无符号右移)）。之所以右移16位是为了减少碰撞，进一步降低hash冲突的几率。int类型的数值是4个字节的，右移16位异或可以同时保留高16位于低16位的特征。
putVal()方法
定义辅助变量
table就是HashMap的一个数组，类型是Node[]；
如果table数组为空或者table数组长度为0，则赋值resize的长度给变量n；其中有一个resize()方法
由于table为null，所以oldcap为0
此时oldcap为0，进入if判断，newCap赋值为16，并计算临界值，到底临界值就扩容，到达数组大小的0.75倍时就进行扩容，比如当前cap=16，则到12个元素进行扩容
这里有两个常量，默认初始容量和默认加载因子
当使用量接近数组容量75%时，数组中还剩下25%的空间，平均来看就是10个桶有四分之一是空的，当向map中存放数据时，碰撞概率是75%，但有25%的空闲空间，发生hash碰撞的概率还处在一个可以接受的范围内，所以如果扩容因子越大，碰撞的概率也就越大，效率也就越低，
如果负载因子是0.9，则平均来看10个桶中之有一个是空的，碰撞概率90%，几乎可以认为会发生碰撞。
如果负载因子是0.5，则平均来看10个桶中一半都是空的，当数组中的元素达到了一半就开始扩容，既然填充的元素少了，Hash冲突也会减少，底层链表或者红黑树的高度就会降低，但查询效率会增加。
现在创建newTab，newTab的容量就是16，并且把newTab赋值给Table
此时返回putVal()方法，根据key得到的hash值（(n - 1) & hash计算hash值，n即为tab.length），计算该key存到放table表的那个索引位置，并把这个位置的对象赋值给p
，如果p为空，表示还没有存放过元素，就创建一个Node
Node中存放hash, key, value, next四个值
modCount计数器改变，记录修改次数，判断如果长度大于12，则进行扩容，afterNodeInsertion方法为空方法，最后返回null
afterNodeInsertion()方法
map.put(e, PRESENT)返回一个null，说明map集合里存放成功，否则就表示添加的元素已经有了
当再次添加时，如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样，并且二者中任意一个 ①准备加入的key和p指向的Node结点的key是同一个对象 ②P指向的Node结点的key的equals()和准备加入的key比较后相同 则就不能加入；再判断p是不是一棵红黑树，如果是则调用putTreeVal()来进行添加；如果table对应索引位置已经是一个链表，就使用for循环中的循环比较机制，即添加进来的元素以此与已添加的链表元素对比，如过有相同的则返回，否则就添加到当前链表之后，注意添加到链表后判断该链表是否到达8个结点，如果达到则调用treefyBin()对当前链表进行树化，在进行树化时再判断table.length <= 64，达不到64时先扩容，到64后再进行树化
（1）、HashMap树化
public class HashMapTree {
? ? public static void main(String[] args) {
? ? ? ? HashMap hashMap = new HashMap();
? ? ? ? for (int i = 1; i <= 20; i++) {
? ? ? ? ? ? hashMap.put(new A(i),"hello");
? ? ? ? }
? ? ? ? System.out.println("HashMap="+hashMap);
? ? }
}
class A{
? ? private int num;
? ? public A(int num) {
? ? ? ? this.num = num;
? ? }
? ? //重写hashCode，所有A对象hashCode都是100
? ? @Override
? ? public int hashCode() {
? ? ? ? return 100;
? ? }
? ? @Override
? ? public String toString() {
? ? ? ? return "\nA{" +
? ? ? ? ? ? ? ? "num=" + num +
? ? ? ? ? ? ? ? '}';
? ? }
}添加第一个数据时，长度为12
当添加至9时，进行扩容，扩容到32
继续进行扩容，此时还是HashMap$Node，并不会进行树化
table到64之后，进行树化，由HashMap$Node演变为HashMap$TreeNode
（2）、索引算法
将hash值与阈值进行位运算获得数组中的索引，当一个int值a是二的次幂的时候，h跟a-1进行与运算的时候，刚好是h % a。
（3）、HashCode算法
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认初始大小为16在HashMap中采用了下图进行HashCode的运算，这样可以将hashCode的前后16位都充分利用。并且使用了异或运（其他的离散值为3/4，而异或为1/2）算来加大离散度（在哈希计算中，所有的操作都是为了加大离散度）。
（4）、扩容算法
initialCapacity（初始容量）+1，默认为16
如果length为2的次幂 则length-1 转化为二进制必定是11111……的形式，在与hashCode的二进制与操作效率会非常的快，而且空间不浪费；如果length不是2的次幂，比如length为15，则length-1为14，对应的二进制为1110，在与hashCode与操作， 最后一位都为0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！这样就会造成空间的浪费。
5、HashTable
（1）、简介
存放的元素是k-v键值对，HashTable的键和值都不能为null，HashTable使用方法基本上和HashMap一样，HashTable是线程安全的，HashMap不是线程安全的
（2）、HashTable底层机制
public class HashTableTest {
? ? public static void main(String[] args) {
? ? ? ? Hashtable table = new Hashtable();
? ? ? ? table.put("john",100);
? ? ? ? table.put("lucy",100);
? ? ? ? table.put("luck",100);
? ? ? ? System.out.println(table);
? ? }
}底层是Hashtable$Entry数组，第一次初始化大小为11
往table中存放第一个元素，还是Hashtable$Entry类型
当进行扩容时会执行addentry()
当满足count >= threshold时，进入rehash()
首先把当前的容量拿到并用oldMap指向它，将原来的容量左移1位再+1，判断新容量大于最大大小就会返回，否则按照最新大小进行扩容
6、Properties
（1）、简介
Properties类继承自Hashtable类并且实现了Map接口，也是使用一种键值对的形式来保存数据，特点和Hashtable类似，Properties还可以从Properties文件中加载数据到Properties类对象，并进行读取和修改
（2）、Properties实现
三、Queue集合
Queue接口与List、Set同一级别，都是继承了Collection接口。
Queue用于模拟队列这种数据结构，队列的头部保存在队列中存放时间最长的元素，队列的尾部保存在队列中存放时间最短的元素。新元素插入（offer）到队列的尾部，访问元素（poll）操作会返回队列头部的元素。Queue中定义了如下几个方法：
-
void add(Object e)
-
Object element()
-
boolean offer(Object e)
-
Object peek()
-
Object poll()
-
Object remove()
四、PriorityQueue实现类
PriorityQueue保存队列元素的顺序并不是按加入时的顺序，而是按照队列怨怒的大小进行重新排序。因此调用poll()或者peek()方法取出队列中的元素时，并不是取出最先进入队列的元素，而是取出队列中最小的元素。
PriorityQueue不允许插入null元素，它还需要对队列元素进行排序，PriorityQueue的元素有两种排序方式：
-
自然排序
-
定制排序
import java.util.PriorityQueue;
public class PriorityQueueTest{
? ?? public static void main(String[] args) {
? ? ? ?? PriorityQueue pq = new PriorityQueue();
? ? ? ?? //依次向pq中加入四个元素
? ? ? ?? pq.offer(6);
? ? ? ?? pq.offer(-3);
? ? ? ?? pq.offer(20);
? ? ? ?? pq.offer(18);
? ? ? ?? //输出pq队列，并不是按元素的加入顺序排列
? ? ? ?? System.out.println(pq);
? ? ? ?? //访问队列的第一个元素，其实就是队列中最小的元素：-3
? ? ? ?? System.out.println(pq.poll());
? ?? }
}