线程不安全问题

当多线程并发访问同一个资源时，容易出现不安全问题                                                      有时候我们分析打印结果，发现没有问题，但是并不是真的没问题，可能我们经验不够，没有发现问题。为了放大问题是用Thread中的sleep（）方法

Thread.sleep(100);  //是当前线程睡眠100毫秒，让其他线程去抢资源，经常用来模拟网络延迟。放大线程中的问题。

解决方法：

（1）同步代码块

（2）同步方法

（3）锁机制（Lock）

1.同步代码块

synchronized( 同步锁){    //同步锁：同步监听对象/ 同步监听器 /互斥锁

需要同步操作的代码

}

对象的同步锁只是一个概念，可以想象在对象上标记 一个锁

java程序运行可以使用任何对象作为同步监听对象，但是一般我们将当前i并发访问的共同资源（多个线程同步共享的资源对象）作为同步监听对象。

注意：在任何时候，只允许一个线程拥有同步锁，谁拿到锁就进入代码块，其他线程只能在外面等

2.同步方法

使用synchronized修饰的方法叫做同步方法，保证该线程执行该方法的时候，其他线程只能等着。

同步锁：1.非static方法，同步锁是this。2.static方法，使用当前方法所在类的字节码对象（Apple.class）是同步锁

注意：

synchronized不能修饰run方法，修饰之后，一个线程就执行了所有的功能，线程出现串行，相当于单线程。

解决方法：将需要同步的 代码定义在一个新的方法中，并且该方法用synchronized修饰，再在run方法中调用该新的方法即可

synchronized提高安全性，但是性能降低了，使用时尽量减小它的作用域。eg:stringBuffer和StringBuilder的区别，stringBuffer的方法全都加了synchronized修饰。

类似的还有：ArrayList和vector  HashMap和Hashtable  一般选择使用性能比较高的。

**单例模式-懒加载同步

一般懒汉式

优化懒汉式

饿汉式

结论：单例模式使用  饿汉式；简单粗暴。

3.锁机制（Lock）

Lock是一个接口，实现提供更广泛的锁定操作可以比使用synchronized获得方法和报表。

锁是一种通过多个线程控制对共享资源的访问的工具。通常，一个锁提供对共享资源的独占访问：在一个时间只有一个线程可以获得锁和所有访问共享资源，需要先获得锁。

jdk1.8中HashMap为什么线程不安全？

会出现数据覆盖。
JDK1.7和JDK1.8中HashMap为什么是线程不安全的？

怎么解决HashMap线程不安全的问题？

1.使用HashTable替代HashMap

HashTable的put操作，有synchronized关键字修饰。

2.使用Map map = Collections.synchronizedMap(new HashMap());

这个方法实际上返回了一个SynchronizedMap。

SynchronizedMap 实现线程安全的方法也是比较简单的，所有方法都是先对锁对象 mutex 上锁，然后再直接调用 Map 类型成员变量 m 的相关方法。这样一来，线程在执行方法时，只有先获得了 mutex 的锁才能对 m 进行操作。因此，跟 Hashtable 一样，在同一个时间点，只能有一个线程对 SynchronizedMap 对象进行操作，虽然保证了线程安全，却导致了性能低下。这么看来，连 Hashtable 都被弃用了，那性能同样低下的 SynchronizedMap 还有什么存在的必要呢？别忘了，后者的构造方法需要传入一个 Map 类型的参数，也就是说它可以将非线程安全的 Map 转化为线程安全的 Map。

上面这段话出自： Hashtable，SynchronizedMap和ConcurrentHashMap线程安全对比
看看这个类的源码：

    public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
       return new SynchronizedMap<>(m);
  	 }
  	 
   private static class SynchronizedMap<K,V>
       implements Map<K,V>, Serializable {
       private static final long serialVersionUID = 1978198479659022715L;

       private final Map<K,V> m;     // Backing Map
       final Object      mutex;        // Object on which to synchronize

       SynchronizedMap(Map<K,V> m) {
           this.m = Objects.requireNonNull(m);
           mutex = this;
       }
       ...
   }
  
   	   //SynchronizedMap的put方法，实际调用的还是HashMap自己的put方法
      public V put(K key, V value) {
           synchronized (mutex) {return m.put(key, value);}
       }

