树是一种很实用的数据结构，往往和查找，决策挂钩。提供对数级的时间复杂度。
而且树还有一点，因为它是结构递归的，所以它的很多算法，都可以用递归去实现。
这算是对《算法》这本书的总结，真心觉得这本书太好看了，不像算法导论那么难懂。
需要记住的是一颗树的深度，表示了它查找最深需要多深，而可以将所有节点的深度进行相加，再除以节点个数，来求出一个二叉查找树的平均高度。1979年，J.Robson证明了随机键构造的二叉查找树的平均高度为树的结点数的对数级别，随后L.Devroye证明了对于足够大的N，这个值趋近于2.99lgN。
二叉查找树被称为（BST），首先它是一颗二叉树，而且每个节点的左子树，键都比它小，每个节点的右子树，键都比它大。
下面分别讲解其对应的接口：
首先要区分几个概念，Map这种东西，其实是一种统称的数据结构，翻译过来应该是映射表或者是关联数组。它的作用其实是提供一种映射来维护键值对，也就是说你可以通过键来找到值。而这些key组成的集合必须要是一个set。
然后再说实现，java的标准库中针对Map提供了好几种实现，比如所有哈希表实现的HashMap，还有基于红黑树实现的TreeMap。而在python中最常用的数据结构，dict也是哈希表实现的。
在java中一个对象要想能够作为Map的key，有一个关键的函数是equals，这个方法是用来判断两个对象是否相等的。如果你不重载此方法的时候，equals其实默认调用的 == 运算符。而等号运算符在堆中创建的对象其实是比较引用。所以对于字符串这样的对象，java重写了equals方法。这个方法对Map的用处是，Map使用此方法来确定两个对象是否相等，也就是说用Map的get方法获得数据的时候，其实是通过equals来比较key的。而如果是以HashMap实现的Map，那还需要一个关键的函数，就是hashCode，这个函数被称为散列函数，用来返回一个散列码，这就是对应哈希表的数据结构实现时的数组索引。
其实提到树这种数据结构，你一定会和搜索联系起来，毕竟每次分支的决策就能过滤掉大半的选择，从而使解空间变得越来越小。有一种在文件系统很常用的树，那就是b树。
上面这张图就是一个b树的样子，b树的非终端节点，都是一个节点，可以存放一组信息，其结构可以定义为：(n, A0, K1, A1, K2, …. , Kn, An).其中n表示这个节点有几个关键字，而K就表示关键字，A表示指向子树节点的指针。那么从数据结构图就能明白，A0指向的节点都小于k1，A1指向的节点都大于k1小于k2.而且所有叶子节点都出现在同一层次上，并且不带信息（其实就是空指针）。
而这种被称为b树的树结构，关键的不同点是每个节点可有多个key和分叉使得你可以把节点的大小凑成某个数，比如接近磁盘一个块的大小(或整数倍)。因为磁盘的读写是一块一块进行的，所以这样做的话能够较高效率地IO。
下面两张图算是机械硬盘的主视图和俯视图了。其实没必要对机械硬盘过于深入的了解，只需要知道，我们的数据其实是存储于盘面的，当我的数据需要被读取或者写入的时候，都需要让磁头移动到那个盘面的那个位置，首先可以看到每一个盘面都都应一个磁头。盘面本身可以转动，而从第二张图也可以知道，磁头可以横向移动，从而触碰一个半径上的磁盘。就这样，我们可以访问n个盘面上的所有位置。但是你会发现，要随机访问一块数据非常慢，因为你要先确定数据在哪个盘面的哪个磁道的哪个扇区。然后先让磁盘旋转到磁头可以触碰的那个磁道，然后在让磁头移动到相应的扇区。
之前公司有一个需求，需要搭建一个微信机器人，查阅了相关资料，整理了一些Demo之后，我大概实现了一个python的微信机器人聊天程序，这里就把经验拿出来分享下。
首先你要明白，微信并没有给你提供一套接口，一套文档，让你开发聊天机器人。如果你想实现一个机器人，能够被拉到群里，与群里的人聊天，就必须用点hack的办法。
这个原理就是web版本的微信，想想你登录web版的微信，在浏览器输入地址后，先会给你返回一个二维码。然后你用你的手机扫描了此二维码，接着就登录成功了。
这个扫二维码登录的过程，其实就是一个授权的过程，即你授权给web界面，使得可以通过web页面，用http的方式与微信服务器建立交互。所以微信机器人的实现方式就是基于此。你创建一个账号，然后这个账号就是微信机器人，你通过扫码的方式登录，使得可以通过http的方式与微信服务器建立交互。就这样，我们的服务托管了你的机器人账户，从而与群里的人进行交流，解析他们的聊天记录，匹配关键字，生成相应的回复信息。
首先想想和微信服务器建立交互的时序图。
这篇博客我打算总结一下，如何用git来完成某些撤销操作。当然这里指的撤销操作,一部分是说，git命令本身就支持的撤销操作，还有一部分是说我们为了对自己错误的补救而做的撤销操作。
我把git所控制的项目结构，分成了四个区。当然这种分法并不完全严谨，但是我认为它对我理解git这个模型很有用。
第一个是工作目录，其实工作目录就是你的项目本身，你平时写代码，都是在和工作目录打交道。而git其实就是在跟踪你的工作目录。所以如果你在开发一个项目，但是根本不打算用git管理，连git init的命令都没有输，那你就只有工作目录本身了。
第二个是暂存区，一开始学git的时候，都有这样一个疑问，为什么直接git commit不行。还非要git add一次。其实git的add一个文件，就是把一个文件放到暂存区。而你commit，其实就是commit暂存区的内容。这样的好处是你可以选择你准备要提交的修进行提交。而不是把所有修改的代码都进行提交。
git的这个add是很有歧义的，因为它和早期的svn意思并不一样，在svn里，add就是将某个文件加入版本控制了。还有这个stage，在git中有些被称为cache的命令：如 git diff --cached,其实就是和stage比较，所以git在新的版本中虽然保留了这两个命令作为后相兼容，同时又提供了新的命令共选择：
git stage 作为 git add 的同义词git diff --staged 作为 git diff --cached 的同义词
第三个区域是代码库，这就是git存储代码版本的地方，你可以理解每一个git项目，都在内部维护了一个数据库，数据库里存放着历史代码，不管它底层是怎样的，它在表现形式上，就像是一颗树，记录着每一个分支的每一个版本。
前几天皮带头部那里一个用于固定的螺丝扣坏了，如果是什么便宜的皮带，那我也就扔掉再买一根了。但是这条皮带还是我最贵的，所以我在淘宝买了几个皮带扣螺丝，自己装上了。
这个螺丝比我想象中的要短，但是用起来没什么大碍。因为这件事，我意识到自己很久没这么修过东西了。
父亲是个喜欢修东西的人，他有各种大大小小的盒子，里面装着各种螺丝帽和螺丝，还有大大小小的扳手和螺丝刀，还有一些看似已经没什么用的，可以扔掉的大大小小的物件，也被父亲收集起来，用来做替补。去年过年回家的时候，我的眼镜鼻梁那里的软垫子一个掉了，父亲从一个已经废弃了的眼镜上面取下了一对，为我装上。
还有小的时候，有一次我的FC游戏机手柄内部的线断了，也是父亲为我修好的，那个东西需要用到一个叫做电烙铁的东西，还要用到锡和焊锡膏。电烙铁加热之后，沾着焊锡膏取下一小块锡，就可以用它把电线固定到板子上了。
最近不是很流行忆童年的那个《神奇宝贝》么，就是那个可以用手机在真实世界的地图上抓神奇宝贝的pokemongo 。但是我对此并不感冒，因为《四驱兄弟》那才是我的童年，当时要组装一辆四驱车，母车就要20块钱，然后你要买一大堆导轮和加固车头的铝合金，这些都要几十块钱，还有高强力的马达和几千毫安的充电电池（你现在觉得都贵）。那种强力的马达要五十块钱，而我的马达仅仅只有十块钱，然而父亲为我改造成了价值五十元的马达。原因就在于马达内部，那种包着绝缘层的铜线，被称为漆包线的东西，而那种五十块钱的马达，漆包线特别粗，父亲为我找来了粗漆包线，然后给我焊了一个。当然实际上，马达那种东西，越强力越费电。
所以之后我也有那么一个小盒子，里面装满了大大小小的齿轮，导轮和赛车轱辘。
最近我自己买了一个书架，一个床头桌和一个工学椅，买来的时候都是散的，我花了一下午的时间才把这些东西装好，装的时候很烦，几次骂娘，因为那个螺丝非常难拧，拧的人手疼，所以你不得不带一个线手套。但是虽然过程痛苦，但当你把这些东西拼装起来的时候还是很有成就感的。
我发现周围一部分程序员，把阻塞，非阻塞，同步，异步这四个概念混淆了，一些没有理解这几个概念之间的关系，另一些则以为自己理解了。
其实很长一段时间我也没有搞明白这四个之间的关系与区别，之后有了一些工作经验，并在阅读了一部分书籍之后才豁然开朗，所以这篇博客打算把自己的经验分享出来。
一种最常见的误区是把”阻塞，非阻塞”作为一组，“同步异步”作为一组，然后做一个组合，然后分别讨论：
同步阻塞
同步非阻塞
异步阻塞
异步非阻塞
这样一下子就变成了四个模型，网上大多数劣质的博客，都是这样介绍的。
很神奇的是，如果都异步了还阻塞个什么。。。
首先我们不谈论io，也不谈论异常机制，只谈论这几个词的单纯概念。
阻塞的英文为：blocking,非阻塞的英文为：non-blocking，其实这两个词是针对等待一个任务时，当前线程的状态。
比如你在当前线程中执行一个任务，如果你必须等到此任务返回结果后才能继续执行，那你的这个任务就是阻塞的。
而如果你在执行一个任务后，并不需要马上得到结果，所以你依旧获得你当前线程的控制权，这里你的任务就是非阻塞的。
而你最后到底是如何获得结果，其实阻塞非阻塞并不能描述，它只能描述你当前线程在执行一个任务后的状态。所以阻塞也就常常预示着让出CPU。