ARTS_WEEK13

这周算法方面学习到了二叉树结构，关于二叉树基本上都是递归。有两个方式DFS与BFS，视频方面主要是更深度多线程知识ThreadLocal相关，以及lock锁。

算法：
- 二叉树
- DFS（Deep First Search）深度优先
- BFS（Breath First Search）广度优先
多线程：
- ThreadLocal
- lock
  - 非公平锁与公平锁
设计模式
- 解决并发相关设计模式
  1. although
  
  1.1. 细胞分裂算法题
  
  1.2. 链表实现二分查找数

package com.myserious.code.cdz.althoughexpand;

/**
 * 链表实现二分查找数
 * <p>
 * 约定：
 * 二分查找树：
 * 任何一个节点，
 * 其左节点全部节点都比其小
 * 其右节点全部节点都比其大
 */
public class Week13BinarySearchTreeLinked {

    private TreeNode root;

    private int size;


    public void add(int v) {

        TreeNode node = new TreeNode(v);
        if (root == null) {
            root = node;
            return;
        }

        TreeNode r = root;

        while (r != null) {
            if (r.val > v) {
                //需要添加带左子节点
                if (r.left != null) {
                    r = r.left;
                } else {
                    r.left = node;
                    break;
                }
            } else {
                //需要添加带右子节点
                if (r.right != null) {
                    r = r.right;
                } else {
                    r.right = node;
                    break;
                }
            }
        }
        this.size++;

    }


    /**
     * 分三种情况
     * 1 没有子节点，直接将其节点置为Null（从父节点上）
     * <p>
     * 2 有一个子节点，直接子节点与之替换
     * <p>
     * 3 有两个节点，找到右节点中最小左节点，与之替换
     *
     * @param v
     */
    public void delete(int v) {
        //先找到 v节点
        TreeNode p = root;

        TreeNode pp = null;//前置父节点

        while (p!=null&&p.val!=v){
            pp = p;
            if (p.val>v){
                p = p.left;
            }else {
                p = p.right;
            }
        }
        if (p==null) return;

        if (p.left!=null&&p.right!=null){
            //有两个节点，找到右节点中最小左节点，与之替换
            TreeNode rmin = p.right;
            TreeNode prmin = p;

            //右节点中最小左节点
            while (rmin.left!=null){
                prmin = rmin;
                rmin = rmin.left;
            }
            prmin.left = null;
            p.val = rmin.val;
        }

        TreeNode child;
        if (p.left!=null){
            child = p.left;
        }else if (p.right!=null){
            child = p.right;
        }else {
            child = null;
        }

        if (pp==null) {
            //删除的根节点
            root = child;
        }else if (pp.right==p){
            pp.right = child;
        }else {
            pp.left = child;
        }

        this.size--;
    }

    public boolean contains(int v) {
        return findVal(v) != null;
    }

    private TreeNode findVal(int v) {
        TreeNode r = root;
        while (r != null) {
            if (r.val == v) {
                return r;
            } else if (r.val > v) {
                r = r.left;
            } else {
                r = r.right;
            }
        }
        return null;
    }

    public int getSize() {
        return this.size;
    }

    public static void main(String[] args) {
        Week13BinarySearchTreeLinked searchTreeLinked = new Week13BinarySearchTreeLinked();
        searchTreeLinked.add(1);
        searchTreeLinked.add(10);
        searchTreeLinked.add(2);
        searchTreeLinked.add(12);
        System.out.println(searchTreeLinked.contains(1));
        System.out.println(searchTreeLinked.contains(2));
        searchTreeLinked.delete(2);
        System.out.println(searchTreeLinked.contains(2));
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
}

1.3. LeetCode

1.3.1. 二叉树的直径

/**
 * 543. 二叉树的直径
 * 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
 *
 * 示例 :
 * 给定二叉树
 *
 *           1
 *          / \
 *         2   3
 *        / \
 *       4   5
 * 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
 *
 * 注意：两结点之间的路径长度是以它们之间边的数目表示
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/diameter-of-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Week13EDiameterOfBinaryTree543 {
    /**
     * 直径 也可以等价于层数！？错误理解
     *
     * 关键点：最长路径有可能不经过root
     *
     * 最长路径可以拆分成：
     * node的最长路径= node.left的最长路径+node.right的最长路径 + 1
     *
     * @param root
     * @return
     */
    int ans;
    public int diameterOfBinaryTree(TreeNode root) {
        ans = 1;
        depth(root);
        return ans-1;
    }