3.使用ConcurrentHashMap

jdk1.8中ConcurrentHashMap通过 CAS+synchronized实现线程安全。
Java并发——ConcurrentHashMap(JDK 1.8）

一、为什么HashMap线程不安全？

原著参考

1、JDK1.7 扩容引发的死循环和数据丢失

（1）.当前jdk1.7版本的HashMap线程不安全主要是发生在扩容函数中，其中调用了HshMap的transfer()方法

//jdk 1.7的transfer方法，HashMap的扩容操作
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

在执行数组扩容操作时，数据会重新定位新数组中索引，并采用头插法将元素迁移到新数组中。头插法会将链表的顺序翻转，这也是形成死循环的关键点。如何造成死循环以及数据丢失的。

（2）、数组扩容时如何造成死循环和数据丢失？

我们假设现在有两个线程A、B同时对下面这个HashMap进行扩容操作：

正常扩容后的结果

但是当线程A执行到上面transfer函数的第11行代码时，CPU时间片耗尽，线程A被挂起。即如下图中位置所示：

此时线程A中：e=3、next=7、e.next=null

当线程A的时间片耗尽后，CPU开始执行线程B，并在线程B中成功的完成了数据迁移

根据JMM可知，线程B执行完数据迁移后，此时主内存中newTable和table都是最新的，也就是说：7.next=3、3.next=null

随后线程A再次获得CPU时间片继续执行newTable[i] = e，将3放入新数组对应的位置，执行完此轮循环后线程A的情况如下：

接着继续执行下一轮循环，此时e=7，从主内存中读取e.next时发现主内存中7.next=3，此时next=3，并将7采用头插法的方式放入新数组中，并继续执行完此轮循环，结果如下：

上轮7.next=3，而e=3，执行下一次循环可以发现，3.next=null，所以此轮循环将会是最后一轮循环。

接下来当执行完e.next=newTable[i]即3.next=7后，3和7之间就相互连接了，当执行完newTable[i]=e后，3被头插法重新插入到链表中，执行结果如下图所示：

此时e.next=null即next=null，当执行完e=null后，将不会进行下一轮循环。到此线程A、B的扩容操作完成，很明显当线程A执行完后，HashMap中出现了环形结构，当在以后对该HashMap进行操作时会出现死循环。同时元素5在扩容期间，发生了数据丢失的问题。

2、JDK1.8中的数据覆盖

（1）dk1.7的数据丢失、死循环问题在JDK1.8中已经得到了很好的解决，直接在HashMap的resize()中完成了数据迁移。

（2）为什么说 JDK1.8会出现数据覆盖的情况？
查看这段JDK1.8中的put操作代码：

如下图框中的代码是判断是否出现hash碰撞，假设两个线程A、B都在进行put操作，并且hash函数计算出的插入下标是相同的，当线程A执行完该行判断代码后由于时间片耗尽导致被挂起，而线程B得到时间片后在该下标处插入了元素，完成了正常的插入，然后线程A获得时间片，由于之前已经进行了hash碰撞的判断，所有此时不会再进行判断，而是直接进行插入，这就导致了线程B插入的数据被线程A覆盖了，从而线程不安全。

除此之外，下图pullVal方法中还有框中代码的有个++size语句，如果还是线程A、B，这两个线程同时进行put操作时，假设当前HashMap的size大小为10，当线程A执行到第38行代码时，从主内存中获得size的值为10后准备进行+1操作，但是由于时间片耗尽只好让出CPU，线程B快乐的拿到CPU还是从主内存中拿到size的值10进行+1操作，完成了put操作并将size=11写回主内存，然后线程A再次拿到CPU并继续执行(此时size的值仍为10)，当执行完put操作后，还是将size=11写回内存，此时，线程A、B都执行了一次put操作，但是size的值只增加了1，所有说还是由于数据覆盖又导致了线程不安全。

二、HashMap线程安全的解决方案

1.Hashtable（废弃）

不建议使用HashTable，Oracle官方也将其废弃，建议在多线程环境下使用ConcurrentHashMap类。

（1）Hashtable的操作
HashTable的操作几乎和HashMap一致，主要的区别在于HashTable为了实现多线程安全，在几乎所有的方法上都加上了synchronized锁（锁的是类的实例,也就是整个map结构），当一个线程访问 Hashtable 的同步方法时，其他线程如果也要访问同步方法，会被阻塞住。举个例子，当一个线程使用 put 方法时，另一个线程不但不可以使用 put 方法，连 get 方法都不可以，而加锁的结果就是HashTable操作的效率十分低下。

（2）HashTable与HashMap对比
①线程安全
HashMap是线程不安全的类，多线程下会造成并发冲突，但单线程下运行效率较高;
HashTable是线程安全的类，很多方法都是用synchronized修饰，但同时因为加锁导致并发效率低下，单线程环境效率也十分低；

②插入null
HashMap最多允许有一个键为null，允许多个值为null；
HashTable不允许键或值为null；

③容量
HashMap底层数组长度必须为2的幂（16，32，128…），这样做是为了hash准备，默认为16；
HashTable底层数组长度可以为任意值，这就造成了hash算法散射不均匀，容易造成hash冲突，默认为11；

④Hash映射
HashMap的hash算法通过非常规设计，将底层table长度设计为2的幂，使用位与运算代替取模运算，减少运算消耗；

// HashMap
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 下标index运算
int index = (table.length - 1) & hash(key)

HashTable的hash算法首先使得hash值小于整型数最大值，再通过取模进行散射运算；

// HashTable
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

⑤扩容机制
HashMap创建一个为原先2倍的数组，然后对原数组进行遍历以及rehash(再次求桶)；
HashTable扩容将创建一个原长度2倍的数组，再使用头插法将链表进行反序；

⑥结构区别
HashMap是由数组+链表形成，在JDK1.8之后链表长度大于8时转化为红黑树；
HashTable一直都是数组+链表；

⑦继承关系
HashTable继承自Dictionary类；
HashMap继承自AbstractMap类；

⑧迭代器
HashMap的 Iterator 迭代器是fail-fast；

fail-fast（快速失败机制）：当我们在遍历集合元素的时候，经常会使用迭代器，但在迭代器遍历元素的过程中，如果集合的结构被修改（增加、删除），就会抛出Concurrent Modification Exception（并发修改异常），防止继续遍历。

fail-safe（安全失败机制）：当集合的结构被改变的时候，fail-safe机制会在复制原集合的一份数据出来，然后在复制的那份数据遍历。因此，fail-safe不会抛出异常，但存在以下缺点：①复制时需要额外的空间和时间上的开销。②不能保证遍历的是最新内容。

HashTable的 Enumerator不是。

2.Collections.synchronizedMap(一般不用)

通过Collections.synchronizedMap()返回一个新的Map的实现

Map<String,String> map = Collections.synchronizedMap(new HashMap<>());

我们在调用上面这个方法的时候就需要传入一个Map，如下图可以看到有两个构造器，如果你传入了mutex参数，则将对象排斥锁赋值为传入的对象。
如果没有，则将对象排斥锁赋值为this，即调用synchronizedMap的对象，就是上面的Map

通过Collections.synchronizedMap()来封装所有不安全的HashMap的方法。

封装的关键点有2处
1 )使用了经典的synchronized来进行互斥
2)使用了代理模式new了一个新的类，这个类同样实现了Map接口.在Hashmap上面,synchronized锁住的是对象,所以第一个申请的得到锁，其他线程将进入阻塞,等待唤醒

