一只攻城狮的学习之旅

synchronized 实现原理2020-03-24 synchronized 实现原理前言众所周知 synchronized 锁在 Java 中经常使用它的源码是 C++ 实现的，它的实现原理是怎样的呢？本文以 OpenJDK 8 为例探究以下内容。 synchronized 是如何工作的 synchronized 锁升级过程 重量级锁的队列之间协作过程和策略 对象头对象头的内容非常多这里我们只做简单介绍以引出后文。在 JVM 中对象布局分为三块区域： 对象头 实例数据 对齐填充 当线程访问同步块时首先需要获得锁并把相关信息存储在对象头中。所以 wait、notify、notifyAll 这些方法为什么被设计在 Object 中或许你已经找到答案了。 Hotspot 有两种对象头： 数组类型，使用 arrayOopDesc 来描述对象头 其它，使用 instanceOopDesc 来描述对象头 对象头由两部分组成 Mark Word：存储自身的运行时数据，例如 HashCode、GC 年龄、锁相关信息等内容。 Klass Pointer：类型指针指向它的类元数据的指针 ...

详细分析JDK中Stream的实现原理前提Stream是JDK1.8中首次引入的，距今已经过去了接近8年时间（JDK1.8正式版是2013年底发布的）。Stream的引入一方面极大地简化了某些开发场景，另一方面也可能降低了编码的可读性（确实有不少人说到Stream会降低代码的可读性，但是在笔者看来，熟练使用之后反而觉得代码的可读性提高了）。这篇文章会花巨量篇幅，详细分析Stream的底层实现原理，参考的源码是JDK11的源码，其他版本JDK可能不适用于本文中的源码展示和相关例子。 这篇文章花费了极多时间和精力梳理和编写，希望能够帮助到本文的读者 Stream是如何做到向前兼容的Stream是JDK1.8引入的，如要需要JDK1.7或者以前的代码也能在JDK1.8或以上运行，那么Stream的引入必定不能在原来已经发布的接口方法进行修改，否则必定会因为兼容性问题导致老版本的接口实现无法在新版本中运行（方法签名出现异常），猜测是基于这个问题引入了接口默认方法，也就是default关键字。查看源码可以发现，ArrayList的超类Collection和Iterable分别添加了数个def ...

HashMap的最大容量是多少.首先, HashMap底层是数组+链表, 所以HashMap的容量约等于 数组长度 * 链表长度.因为链表长度不固定,甚至可能链表会是树结构, 所以我们主要讨论数组长度. 那么, 数组的最大长度是多长呢? 仔细想想, 好像这么多年也没去看过数组的源码(笑). 1234567一是规范隐含的限制。Java数组的length必须是非负的int，所以它的理论最大值就是java.lang.Integer.MAX_VALUE = 2^31-1 = 2147483647。二是具体的实现带来的限制。这会使得实际的JVM不一定能支持上面说的理论上的最大length。例如说如果有JVM使用uint32_t来记录对象大小的话，那可以允许的最大的数组长度（按元素的个数计算）就会是：(uint32_t的最大值 - 数组对象的对象头大小) / 数组元素大小 嗯..数组长度理论上可以达到 2^31-1 这么长, 那么HashMap的最大长度也是这么了? 不, 在HashMap中规定HashMap底层数组的元素最大为 1<<30 1static final int M ...

