xhj的博客

图概念 图：由顶点集合和顶点间的关系集合组成的一种数据结构 有向图与无向图：在有向图中，顶点对(x,y)是有序的；无向图是无序的 完全图：在有n个顶点的图有n(n-1)/2条边，即为完全无向图；有n(n-1)条边，即为完全有向图 顶点的度：某一个顶点与其相关联的边的条数，有向图度是入度和出度之和 生成树：一个连通图的生成树是其极小连通子图，包括图中所有顶点，包含n-1条边 图的存储结构－邻接矩阵 在图的邻接矩阵表示中，有一个记录仪各个顶点信息的顶点表，还要一个表示各个顶点之间关系的邻接矩阵 网络的邻接矩阵 邻接表 邻接表是邻接矩阵的改进形式，需要把邻接矩阵的各行分别组织为一个单链表、 无向图的邻接表： 有向图的邻接表和逆邻接表： 网络邻接表： 图的遍历与连通性 DFS（深度优先搜索） BFS（广度优先搜索） 连通分量和生成树 极小连通子图（一棵生成树） 广度优先生成树、深度优先生成树 非连通无向图生成的生成树组将组成非连通图的森林 最小生成树（MST） 网络带权重的最小和的生成树 Prim算法：从顶点开始依次找最短边，然后相连 Kruskal算法...

内部排序概述 排序：将一组杂乱无章的数据按照一定规律顺次排列 数据表：待排序数据元素的有限集合 排序算法的稳定性：数据表中两个相同的值在经过算法排序后的相对位置是否改变 内排序：排序期间数据元素全部在内存中 外排序：数据太多，只能部分在内存中进行，需要不断进行内外存的数据转移 排序的时间开销：衡量算法好坏的标志，主要表现是数据比较次数和数据移动次数 总关键字比较次数：KCN 元素移动次数：RMN 内部排序 插入排序：每步将一个待排序的元素按照其关键字的大小，插入到前面已经排好序的一组元素的适当位置上面，直到全部元素插入完毕为止 直接插入排序：从unsorted的列表中找到最大的和sorted列表中最后一个元素交换 折半插入排序：利用折半查找算法，找到合适的位置层层递进插入（类似二叉查找树），实际复杂度取决于数据表的初始排列 2-路插入排序：复制一个新的数据表，遍历原数据表时判断与新数据表的关系选择插入位置 表插入排序：使用链表实现直接插入排序 希尔排序：(缩小增量排序)按照一个k的维度进行排序，开始时k值较大，子序列中元素较少，速度快；后来基本已完成排序，需要移动的元素减少...

内存管理内存管理基础内存管理概念 程序装入与链接 程序包括代码、数据和堆栈三个部分。 逻辑地址和物理地址空间 物理地址空间：硬件支持的地址空间 逻辑地址空间：CPU运行时，进程看到的进程空间 逻辑地址的生成：高级语言源码 –编译–> 指令汇编码 –编译–> 二进制代码 –链接：函数库平移–> 调用函数库（如果需要调用别的内存地址的函数） 程序加载重定位（逻辑地址平移）：内存实际分配位置不一定从0开始 编译时：假设起始地址已知，如果起始地址改变必须重新编译 加载时：如编译起始位置未知，编译器需要生成可重新定位的代码，加载时需要生成绝对地址 执行时：执行代码可移动，需要地址转换（映射的支持） 内存保护 连续分配管理方式给进程分配一块不小于指定大小的连续的物理内存区域（代码数据堆栈） 内存碎片：无法利用的空闲内存 外部碎片：两个区域之间的未被使用区域 内部碎片：分配单元内部的未被使用内存，取决于分配单元大小是否需要取整 动态分区分配：（指定大小、可变、地址连续） 操作系统维护数据结构：所有进程已分配分区和空闲分区 策略：最先匹配，最佳匹配，最差匹配 ...

串串 串（字符串）：由零个或者多个字符组成的有限序列。 串值：双引号括起来的字符序列 串长：所包含的字符总数量 子串（substring） 子串序号（index） 串相等：长度相等且对应位置的字符也一样 串常量：只能读，不能写 串变量：可读可写 串在计算机中的存储方式 定长顺序存储表示 堆分配存储 块链存储（块的意思是每个结点存放不止一个字符） 串的模式匹配算法 模式匹配：子串在主串中的定位称为模式匹配或串匹配 Brute-Force模式匹配算法 匹配流程 代码 BF算法代码 执行的复杂度为O(m+n)，最坏为O(m*n)。当遇到s=”001”,p=”00000000001”的串的时候，就会遇到最坏情况 KMP模式匹配算法 改进点：每当一趟匹配出现字符不相等时，主串指示器不用回溯，而利用已经得到的部分匹配的结果，将模式匹配器向右尽可能滑动一段距离后在继续比较 匹配流程 代码 KMP算法代码 可以大大缩短匹配的次数 时间复杂度一定是O(m+n) 仅当模式与主串之间存在许多部分匹配的情况，才会比BF算法有明显的性能提升

[TOC] Hadoop常见参数 配置所在文件 参数 参数默认值 作用 hdfs-site.xml dfs.namenode.support.allow.format true 表示设置NameNode是否允许被格式化。 在生产系统，把它设置为false，阻止任何格式化操作在一个运行的DFS上。 建议初次格式化后，修改配置禁止，改成false hdfs-site.xml dfs.heartbeat.interval 3 DataNode的心跳间隔，默认单位为秒 在集群网络通信状态不好的时候，适当调大 hdfs-site.xml dfs.blocksize 134217728 块大小，默认是128MB 必须得是1024(page size)的整数倍 hdfs-site.xml dfs.namenode.checkpoint.period 或者： fs.checkpoint.period 3600 edits和fsimage文件合并周期阈值，默认单位为s hdfs-site.xml dfs.stream-buffer-size 4096 文件流缓存大小。需要...