    private int depth(TreeNode root) {
        if (root==null)return 0;

        int R = depth(root.right);
        int L = depth(root.left);

        ans = Math.max(ans,R+L+1);

        //返回的是，加本节点，的单边最多数量。
        //所以长度就需要减一
        return Math.max(R,L)+1;
    }
}

1.3.2. 路径总和

/**
 * 112. 路径总和
 * 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
 * <p>
 * 说明: 叶子节点是指没有子节点的节点。
 * <p>
 * 示例: 
 * 给定如下二叉树，以及目标和 sum = 22，
 * <p>
 * 5
 * / \
 * 4   8
 * /   / \
 * 11  13  4
 * /  \      \
 * 7    2      1
 * 返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/path-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Week13EHasPathSum112 {
    /**
     * root节点开始 左右分别计算，如果有值相等sum的就返回
     * @param root
     * @param sum
     * @return
     */
    public boolean hasPathSum(TreeNode root, int sum) {

        if (root==null){
            return false;
        }

        sum-=root.val;
        if (root.left==null&&root.right==null){
            return sum==0;
        }

        return hasPathSum(root.left,sum)||hasPathSum(root.right,sum);
    }
}

1.3.3. 翻转二叉树

/**
 * 226. 翻转二叉树
 * <p>
 * <p>
 * 翻转一棵二叉树。
 * <p>
 * 示例：
 * <p>
 * 输入：
 * <p>
 * 4
 * /   \
 * 2     7
 * / \   / \
 * 1   3 6   9
 * 输出：
 * <p>
 * 4
 * /   \
 * 7     2
 * / \   / \
 * 9   6 3   1
 * 备注:
 * 这个问题是受到 Max Howell 的 原问题 启发的 ：
 * <p>
 * 谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。
 */

public class Week13EInvertTree226 {
    public TreeNode invertTree(TreeNode root) {

        depth(root);
        return root;
    }

    private void depth(TreeNode root) {
        if (root == null) return;

        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        depth(root.left);
        depth(root.right);
    }
}

1.3.4. 平衡二叉树

/**
 * 110. 平衡二叉树
 * <p>
 * 给定一个二叉树，判断它是否是高度平衡的二叉树。
 * <p>
 * 本题中，一棵高度平衡二叉树定义为：
 * <p>
 * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
 * <p>
 * 示例 1:
 * <p>
 * 给定二叉树 [3,9,20,null,null,15,7]
 * <p>
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 * 返回 true 。
 * <p>
 * 示例 2:
 * <p>
 * 给定二叉树 [1,2,2,3,3,null,null,4,4]
 * <p>
 * 1
 * / \
 * 2   2
 * / \
 * 3   3
 * / \
 * 4   4
 * 返回 false 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/balanced-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Week13EIsBalanced110 {
    /**
     * 置顶向下 暴力破解
     *
     * 把每个节点当做父节点，那左右两边去计算器左右子树的高度差。
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        if (root==null){
            return true;
        }
        return Math.abs(depth(root.left)-depth(root.right))<=1
                &&isBalanced(root.left)&&isBalanced(root.right);
    }

    private int depth(TreeNode node) {
        if (node==null) return 0;
        return Math.max(depth(node.left),depth(node.right))+1;
    }


    /**
     * 自底向上
     *
     * 将每个节点当做是子节点，标记是否为平衡和子节点的高度
     * 然后根据子节点 再去判断父节点
     *
     * 理论上来说这个会更好一些，但是上面暴力破解在极度不平衡下，其实遍历的次数少。
     * @param root
     * @return
     */
    public boolean isBalanced1(TreeNode root) {

        TreeInfo treeInfo =  isBalancedHelper(root);
        return treeInfo.balance;

    }

    private TreeInfo isBalancedHelper(TreeNode root) {

        if (root==null)return new TreeInfo(0,true);

        TreeInfo lt = isBalancedHelper(root.left);
        if (!lt.balance){
            return new TreeInfo(-1,false);
        }
        TreeInfo rt = isBalancedHelper(root.right);
        if (!rt.balance){
            return new TreeInfo(-1,false);
        }

        if (Math.abs(lt.hight-rt.hight)<2){
            //返回的是父节点的信息 所以+1
            return new TreeInfo(Math.max(lt.hight,rt.hight)+1,true);
        }
        return new TreeInfo(-1,false);
    }

    class TreeInfo{
        protected int hight;
        protected boolean balance;

        public TreeInfo(int hight, boolean balance) {
            this.hight = hight;
            this.balance = balance;
        }
    }


}

