在这里说一下，线程安全和线程不安全的容器类。请带着质疑的角度看待这篇文章，感恩。
前提
什么是线程安全？
通俗的说，在多线程中，在执行一段代码上，仍然按照我们原先设想的逻辑运行，产生我们意向到的结果。
学术的说，在一个线程调用共享资源的时候，什么时候让其他线程，或者怎么样让其他线程看到这个资源的变化。
java内存模型如何应对上述问题？
happend-before ，数据依赖性 ，as-if-serial , 内存屏障，----这些都是禁止某些指令重排
happend-before ，数据依赖性 ，as-if-serial 这三个都是说，禁止某些重排序，按照前趋图，执行。就是写了才能读，开始了才能结束，有一个逻辑上的先后关系。当然happend-before有个更重要的一点
A hb B
B hb C
结果 ： A hb C
内存屏障：禁止某些重排序 + 缓存和主存之间数据的一致性问题。
如何保证线程安全，
锁（synchronized / lock ) ， CAS ， 写时复制，
正题
关于数据结构，分为逻辑上的和真实存储在计算机中的数据的结构。也可以分为真实的结构（数组，链表）和具体的程序员实现的抽象结构（栈，队列 ，堆，图，树，散列表）.
java中常见的，我下面要说的数据结构：list , set , map
1.关于list :
有序（存储的/插入的顺序），意思就是排队的内个意思，每个人都拿着爱的号码牌，
可以重复
删除，查找的时候要比较，数据类型为引用数据类型时 ， 类要重写equals()方法。
单线程：
ArrayList和LinkedList的差别？
看过源码都知道：ArrayList 用数组实现，查询效率高，插入删除效率低， LinkedList是用双向链表实现的，插入删除效率高 ，查询效率低。
这些单线程的都是强一致性，有一个字段modCount （对象被修改次数）这个字段作用：在用迭代器的遍历中，这个时候其他线程修改了数据的结构（增/删），就会报ConcurrentModificationException异常。
多线程安全：
1.Vector.Class ， 在每个方法上加synchronized关键字，加锁实现线程安全。
2.Collections.synchronizedList(....) ,也是通过加synchronized锁来实现线程安全
3.juc包下CopyOnWriteArrayList.Class ，数组实现，适用在读多，写少的场合中。
- 使用 ReentrantLock 和 volatile 和 写时复制 ，三个方面解决线程安全问题
- volatile : 解决数组的内存可见性
-RentrantLock ，锁住的是：修改容器内的数据的时候的只允许一个线程修改。
-写时复制：保证如果有线程正在修改容器内的数据，这个时候有线程想读，读取容器内的数据，修改的是复制的版本，修改之后把数据在刷新在容器内，因为这个容器内的数据是volatile， 保证多线程中的内存可见性。
2.关于Map
这里先说Map，因为大部分Set中数据的存储在对应Map中的Key中。
容器内的数据类型，如果是引用数据类型，要重写hashCode(）方法和equals()方法，因为添加对象步骤如下;
首先调用hashCode()方法，（此计算的对象哈希值决定了Set中的存储位置）：若此位置之前没有对象存储，则这个对象，直接存储到此位置上;若有存储对象，通过equals方法，比较这两个对象是否相同，如果相同，后一个对象就不能再添加，万一返回false呢，则都存储在"同一个位置"。
单线程：
1.HashMap （数组 + 链表+红黑树 ，null ok）
问题：HashMap get() / put()的工作原理？
存储过程：
0.hash(key.hashCode()) 充分使用key的hashCode值的前16位和后16位 “&”操作 得到一个 int hash值
1.判断table是否为null,是就扩容
2.这个hash值 & (数组Size -1 ) , 得出找到要放在桶上的索引，如果这个位置上没值，就保存key -value，
3.如果索引位置上有值，再equalse(）判断是否相等，如果相等，就覆盖old value
4. 如果索引位置上的值和插入的值不相等，就检查这个节点是不是treeNode，如果是就红黑树插入key-value ，这里依然要equals(），如果相等就 覆盖 old value
5. 如果不是红黑树，那么遍历他的链表，遍历的过程中做两件事 1.检查是否遍历到了链表的尾端，如果是就插入到尾端检查这个时候链表的长度是否是8，是的话 ，(判断数组的length如果大于64，就把链表转化为红黑树，小于64就扩容) 2.equals()于当前链上结点是否相等，相等就跳出遍历，覆盖old valueB
6.覆盖了old value会返回old value ， 没有覆盖就modCount +1 ,检查是否需要扩容
get() 过程：
1. hash(key.hashCode()) & (table.length -1) 找到索引，桶的位置
2.索引上没有值，返回null , 桶上有值equals() 相等，返回;
3.不等就看这个节点是不是treeNode，是就查找equals()，true返回值，false 就返回null
4.不是treeNode ， 就查看这个有没有next个节点链，遍历，equals()，同上。
问题：HashMap中解决碰撞的方法？
首先知道几个数字 ：
16 ： capacity 默认数组的长度 , 不默认就2的幂次方，减少碰撞。
8：当值插入值后链表长度变成 8 就把链表变为红黑树,或者扩容
扩容相关参数
0.75：final loadFactor 负载因子，当添加key-value之后 ， 检查当前的容量 size 是否达到了threshold（capacity*loadFactor）阈值，达到了就扩容。至于为什么是0.75呢？javadoc上说，0.75满足泊松分布。
64: final，最小转变为红黑树的这个一个阈值： 在链表转红黑树中 ， 如果map中table 的长度没有达到这个值，就会通过扩容解决冲突，并不会链表转红黑树
总结：这个如何解决冲突，就是在桶后面加了一个链表，为了解决链表过长查找效率变为O(n）,链表过长变为红黑树查找效率变为O(logN)
问题：HashMap的扩容？
扩容就是变成原来table.length的两倍，这样的好处，关于整体结构上的动荡，这个值，要不就在 原来的索引上，要不就在原来的索引+原来table.length处。多线程扩容会产生循环链表，引起死锁，让Cpu的使用率变成100%
继承HashMap的LinkedHashMap：
就是在HashMap的基础上，加了双向链表，维护了一个顺序，默认是插入的顺序，可以用过构造方法指定accessOrder为true, 然后重写LinkedHashMap中的removeEldestEntry方法 这样维护的是LRU（最近最久未使用淘汰）顺序。
问题：如何维护顺序问题？
LinkedHashMap 继承HashMap之后重写了三个钩子方法，用着三个方法来维护一个顺序问题
2.TreeMap（红黑树）
自定义key的排序 ，在数量级很大的情况下使用TreeMap。关于key为null的问题 ， 可以put存储,如果get读的时候回报错NullPointerException异常，但是可以遍历，迭代器读取
多线程安全：
1.Hashtable : （不允许key为 null）加synchronized 关键字实现同步方法 .
2.Collections.synchronizedMap() /synchronizedSortedMap()
3.ConcurrentHashMap ( 数据类型和HashMap一样，不能为null ) :
volatile table ， CAS方法一些状态值的维护或者插入 ， synchronized（node），三个原子操作
问题：put() / get()的工作原理？HashMap有什么不一样呢 ？
put()
0.这里写了循环，只有插入成功才会返回。
1.判断当桶上是不是有值 ，CAS插入值，插入成功就返回，有值之后先判断是否有其他线程是否在扩容，是就帮助扩容，没有扩容就接着插入。
2.加锁的粒度不是整个这个方法，加锁是在node结点上，这个时候synchronized(当前这个桶)，下面和HashMap一样，是链表就插在链表后面（这个之后要判断链表长度是否大于8，当前table.length是否大于64，是就转变为红黑树），是红黑树就按照红黑树插入。
3.插入之后判断是否要扩容
问题：关于扩容的问题？很难
在ConcurrentHashMap里，sizeCtl承担map扩容的问题，并增加了一点功能。
当sizeCtl=-1，代表正在初始化。
当sizeCtl=-N，代表有N-1个线程在扩容。
当sizeCtl=0，代表需要初始化。
以上三个值，都是状态位。
当sizeCtl>0，即扩容的阈值，也即总容量 * 0.75。
多线程扩容，每个线程都扩容自己分到的桶，扩容完成后把node结点变为ForwardingNode，通知其他线程这个桶已经扩容完毕，并且设置桶上hash值为 MOVED
问题：ConcurrentHashMap的弱一致性问题？
如果有线程遍历，这个时候有线程做修改数据结构的事情？
在使用迭代器时，如果修改的部分发生在还没有迭代的地方，就会显示出来，如果迭代在已经迭代的地方就不会显示出来
问题：ConcurrentHashMap并行度？
读完全并行。
写部分并行，因为synchronized的是桶上的node , 所以table的length有多少，并行度就是多少。
迭代器
3.ConcurrentSkipListMap :
ConcurrentHashMap是HashMap的 多线程版本，ConcurrentSkipListMap是TreeMap的多线程版本，对key有一个排序。
无阻塞，所有的操作都是并行的 ， 跳表基于链表 ， 这个结构查找类似二分查找。这个以后再写
3.关于Set
1.无序（存储位置 根据Hash值），他和list一样都继承Collection.Class
2.不可重复
单线程：
HashSet , TreeSet 这些类各自实现 HashMap ， TreeMap，以其中的key保存自己的值，value是一个默认的值。
线程安全：
1.Collections.synchronizedSet
2.CopyOnWriteArraySet()
同CopyOnWriteArrayList一样, 使用volatile 数组 + lock +写时复制 ，实现线程安全。
网友评论