CAS简介
CAS简介一、CAS概念CAS的全称为Compare And Swap即比较并交换,它是一条CPU并发原语。它的功能是判断内存某个位置的值是否为预期值，如果是则更改为新的值。看起来这是两步操作，但是由于底层硬件的支持，使两步操作能一步完成，从而保证了原子性，避免了独占锁的资源浪费。CAS并发原语体现在Java语言中就是sun.misc.Unsafe类中的各个方法。调用UnSafe类中的CAS方法，JVM会帮我们实现出CAS汇编指令。这是一种完全依赖于硬件的功能，通过它实现了原子操作。再次强调，由于CAS是一种系统原语，原语属于操作系统用语范畴，是由若干条指令组成的，用于完成某个功能的一个...
单例模式volatile分析
单例模式volatile分析概述DCL(双端检锁)机制不一定线程安全，原因是有指令重排序的存在，加入volatile可以禁止指令重排原因在于某一个线程执行到第一次检测，读取到instance不为null时，instance的引用对象可能没有完成初始化。instance = new SingletonDemo();可以分为以下3步完成memory = allocate();//1.分配对象内存空间instance(memory);;//2.初始化对象instance = memory;//3.设置instance指向刚分配的内存地址，此时instance != null步骤2和步骤3不存在...
【转载】单例模式简介
【转载】单例模式简介一、概述 单例模式是设计模式中相对简单且非常常见的一种设计模式，但是同时也是非常经典的高频面试题，相信还是有很多人在面试时会挂在这里。本篇文章主要针对单例模式做一个回顾，记录单例模式的应用场景、常见写法、针对线程安全进行调试（看得见的线程）以及总结。相信大家看完这篇文章之后，对单例模式有一个非常深刻的认识。文章中按照常见的单例模式的写法，由浅入深进行讲解记录；以及指出该写法的不足，从而进行演进改造。秉承废话少说的原则，我们下面快速开始二、定义具体实现（1）将构造方法私有化，使其不能在类的外部通过new关键字实例化该类对象。（2）在该类内部产生一个唯一的...
LeetCode-4 寻找两个有序数组的中位数
LeetCode-4 寻找两个有序数组的中位数题目描述给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。示例 1:nums1 = [1, 3]nums2 = [2]则中位数是 2.0示例 2:nums1 = [1, 2]nums2 = [3, 4]则中位数是 (2 + 3)/2 = 2.5代码实现public class Solution04 { public static void main(String[] a...
【转载】volatile关键字简介
【转载】volatile关键字简介Java线程控制中常见的两个关键字：synchronized、volatile一、volatile是什么？volatile是Java中的关键字，也是Java虚拟机提供的轻量级的同步机制(乞丐版的synchronized)。二、volatile的三大特性1.可见性2.不保证原子性3.禁止指令重排序三、为什么说volatile是轻量级的同步机制？因为大多数多线程开发都需要遵守JMM的三大特性：1.可见性2.原子性3.有序性而volatile只保证可见性和禁止指令重排序（有序性）所以说是轻量级的同步机制。可见性由于JVM运行程序的实体是线程，而每个线程创建时J...
LeetCode-3 无重复字符的最长子串
LeetCode-3 无重复字符的最长子串难度：中等分类：字符串解决方案：双指针、滑动窗口题目描述给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。示例1：输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为3。示例2：输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例3：输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所...
数据结构和算法学习--二叉排序树
数据结构和算法学习--二叉排序树一、二叉排序树介绍二叉排序树：BST（Binary Sort(Search) Tree）,对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点比如针对前面的数据(7,3,10,12,5,1,9),对应的二叉排序树为：二、二叉排序树创建和遍历一个数组创建成对应的二叉排序树，并使用中序遍历二叉排序树，比如：数组为Array(7,3,10,12,5,1,9),创建对应的二叉排序树为：三、二叉排序树的删除二叉排序树的删除情况比较复杂，有下面三种情况需要考虑（...
LeetCode-2 两数相加
LeetCode-2 两数相加题目：2. 两数相加难度：中等分类：链表解决方案：链表的遍历题目描述给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 注意：您可以假设除了数字0之外，这两个数都不会以0开头。示例：输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)输出：7 -> 0 -> 8原因：342 + 465 = 807分析这个题理解起来难度不大，就是将数字从个位数开始将数字放到链表的各个结点上，...
LeetCode-1.两数之和
LeetCode-1.两数之和题目给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的 两个 整数。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。示例:给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]解法一：通过暴力搜索进行解决。public static int[] twoSum(int[] arr,int target){ int[] sumIndex = new int[2]; for(int...
数据结构和算法学习--堆排序
数据结构和算法学习--堆排序一、堆排序基本介绍（1）堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn),它也是不稳定排序。（2）堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆，注意：没有要求结点的左孩子的值和右孩子的值的大小关系。（3）每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆（4）大顶堆举例说明我们对堆中的结点按层进行编号，映射到数组中就是下面这个样子：大顶堆特点：arr[i]>=arr[2*i+1]&&arr[i]>=arr[2*i+2]...