1.3.5. 二叉树的最大深度

/**
 * 104. 二叉树的最大深度
 * <p>
 * 给定一个二叉树，找出其最大深度。
 * <p>
 * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
 * <p>
 * 说明: 叶子节点是指没有子节点的节点。
 * <p>
 * 示例：
 * 给定二叉树 [3,9,20,null,null,15,7]，
 * <p>
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 * 返回它的最大深度 3 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Week13EMaxDepth104 {

    /**
     * DFS深度优先
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        if (root==null){
            return 0;
        }else {
            int l = maxDepth(root.left);
            int r = maxDepth(root.right);
            return Math.max(l,r)+1;
        }
    }


    /**
     * BFS广度优先
     *
     * 按层次来算出
     *
     * 需要借助队列实现
     * @param root
     * @return
     */
    public int maxDepth1(TreeNode root) {

        LinkedList<TreeNode> list = new LinkedList<>();
        if (root!=null){
            list.add(root);
        }
        int d = 0;
        while (!list.isEmpty()){
            d++;
            int size = list.size();
            for (int i = 0; i < size; i++) {
                TreeNode treeNode = list.pollFirst();
                if (treeNode.left!=null){
                    list.add(treeNode.left);
                }
                if (treeNode.right!=null){
                    list.add(treeNode.right);
                }
            }
        }
        return d;
    }

    /**
     * DFS前序遍历
     *
     * 先本身
     * 后左子
     * 最后右子
     * @param root
     * @return
     */
    public int maxDepth2(TreeNode root){
        LinkedList<Pair<TreeNode, Integer>> stack = new LinkedList<>();

        if (root!=null){
            stack.push(new Pair<>(root,1));
        }

        int d = 0;

        while (!stack.isEmpty()){

            Pair<TreeNode, Integer> pair = stack.pop();
            TreeNode key = pair.getKey();
            Integer value = pair.getValue();
            d = Math.max(d,value);

            if (key.right!=null){
                stack.push(new Pair<>(key.right,value+1));
            }
            if (key.left!=null){
                stack.push(new Pair<>(key.left,value+1));
            }
        }
        return d;
    }




    public static void main(String[] args) {
        Week13EMaxDepth104 maxDepth104 = new Week13EMaxDepth104();

        TreeNode treeNode = new TreeNode(10);
        treeNode.left = new TreeNode(1);
        treeNode.right = new TreeNode(2);
        treeNode.left.left = new TreeNode(3);
        treeNode.left.right = new TreeNode(4);
        treeNode.left.left.left = new TreeNode(5);
        treeNode.left.left.left.right = new TreeNode(5);

        System.out.println(maxDepth104.maxDepth2(treeNode));
    }

}

1.3.6. 合并二叉树