Hadoop简介概述 Hadoop：开源分布式存储、计算矿框架。免费试用 CHD：Hadoop的一个发行版本，可以一键式部署集群，但是是收费的，非常昂贵 Hadoop是Yahoo 开发，后来贡献给了Apache的一套开源的、可靠的、可扩展的（可伸缩的）用于进行分布式计算的框架 Hadoop之父：Doug Cutting（道格·卡丁） Hadoop的版本管理非常混乱（最新更新版本2.10，版本最新确实3.2） 模块 Hadoop Common：基本模块，支撑其他模块运行 Hadoop Distributed File System (HDFS™)：分布式存储 Hadoop YARN：任务调度和集群资源管理 Hadoop MapReduce：分布式计算 Hadoop Ozone：对象存储 版本 Hadoop 1.0：包含Common、HDFS、MapReduce Hadoop 2.0：包含Common、HDFS、MapReduce和YARN 从Hadoop 2.7开始包含了Ozone 从Hadoop 2.9开始包含了Submarine ==Hado...

目录[TOC] 23种设计模式GOF在 1994 年，由 Erich Gamma、Richard Helm、Ralph Johnson 和 John Vlissides 四人合著出版了一本名为 Design Patterns - Elements of Reusable Object-Oriented Software（中文译名：设计模式 - 可复用的面向对象软件元素） 的书，该书首次提到了软件开发中设计模式的概念。 四位作者合称 GOF（四人帮，全拼 Gang of Four）。他们所提出的设计模式主要是基于以下的面向对象设计原则。 对接口编程而不是对实现编程。 优先使用对象组合而不是继承。 设计模式简介参考网址 模式类型 模式 & 描述 包括 创建型模式 这些设计模式提供了一种在创建对象的同时隐藏创建逻辑的方式， 而不是使用 new 运算符直接实例化对象。这使得程序在判断针对某个给定实例需要创建哪些对象时更加灵活。 单例模式（Singleton Pattern） 原型模式（Prototype Pattern） 工厂模式（Factory Pattern）...

目录[TOC] Mysql基础数据库相关概念数据库的好处 持久化数据到本地 可以实现结构化查询，方便管理 数据库常见名词解释 DB：数据库，保存一组有组织的数据的容器 DBMS：数据库管理系统，又称为数据库软件（产品），用于管理DB中的数据 SQL:结构化查询语言，用于和DBMS通信的语言，不是某个数据库软件特有的，而是几乎所有的主流数据库软件通用的语言 数据库存储数据的特点 将数据放到表中，表再放到库中 一个数据库中可以有多个表，每个表都有一个的名字，用来标识自己。表名具有唯一性。 表具有一些特性，这些特性定义了数据在表中如何存储，类似java中 “类”的设计。 表由列组成，我们也称为字段。所有表都是由一个或多个列组成的，每一列类似java 中的”属性” 表中的数据是按行存储的，每一行类似于java中的“对象”。 常见数据库mysql、oracle、db2、sqlserver MySQL产品的介绍和安装MySQL背景前身属于瑞典的一家公司，MySQL AB08年被sun公司收购09年sun被oracle收购 MySQL的优点1、开源、免费、成本低2、性能高、移植性也好3、...

Maven1.Maven 是什么？Maven 主要服务于基于 Java 平台的项目构建、依赖管理和项目信息管理。 Maven 的主要功能主要分为 5 点： 依赖管理系统 多模块构建 一致的项目结构 一致的构建模型和插件机制 2.什么选用 Maven 进行构建？ 首先，Maven 是一个优秀的项目构建工具。使用 maven，可以很方便的对项目进行分模块构建，这样在开发和测试打包部署时，效率会提高很多。 其次，Maven 可以进行依赖的管理。使用 Maven ，可以将不同系统的依赖进行统一管理，并且可以进行依赖之间的传递和继承。 3. Maven 规约是什么？ /src/main/java/ ：Java 源码。 /src/main/resource ：Java 配置文件，资源文件。 /src/test/java/ ：Java 测试代码。 /src/test/resource ：Java 测试配置文件，资源文件。 /target ：文件编译过程中生成的 .class 文件、jar、war 等等。 pom.xml ：配置文件 Maven 要负责项目的自动化构建，以编译为例，Mav...

Zookeeper1.ZooKeeper 是什么？ZooKeeper 是一个开源的分布式协调服务。它是一个为分布式应用提供一致性服务的软件，分布式应用程序可以基于 Zookeeper 实现诸如数据发布/订阅、负载均衡、命名服务、分布式协调/通知、集群管理、Master 选举、分布式锁和分布式队列等功能。 ZooKeeper 的目标就是封装好复杂易出错的关键服务，将简单易用的接口和性能高效、功能稳定的系统提供给用户。 Zookeeper 保证了如下分布式一致性特性： （1）顺序一致性 （2）原子性 （3）单一视图 （4）可靠性 （5）实时性（最终一致性） 客户端的读请求可以被集群中的任意一台机器处理，如果读请求在节点上注册了监听器，这个监听器也是由所连接的 zookeeper 机器来处理。对于写请求，这些请求会同时发给其他 zookeeper 机器并且达成一致后，请求才会返回成功。因此，随着 zookeeper 的集群机器增多，读请求的吞吐会提高但是写请求的吞吐会下降。 有序性是 zookeeper 中非常重要的一个特性，所有的更新都是全局有序的，每个更新都有一...