优点:代码实现十分简单,一看就懂

缺点:从锁的角度来看，基本上是锁住了尽可能大的代码块.性能会比较差.

3.ConcurrentHashMap（常用）

(1）JDK 1.7 中，采用分段锁的机制，实现并发的更新操作，底层采用数组+链表的存储结构，包括两个核心静态内部类 Segment 和 HashEntry。
　　　　①、Segment 继承 ReentrantLock（重入锁） 用来充当锁的角色，每个 Segment 对象守护每个散列映射表的若干个桶；
　　　　②、HashEntry 用来封装映射表的键-值对；
　　　　③、每个桶是由若干个 HashEntry 对象链接起来的链表

分段锁：Segment数组中，一个Segment对象就是一把锁,对应一个HashEntry数组,该数组中的数据同步依赖于同一把锁,不同HashEntry数组的读写互不干扰

jdk 1.7源码分析
ConcurrentHashMap继承了AbstractMap类，并且实现了ConcurrentMap接口，并且线程安全的实现了接口中的增删改查的方法

ConcurrentMap接口中的方法声明

ConcurrentMap中的静态变量

ConcurrentMap中的成员变量

静态内部类HashEntry

静态内部类Segment

静态内部类Segment-成员方法

ConcurrentHashMap的构造器

put方法

调用segment的put方法，首先第一步的时候会尝试获取锁，如果获得锁则node=null

获取失败肯定就有其他线程存在竞争，则利用 scanAndLockForPut() 自旋获取锁

扩容操作，在concurrentHashMap中是被保护的

当 put 方法时，发现元素个数超过了阈值，则会扩容。需要注意的是，每个Segment只管它自己的扩容，互相之间并不影响,只要是2的n次幂）。

get 方法的逻辑，需要将 Key 通过 Hash 之后定位到具体的 Segment ，再通过一次 Hash 定位到具体的元素上
由于 HashEntry 中的 value 属性是用 volatile 关键词修饰的，保证了内存可见性，所以每次获取时都是最新值。

缺点：jdk1.7版本虽然可以支持每个Segment并发访问，但是基本上还是数组加链表的方式，当执行查询的时候，还得遍历链表，会导致效率很低.

（2）JDK 1.8中抛弃了原有的 Segment 分段锁，来保证采用Node + CAS + Synchronized来保证并发安全性。取消类 Segment，直接用table 数组存储键值对；当 Node对象组成的链表长度超过TREEIFY_THRESHOLD 时，链表转换为红黑树，提升性能。底层变更为数组 + 链表 + 红黑树。

首先Node代替了1.7之中的HashEntry，并在val和next添加了volatile，保证了原子的可见性，也引入了红黑树，在链表大于一定值的时候会转换（默认是8）。

ConcurrentHashMap的put方法

CAS以及ABA问题

CAS性能很高，但synchronized之前一直都是重量级的锁，jdk1.8 引入了synchronized，采用锁升级的方式。

针对 synchronized 获取锁的方式，JVM 使用了锁升级的优化方式，就是先使用偏向锁优先同一线程然后再次获取锁，如果失败，就升级为 CAS 轻量级锁，如果失败就会短暂自旋，防止线程被系统挂起。最后如果以上都失败就升级为重量级锁。

偏向锁：为了在无多线程竞争的情况下尽量减少不必要的轻量级锁执行，始终只有一个线程在执行同步块，在它没有执行完释放锁之前，没有其它线程去执行同步。
轻量级锁：当有两个线程，竞争的时候就会升级为轻量级锁。引入轻量级锁的主要目的是在没有多线程竞争的前提下，减少传统的重量级锁使用操作系统互斥量产生的性能消耗。
重量级锁：大多数情况下，在同一时间点，常常有多个线程竞争同一把锁，悲观锁的方式，竞争失败的线程会不停的在阻塞及被唤醒态之间切换，代价比较大

ConcurrentHashMap的get方法