/**
 * 617. 合并二叉树
 * <p>
 * 给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
 * <p>
 * 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
 * <p>
 * 示例 1:
 * <p>
 * 输入:
 * Tree 1                     Tree 2
 * 1                         2
 * / \                       / \
 * 3   2                     1   3
 * /                           \   \
 * 5                             4   7
 * 输出:
 * 合并后的树:
 * 3
 * / \
 * 4   5
 * / \   \
 * 5   4   7
 * 注意: 合并必须从两个树的根节点开始。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/merge-two-binary-trees
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Week13EMergeTrees617 {

    /**
     * 递归方式
     *
     * @param t1
     * @param t2
     * @return
     */
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {

        if (t1 == null) {
            return t2;
        } else if (t2 == null) {
            return t1;
        }
        t1.val = t2.val + t1.val;
        t1.right = mergeTrees(t1.right, t2.right);
        t1.left = mergeTrees(t1.left, t2.left);

        return t1;
    }

    /**
     * 迭代方式
     *
     * @param t1
     * @param t2
     * @return
     */
    public TreeNode mergeTrees1(TreeNode t1, TreeNode t2) {

        if (t1==null){
            return t2;
        }
        Stack<TreeNode[]> stack = new Stack<>();

        stack.push(new TreeNode[]{t1,t2});

        while (!stack.isEmpty()) {

            TreeNode[] pop = stack.pop();

            TreeNode tn1 = pop[0];
            TreeNode tn2 = pop[1];
            if (tn1==null||tn2==null){
                continue;
            }

            tn1.val = tn1.val+tn2.val;

            if (tn1.left==null){
                tn1.left = tn2.left;
            }else {
                stack.push(new TreeNode[]{tn1.left,tn2.left});
            }

            if (tn1.right==null){
                tn1.right = tn2.right;
            }else {
                stack.push(new TreeNode[]{tn1.right,tn2.right});
            }
        }


        return t1;
    }


}

1.3.7. 路径总和 III

/**
 * 437. 路径总和 III
 * <p>
 * 给定一个二叉树，它的每个结点都存放着一个整数值。
 * <p>
 * 找出路径和等于给定数值的路径总数。
 * <p>
 * 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
 * <p>
 * 二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
 * <p>
 * 示例：
 * <p>
 * root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
 * <p>
 * 10
 * /  \
 * 5   -3
 * / \    \
 * 3   2   11
 * / \   \
 * 3  -2   1
 * <p>
 * 返回 3。和等于 8 的路径有:
 * <p>
 * 1.  5 -> 3
 * 2.  5 -> 2 -> 1
 * 3.  -3 -> 11
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/path-sum-iii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Week13EPathSum437 {

    /**
     * 深度遍历，每次下行相加都与num值做比较如果相等就累加
     * <p>
     * 每个节点都要当做根节点来遍历
     *
     * @param root
     * @param sum
     * @return
     */
    public int pathSum(TreeNode root, int sum) {

        if (root == null) {
            return 0;
        }

        return path(root, sum)
                //每个节点都要当做根节点来遍历
                + pathSum(root.left, sum)
                + pathSum(root.right, sum);
    }

    private int path(TreeNode root, int sum) {

        if (root == null) return 0;

        int count = 0;
        if (root.val == sum) {
            count+=1;
        }
        count += path(root.left, sum - root.val);
        count += path(root.right, sum - root.val);
        return count;
    }
}

2. review

3. tip

3.1. 图解公平锁与非公平锁

公平锁与非公平锁

3.2. 图解ThreadLocal结构

ThreadLocal结构

4.1. 设计模式

4.1.1. 并发相关设计模式：不变性（Immutability）模式

使用设计模式避免并发问题。

Immutability(不变性)模式：并发问题的先决条件是，变量的被多个线程读与写，如果只被读不被写那么就不会有线程安全问题。也就是说，一旦被创建就不能改变其状态。（String、Long…）

如何快速的实现不可变限制？使用final修饰，类与变量都使用final修饰。

问题，会导致频繁的创建对象，占用内存。解决：使用享元模式（对象池）(Long、Integer类都有缓存)

不变性（Immutability）模式使用注意事项：

对象所有属性都要使用final修饰，并且保证不可变
不可变对象也需要正确发布
使用不可变性模式时，一定要注意，不可变的边界在哪里，是否要求属性对象也具备不可变性

4.1.2. 并发相关设计模式：线程封闭

使用ThreadLocal来做到线程内部，独享变量。

4.1.3. 并发相关设计模式：Copy-on-Write模式

Copy-on-Write模式：适用于，多读少些的情况。

本质：并发发生在写上，只读的（并发相关设计模式：不变性（Immutability）模式）话是不会有并发问题，所以特别在写上做文章。

也就是写时复制。

