50.图
[ConcurrentHashMap](//www.greatytc.com/p/0b452a6e4f4e)
1.Java 多线程的内存模型
HashMap数据存储在主线程内存，
几个线程来修改数据，都会把【主内存】的数据读到线程的【工作内存】中，操作完毕后，再将内容重新 写回到【主内存】。
1.1.HashMap 多线程同时put数据，会出现什么问题？
- 会出现数据丢失；
由于子线程相互不可见，数据被其他线程回写时覆盖了。写入白写了。 - 会出现死循环（扩容时引起的）。
产生死循环的主要原因是由于 并发操作 和 头插法 导致的。
因为是头插法，所以 HashMap 的顺序已经发生了改变，但线程 T2 对于发生的一切是不可知的，所以它的指向元素依然没变.
T1 执行完之后的顺序是 B 到 A，而 T2 的顺序是 A 到 B，这样 A 节点和 B 节点就形成死循环了.
上述问题的 解决方案：
1.使用ConcurrentHashMap：从JDK1.8开始，官方推荐使用 ConcurrentHashMap，
它是一个线程安全的HashMap变体，内部通过分段锁（Segment）机制来保证并发操作的正确性，避免了死循环的问题。
jdk1.8前使用分段的lock；jdk1.8后使用分段的（synchronized + CAS）
CAS：compare and swap 保证线程安全。
2.同步控制：在多线程环境下操作HashMap时，可以通过显式锁定相关代码块来避免死循环。
- HashTab(已过时api)-给put加锁 或 Collections.synchronizedMap 锁住put方法。
都是锁住整个个方法，
如果一个线程在put数据，另外一个线程不允许也不允许get；如果是一个线程get也同理。
把整个方法都锁起来，没有必要。 只需要分段锁住某一个链即可。
操作同一个链表，你改了我不可见，两次刷新就会导致数据丢失；
不是操作同一链表，你改了我不可见，两次刷新没有覆盖的可能，就不会出现数据丢失。
最好的解决方案，只要保证2个线程，不操作同一个链即可。 这就有了分段锁的 ConcurrentHashMap。
1.2 ConcurrentHashMap源码
put的时候，不直接锁住整个方法，只要不操作同一个链，可以同时put数据。---》 分段锁，只锁住单个链。
jdk1.8前使用分段的lock；jdk1.8后使用分段的（synchronized + CAS）
CAS：compare and swap 保证线程安全。
put方法，头结点非空，锁住头结点，
get方法，next和val 都用voilate修饰，保证子线程可见
（数据 被子线程修改但是没有刷到主内存，另外的子线程能读取到修改后的数据）。
2. synchronized 的底层实现原理
synchronized 是怎么实现线程安全的？
synchronized 包起来的代码，会添加2个代码。
synchronized void add(){
// 每个对象头里面有个重要信息 mark work，里面放了gc的分代年龄，hashCode，锁的信息。
// 锁信息moniter：线程id，是否偏向锁，锁的标志 等。
moniterenter(object);
size++;
moniterexit(object);
}
// 有线程1在操作 moniterenter moniter里面的线程信息会被改变，新的线程就等待。
// 线程1执行完后，把工作内存的数据刷新回主内存，然后执行moniterexit，锁的信息回置空，然后把所有在这里等待的线程唤醒。
多个子线程在等待，看谁执行的快。
大多数情况下，只有一个线程，
EventBus 也使用的 ConcurrentHashMap 有可能在eventbus中做多线程，EventBus用在主线程中。
防止在多线程时，使用eventBus通信。
一个线程执行，没必要锁死和唤醒，会好性能。
jdk1.6 再次进行优化，将锁进行分级：
偏向锁：
第一个线程进来，锁设置为偏向锁；没新的线程进来，不需要唤醒；同一个线程自己重新进来，不需要判断锁id等信息。
如果只有一个线程，结束时 不要做唤醒这一步，但是锁的状态还是要释放。轻量级：
假设有2个线程竞争，第一个线程进去设置的是偏向锁，第二个线程进来 锁住了进不去，他要对锁进行升级，升级为轻量级锁。
线程二进行自旋（清醒状态，不断地在这里等），假设线程一执行完，发现锁是轻量级锁，就释放锁即可。 线程二可以执行重量级：
不断地自旋，肯定会消耗内存，如果迟迟拿不到锁，就必须对锁在进行再升级（重量级锁）线程阻塞等待，
第一个线程出去的时候，发现是重量级，首先将锁的状态释放，然后通知其他线程竞争锁。
sync 有点像挤地铁，
TODO：lock锁，有点像医院排队，
volatile 关键字：保证内存可见（读写），指令集乱序问题。
发现缓存失效了，重新从主内存读取。
工作内存中，都有一个信号的观察者。
当数据在工作内存修改后，会立即刷到主内存，然后通知每个信号观察者 你的缓存已经失效了，再操作的时候，要从主内存重新读一遍。
每次写的数据，保证另一个线程能看的到。
volatile int size =0;
只加volatile，并不能解决多线程访问数据，数据不可控问题。并不能解决。还是要依赖synchronized锁。
void add(){
size++; // 相当于三行代码，[同步]int temp=get(); temp+=1; [同步]set(temp)，中间那行代码容易出问题。
}
《Java的多线程编程艺术》
3.图（Graph）的基础定义
图（Graph）是由顶点的【有穷非空集合】和【顶点之间边的集合】组成，通常表示为：G（V，E），
其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
图由点和变组成，
注意：线性表中可以没有元素，称为空表。树中可以没有结点，叫做空树。但是在图中不允许没有顶点，可以没有边。
基本术语：
无向边：若顶点V1和V2之间的边没有方向，称这条边为无向边（Edge），用（V1，V2）来表示。
无向图（Undirected graphs）：图中任意两个顶点的边都是无向边。
有向边：若从顶点V1到V2的边有方向，称这条边为有向边，也称为弧（Arc），用<V2, V1>来表示，其中V1称为弧尾（Tail），V2称为弧头（Head）。
有向图（Directed graphs）：图中任意两个顶点的边都是有向边。
无向完全图：无向图中，任意两个顶点之间都存在边。
有向完全图：有向图中，任意两个顶点之间都存在方向相反的两条弧。
稀疏图；有很少条边或弧的图称为稀疏图 n*log(n)，反之称为稠密图。 相对的概念（头发稀疏）完全图肯定是稠密
权（Weight）：表示从图中一个顶点到另一个顶点的距离或耗费。
网：带有权重的图.
度：与特定顶点相连接的边数量；
出度、入度：有向图中的概念，出度表示以此顶点为起点的边的数目，入度表示以此顶点为终点的边的数目；
连通图：任意两个顶点都相互连通的图；
生成树：n个顶点，n-1条边 ，的图可以看成树 （生成树）
最小生成树：此生成树的边的权重之和是所有生成树中最小的，找最短路径；
4.图的存储结构
数组存，链表存
顶点 ：用数组
边：二维数组（矩阵）
一个图对象，有两个变量：
- 一个变量存顶点 [V1,V2, V3,V4,V5]；
- 另一个边的二维数组 vertex[5][5]。
图的深度优先和广度优先遍历
最小生成树和最短路径
系统学习，书本+视频。