HashMap简介 HashMap核心数据结构Hash表 = 数组 + 线性链表 + 红黑树 为什么初始容量是2的指数幂?如果创建HashMap时指定的大小不是2的指数就会报错吗? 1Map map = new HashMap<>(13); 这行代码在编译的时候也不会报错,那为什么说初始容量是2的指数呢? 看一下HashMap的构造器 1234567891011121314151617181920212223public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if ( ...

C语言中三块难啃的硬骨头C语言在嵌入式学习中是必备的知识，审核大部分操作都要围绕C语言进行，而其中有三块“难啃的硬骨头”几乎是公认级别的。 0x01 指针指针公认最难理解的概念，也是让很多初学者选择放弃的直接原因。 指针之所以难理解，因为指针本身就是一个变量，是一个非常特殊的变量，专门存放地址的变量，这个地址需要给申请空间才能装东西，而且因为是个变量可以中间赋值，这么一倒腾很多人就开始犯晕了，绕不开弯了。C语言之所以被很多高手所喜欢，就是指针的魅力，中间可以灵活的切换，执行效率超高，这点也是让小白晕菜的地方。 指针是学习绕不过去的知识点，而且学完C语言，下一步紧接着切换到数据结构和算法，指针是切换的重点，指针搞不定下一步进行起来就很难，会让很多人放弃继续学习的勇气。 指针直接对接内存结构，常见的C语言里面的指针乱指，数组越界根本原因就是内存问题。在指针这个点有无穷无尽的发挥空间。很多编程的技巧都在此集结。 指针还涉及如何申请释放内存，如果释放不及时就会出现内存泄露的情况，指针是高效好用，但不彻底搞明白对于有些人来说简直就是噩梦。 在概念方面问题可以参见此前推文《对于C语言指针最详尽的 ...

C++内存管理内存管理是C++最令人切齿痛恨的问题，也是C++最有争议的问题，C++高手从中获得了更好的性能，更大的自由，C++菜鸟的收获则是一遍一遍的检查代码和对C++的痛恨，但内存管理在C++中无处不在，内存泄漏几乎在每个C++程序中都会发生，因此要想成为C++高手，内存管理一关是必须要过的，除非放弃C++，转到Java或者C#，他们的内存管理基本是自动的，当然你也放弃了自由和对内存的支配权，还放弃了C++超绝的性能。本期专题将从内存管理、内存泄漏、内存回收这三个方面来探讨C++内存管理问题。 1. 内存管理伟大的Bill Gates 曾经失言： 640K ought to be enough for everybody — Bill Gates 1981 程序员们经常编写内存管理程序，往往提心吊胆。如果不想触雷，唯一的解决办法就是发现所有潜伏的地雷并且排除它们，躲是躲不了的。本文的内容比一般教科书的要深入得多，读者需细心阅读，做到真正地通晓内存管理。 1.1 C++内存管理详解1.1.1 内存分配方式1.1.1.1 分配方式简介在C++中，内存分成5个区，他们分别是栈、堆、自由存 ...

一起探索C++类内存分布C++ 类中内存分布具体是怎么样，尤其是C++中含有继承、虚函数、虚拟继承以及菱形继承等等情况下。 由于在linux下没有windows下显示直观，我们采用vs2015进行调试。 部署环境 我们在 属性->C/C++ ->命令行 -> /d1 reportSingleClassLayoutXXX ,XXX表示类名； 单个基础类 12345678class Base{private: int a; int b;public: void test();}; 内存分布： 12345class Base size(8): +-- - 0 | a 4 | b +-- - 总结：我们发现普通类的内存分布是根据声明的顺序进行的,成员函数不占用内存。 基础类+继承类 12345678910111213141516class Base{ int a; int b;public: void test();};class Divide :public Base{public: ...

C++编码优化之减少冗余拷贝或赋值临时变量目前遇到的一些产生临时变量的情况：函数实参、函数返回值、隐式类型转换、多余的拷贝。 1. 函数实参这点应该比较容易理解，函数参数，如果是实参传递的话，函数体里的修改并不会影响调用时传入的参数的值。那么函数体里操作的对象肯定是函数调用的过程中产生出来的。 那么这种情况我们该怎么办呢？ 如果 callee 中确实要修改这个对象，但是 caller 又不想 callee 的修改影响到原来的值，那么这个临时变量就是必须的了，不需要也没办法避免。 如果 callee中根本没有修改这个对象，或者 callee 中这个参数本身就是 const 型的，那么将实参传递改为引用传递是个不错的选择（如果是基本类型的函数实参，则没有必要改为引用），可以减少一个临时变量而且不会带来任何损失。 另外，推荐一个静态代码检查工具 cppcheck，这个工具可以提示非基本类型的 const 实参改为引用。 2. 函数返回值（返回对象）函数返回值的情况比较复杂，因为编译器在这方面做了很多优化，编译器优化到何种程度我也没追根究底研究过。 在没开任何优化选项的时候，gcc 也优化了一 ...

N皇后51. N皇后 题目描述 n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 上图为 8 皇后问题的一种解法。 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。 示例： 12345678910111213输入: 4输出: [ [".Q..", // 解法 1 "...Q", "Q...", "..Q."], ["..Q.", // 解法 2 "Q...", "...Q", ".Q.."]]解释: 4 皇后问题存在两个不同的解法。 问题分析约束条件为每个棋子所在的行、列、对角线都不能有另一个棋子。 使用一维数组表示一种解法，下标（index）表示行，值（value）表示该行的Q（皇后）在哪一列。每行只存储一个元素，然后递归到下一行 ...

「游戏」寻路算法之A Star算法原理及实现前言自动寻路是在一些如MMORPG等类型游戏中常见的一种功能，其给了玩家良好的游戏体验，使得玩家在游戏过程中省去了大量游戏坐标点的记录以及长时间的键盘操作，不必记忆坐标，不必担心迷路，用最快捷的方法移动到指定地点。 寻路算法（自动寻路算法，下同），其实可以看作是一种路径查找算法以及图搜索算法，图搜索（Graph Search）算法是用于在图上进行一般性发现或显式地搜索的算法。这些算法在图上找到出路径，但没有期望这些路径是在计算意义上是最优的。 路径查找算法（Pathfinding）是建立在图搜索算法的基础上，它探索节点之间的路径，从一个节点开始，遍历关系，直到到达目的节点。这些算法用于识别图中的最优路由，算法可以用于诸如物流规划、最低成本呼叫或IP路由以及游戏模拟等用途。 常见的路径搜索算法和图搜索算法有：A（A Star）算法、Dijkstra算法、广（深）度优先搜索、最佳优先搜索、Jump Point Search算法等，今天本文主要讲解的是A（A Star）算法的原理以及实现。 常见搜索算法Dijkstra算法迪杰斯特拉算法(Dijks ...