这个复制的意思其实很广泛，经常会配合并发相关设计模式：不变性（Immutability）模式一起使用，也就是说，当有修改时，直接覆盖掉久有的。

截取一段CopyOnWriteArrayList的set代码：

public E set(int index, E element) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        E oldValue = get(elements, index);


        if (oldValue != element) {
            int len = elements.length;
            //当需要更新一个元素时，直接复制一份原有对象，进行覆盖。
            Object[] newElements = Arrays.copyOf(elements, len);
            newElements[index] = element;
            setArray(newElements);
        } else {
            // Not quite a no-op; ensures volatile write semantics
            setArray(elements);
        }
        return oldValue;
    } finally {
        lock.unlock();
    }
}

4.2. 线程池

4.2.1. 钩子函数拓展——线程池

使用线程池的钩子函数，拓展一个线程池能力，使其有暂停功能。

其实这个设计模式，钩子函数拓展——LinkedHashMap设计LRU缓存有异曲同工之妙。

package com.myserious.code.cdz.thread.threadpool;


import java.util.concurrent.*;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;


public class PauseThreadPool extends ThreadPoolExecutor {


    public PauseThreadPool(int corePoolSize, int maximumPoolSize, long keepAliveTime, TimeUnit unit, BlockingQueue<Runnable> workQueue) {
        super(corePoolSize, maximumPoolSize, keepAliveTime, unit, workQueue);
    }


    public PauseThreadPool(int corePoolSize, int maximumPoolSize, long keepAliveTime, TimeUnit unit, BlockingQueue<Runnable> workQueue, ThreadFactory threadFactory) {
        super(corePoolSize, maximumPoolSize, keepAliveTime, unit, workQueue, threadFactory);
    }


    public PauseThreadPool(int corePoolSize, int maximumPoolSize, long keepAliveTime, TimeUnit unit, BlockingQueue<Runnable> workQueue, RejectedExecutionHandler handler) {
        super(corePoolSize, maximumPoolSize, keepAliveTime, unit, workQueue, handler);
    }


    public PauseThreadPool(int corePoolSize, int maximumPoolSize, long keepAliveTime, TimeUnit unit, BlockingQueue<Runnable> workQueue, ThreadFactory threadFactory, RejectedExecutionHandler handler) {
        super(corePoolSize, maximumPoolSize, keepAliveTime, unit, workQueue, threadFactory, handler);
    }




    private boolean isPaused;
    private Lock lock = new ReentrantLock();


    private Condition condition = lock.newCondition();

