GrayWind的博客

Java HashMap类源码解析

分析Map集合HashMap实现原理

　　作为重要的常用集合，HashMap主要是提供键值对的存取，通过key值可以快速找到对应的value值。Hash表是通过提前设定好的规则计算一个元素的hash值来找到他在数组中的存储位置进行快速定位，假设有一个大小为10的数组，可以设定简单的计算规则为元素转为int后mod 10，由此元素的hash值一定会落在大小为10的数组内。由于不同元素可能会计算出相同的hash值，如例子中1和11都...

Posted by GrayWind on August 11, 2018

算法导论——最小生成树

算法导论读书笔记——最小生成树

　　对于一个连通图来说，我们可以去掉其中一些边依然保持其连通的性质，在这些图中存在一个或多个图，他们的路径总和是最小的，这样的图必然是树。因为，如果说图中存在环，则去掉环的一条边依然可以保证连通性，这与总路径和最小是矛盾的。这样的图被称为最下生成树。城市间铺设电路就可以利用最小生成树来进行规划。如图所示的黑色路径构成了最小生成树，去掉bc并加入ah也是一棵最小生成树，可见一个图的最小...

Posted by GrayWind on August 7, 2018

Java LinkedList类源码解析

分析List集合LinkedList实现原理

LinkedList底层为双向链表同样继承了AbstractSequentialList，跟ArrayList的数组相比读取效率低，不支持随机读取，碎片化空间利用率高，平均随机插入效率相对高。同时可以用来实现queue。属性有: transient int size = 0;list大小 transient Node first;头指针 transient Node last;尾指针 ...

Posted by GrayWind on August 7, 2018

算法导论——基本的图算法

算法导论读书笔记——基本的图算法

　　对于图G=(V,E)，V代表点，E代表边。图有两种标准的表示方法：邻接矩阵法和邻接链表法。　　邻接链表法适合表示边的条数少的稀疏图，可以节约存储空间。对于有向图G来说，边(u,v)一定会出现在链表Adj[u]中，因此，所有链表的长度之和一定等于 E 。对于无向图来说，边(u,v)会同时出现在Adj[u]和Adj[v]中，因...

Posted by GrayWind on August 6, 2018

Java ArrayList类源码解析

分析List集合ArrayList实现原理

ArrayList是最常用的集合类，底层是由数组实现的首先可以看到，有两个static final对象数组，也就是被线程间共享的，EMPTY_ELEMENTDATA是非default大小的空集合，原因是要辨别第一次添加元素时应该扩展的大小。 private static final Object[] EMPTY_ELEMENTDATA = {}; private static fin...

Posted by GrayWind on August 5, 2018

算法导论——用于不相交集合的数据结构

算法导论读书笔记——用于不相交集合的数据结构

不相交集合的操作一些应用涉及将n个不同元素分成一组不相交的集合，常进行两种操作：寻找包含制定元素的唯一集合以及合并两个集合。操作进行以下定于： MAKE-SET(x)建立一个新的集合，仅含有x UNION(x,y)将包含x和y的两个集合合并成一个新的集合，删除原本的集合 FIND-SET(x)返回一个指向包含唯一x的集合的指针无向图的连通...

Posted by GrayWind on August 4, 2018

算法导论——斐波那契堆

算法导论读书笔记——斐波那契堆

斐波那契堆是具有最小堆序的有根树的集合，也就是集合中的每棵树都具有父结点的关键字小于或等于子结点的关键字。对于每一个结点x，主要有以下属性：名称说明记作关键字结点存储的值 x.key 父结点结点的父亲 ...

Posted by GrayWind on August 2, 2018

Java String类源码解析

分析字符串String实现原理

String直接继承Object 含有一个char[] value，还有一个int hash默认值为0 new String()的构造产生的是一个值为””的字符数组 String(char value[], int offset, int count)当count=0且offset<=value.length时构造一个值为””的字符串。offset>0且offset+cou...

Posted by GrayWind on August 1, 2018

算法导论——贪心算法

算法导论读书笔记——贪心算法

贪心算法（greedy algorithm）是指，在每一步都做出当时看起来最佳的选择，也就是局部最优的选择，期望这样的选择能够导向全局最优解。所以并不是所有的问题都能得到全局最优解。典型的例子如分数背包问题：背包容量为50kg，有三个商品分别是重60元/10kg、100元/20kg、120元/30kg，商品可以分割，如何选取商品使背包价值最大。这里使用贪心算法，应当优...

Posted by GrayWind on July 31, 2018

算法导论——动态规划

算法导论读书笔记——动态规划

　　动态规划指的是一个问题可以拆分成多个小的最优子问题，并且这些子问题具有重叠，典型的如斐波那契数列：f(2)=f(1)+f(0),f(3)=f(2)+f(1),f(4)=f(3)+f(2)，若使用简单的递归算法求f(4)，则f(2)会被计算两次，当计算f(n)时需要计算f(n-1)和f(n-2)而f(n-1)又要计算记一次f(n-2)，如此往复时间复杂度为n的指数级别，导致算法效率低下。若...

Posted by GrayWind on July 24, 2018

GW Blog