    //重写关键的函数
    @Override
    protected void beforeExecute(Thread t, Runnable r) {
        super.beforeExecute(t, r);
        lock.lock();
        try {
            while (isPaused) {
                condition.await();
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            lock.unlock();
        }
    }


    public void pause() {
        lock.lock();
        try {
            this.isPaused = true;
        } finally {
            lock.unlock();
        }
    }


    public void resume() {
        lock.lock();
        try {
            this.isPaused = false;
            this.condition.signalAll();
        } finally {
            lock.unlock();
        }
    }




    public static void main(String[] args) throws InterruptedException {
        PauseThreadPool pauseThreadPool = new PauseThreadPool(10, 20, 0, TimeUnit.SECONDS, new LinkedBlockingDeque<>());


        for (int i = 0; i < 10000; i++) {
            pauseThreadPool.execute(() -> {
                System.out.println(Thread.currentThread().getName() + "正在执行");
                try {
                    Thread.sleep(20);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            });
        }


        TimeUnit.SECONDS.sleep(1);
        pauseThreadPool.pause();
        System.out.println("pauseThreadPool被暂停了");
        TimeUnit.SECONDS.sleep(5);
        pauseThreadPool.resume();
        System.out.println("pauseThreadPool重新开始了");


        pauseThreadPool.shutdown();
    }
}

4.2.2. 钩子函数拓展——LinkedHashMap实现LRU

/**
 * 封装 linkedhashMap 得到LRU
 * 测试 LinkedHashMap
 * mybatis LRU实现
 * 第三个参数：accessOrder 是否开启排序（每次访问放入链表尾部）
 */
class LRUCache extends LinkedHashMap {
    private int maxElements;


    public LRUCache(int maxElements) {
        super(maxElements, .75F, true);
        this.maxElements = maxElements;
    }


    //钩子设计策略
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > maxElements;
    }
}

4.2.3. 线程池线程复用逻辑

启动的核心线程，一直while循环从队列中取出任务（runnable），然后调用run方法执行。

也就是说，线程池中的线程复用，是利用启动的线程，一直执行不同的任务。

4.2.4. 线程池状态

RUNNING：接受新任务并处理排队任务
SHUTDOWN：不接受新的任务，但是处理排队任务
STOP：不接受新任务，也不处理排队任务，并中断正在进行的任务
TIDYING：中文是整洁，意思是所有任务都终止，workerCount为零时，线程会转换到TIDYING状态，并将运行terminate()钩子方法。
TERMINATED：terminate()运行完成
4.3. ThreadLocal

4.3.1. ThreadLocal使用场景
1. 独享对象工具类 Random线程不安全，其实每次生成不同的随机值，安全不安全没有太大的用处，主要处理是，多线程调用生成比较慢的话会被堵塞，效率低下。JDK7.0已经有工具类可以直接调用ThreadLocalRandom，类似的方法还有很多。
2. 线程内，全局变量。避免参数传递的麻烦

两种场景对应两种 ThreadLocal用法 initialValue与set，对象的生成

4.3.2. ThreadLocal使用时，内存泄露的原因

内存泄露：顾名思义，肯定是有些地方的引用没有被GC回收，导致内存爆满进而OOM异常。

那么ThreadLocal主要存储与ThreadLocalMap中，ThreadLocal为key,value形式。所以只可能是key,value两个值可能出现泄露。

源码：可以看到 key为弱引用，value为强引用。（弱引用：是指当代码中没有任何被强引用此字段后，GC就会忽略弱引用部分直接回收）

static class Entry extends WeakReference<ThreadLocal<?>> {
    /** The value associated with this ThreadLocal. */
    Object value;


    Entry(ThreadLocal<?> k, Object v) {
        super(k);
        value = v;
    }
}

这就为内存泄露带来了隐患，因为当key没有再被强引用时，就会直接被GC回收掉，但是value为强引用，并没有被回收。

于是发生内存泄露问题

value泄露的原因：

正常情况下，首先因为ThreadLocalMap是Thread类中的一个成员变量。所以当Thread销毁时就会出现，直接回收对应的ThreadLocalMap，自然对应key,value都会被回收。

但是在线程池下，一个线程会一直运行，除非线程池关闭，那么就会有很大几率导致ThreadLocal 对应value内存泄露

4.3.3. ThreadLocal内存泄露解决办法

JDK已经考虑到此问题，set,remove,rehash方法中，发现key为null的entry会直接把value设置为null帮助回收。

避免方法：当线程使用完后（业务），调用remove方法，删除

4.3.4. ThreadLocal注意事项

空指针异常
- ThreadLocal没有初始化与赋值之前，get会返回null
- 如果设计到基础类型的，拆装箱操作，就会报出空指针异常
共享对象
- 每个线程的set()进去的东西本来就是，线程共享的同一对象，比如static对象时，还是会出现并发问题
不要强行使用
- 少数线程时，直接局部变量中新建对象就可以了
优先使用框架支持
- spring中如果可以使用RequestContextHolder，那就使用框架的，自己调用中会忘记remove()，造成内存泄露

4.4. Lock(锁)

4.4.1. lock与synchronized关系

为什么synchronized不够用？
- 效率低：锁释放情况少、不能设置超时、中断一个正在试图获取锁的线程
- 不够灵活（读写锁更灵活）：加锁和释放的时机单一，每个锁仅有单一的条件（某个对象）
- 无法知道是否成功获取锁
  4.4.1.1. Lock中trylock不会导致饥饿

饥饿是指：饥饿是什么意思？一个线程堵塞而得不到运行。

然而tryLock实质上是解决了饥饿问题，当线程一段时间内获取不到锁时，直接返回，线程执行其他业务。

4.4.2. 悲观锁与乐观锁

悲观锁
- 假设所有人都会访问并修改，在执行是直接锁住全局。
- synchronized与Lock相关（lock虽然其中使用到了部分的乐观锁，但是本质上从使用角度看，还是悲观锁）
乐观锁：
- 修改数据时，假设此数据不会被其他线程修改，先赋值修改，写回主存时查看是否被修改过，如果修改过，重试或者丢弃。
- 一般使用CAS来实现
  4.4.3. 悲观锁与乐观锁不同的使用场景
悲观锁：适合并发写入多的情况，适合于临界区持锁时间比较长的情况，因为这种情况下，乐观锁会自旋很长时间，消耗CPU资源
- 临界区有IO操作
- 临界区代码复杂或者循环量大
- 临界区竞争激烈
乐观锁：适合并发写入少，大部分是读的情况，不加锁能让读效率大增

4.5. 砸穿认知

砸穿认知，是我今年以来听到最震惊的一句话。半佛写的。语境是你以为的酷为什么你会以为这样就是酷？你的认知是谁控制的？

二叉树、ThreadLocal、lock

1. although

1.1. 细胞分裂算法题

1.2. 链表实现二分查找数

1.3. LeetCode

1.3.1. 二叉树的直径

1.3.2. 路径总和

1.3.3. 翻转二叉树

1.3.4. 平衡二叉树

1.3.5. 二叉树的最大深度

1.3.6. 合并二叉树

1.3.7. 路径总和 III

2. review

3. tip

3.1. 图解公平锁与非公平锁

3.2. 图解ThreadLocal结构

4.1. 设计模式

4.1.1. 并发相关设计模式：不变性（Immutability）模式

4.1.2. 并发相关设计模式：线程封闭

4.1.3. 并发相关设计模式：Copy-on-Write模式

4.2. 线程池

4.2.1. 钩子函数拓展——线程池

4.2.2. 钩子函数拓展——LinkedHashMap实现LRU

4.2.3. 线程池线程复用逻辑

4.2.4. 线程池状态

4.3. ThreadLocal

4.3.1. ThreadLocal使用场景

4.3.2. ThreadLocal使用时，内存泄露的原因

4.3.3. ThreadLocal内存泄露解决办法

4.3.4. ThreadLocal注意事项

4.4. Lock(锁)

4.4.1. lock与synchronized关系

4.4.1.1. Lock中trylock不会导致饥饿

4.4.2. 悲观锁与乐观锁

4.4.3. 悲观锁与乐观锁不同的使用场景

4.5. 砸穿认知

CATALOG

FEATURED TAGS

FRIENDS

1. although

1.1. 细胞分裂算法题

1.2. 链表实现二分查找数

1.3. LeetCode

1.3.1. 二叉树的直径

1.3.2. 路径总和

1.3.3. 翻转二叉树

1.3.4. 平衡二叉树

1.3.5. 二叉树的最大深度

1.3.6. 合并二叉树

1.3.7. 路径总和 III

2. review

3. tip

3.1. 图解公平锁与非公平锁

3.2. 图解ThreadLocal结构

4. share

4.1. 设计模式

4.1.1. 并发相关设计模式：不变性（Immutability）模式

4.1.2. 并发相关设计模式：线程封闭

4.1.3. 并发相关设计模式：Copy-on-Write模式

4.2. 线程池

4.2.1. 钩子函数拓展——线程池

4.2.2. 钩子函数拓展——LinkedHashMap实现LRU

4.2.3. 线程池 线程复用逻辑

4.2.4. 线程池状态

4.3. ThreadLocal

4.3.1. ThreadLocal使用场景

4.3.2. ThreadLocal使用时，内存泄露的原因

4.3.3. ThreadLocal内存泄露解决办法

4.3.4. ThreadLocal注意事项

4.4. Lock(锁)

4.4.1. lock与synchronized关系

4.4.1.1. Lock中trylock不会导致饥饿

4.4.2. 悲观锁与乐观锁

4.4.3. 悲观锁与乐观锁不同的使用场景

4.5. 砸穿认知

CATALOG

FEATURED TAGS

FRIENDS

4.2.3. 线程池线程复用逻辑