所谓“洗牌算法”，就是把一组序列完全打乱，怎样才算乱呢？需要满足这样一个条件：对于包含n个元素的序列，每个元素出现在每个位置的概率都是$1/n$。

一种直白的方法就是，统计序列的全排列，然后在全排列集合中随机选取一各排列出来。这种方法虽然简单，但是无论是空间还是时间复杂度都太高了，有没有其他性能更高的算法呢？当然有，本文简单总结下集中常用的洗牌算法。

概述

拓扑排序，我的理解就是：有向图中所有节点的一种排列，这个排列需要满足下面两个条件：

• 序列包含图中所有节点，且每个节点只出现一次；
• 若A在序列中排在B的前面，则图中不存在从B到A的路径。

并查集，是一种高级数据结构，常用于数据分组问题。本文简单介绍一下并查集相关概念以及实现方法，并附带一些leetcode练习题。

平衡二叉树（Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。

148. 排序链表的最优方法应该是归并排序，鉴于面试时候经常会问链表快排，本文简单总结下链表排序的归并和快排方法。至于插入排序或者冒泡排序什么的，比较简单，本文不作介绍。

最近刷leetcode过程中遇到了很多背包问题，趁此机会总结下如何用动态规划解决背包问题及其各种变体。

写在前面：

本文适合有一定dp基础的读者阅读，用来复习回顾背包相关问题，遇到类似问题可快速秒掉。

这篇文章主要搬运自这里

之前学习Redis集群的数据分区方案时，了解到“一致性hash算法”，今天来详细探究一下一致性hash背后的事儿！

一致性hash算法主要用于解决分布式环境下的数据分区和负载均衡问题：

1. 分布式环境下，如何确定那个key存储在那个节点上呢？
2. 如何保证数据或者请求分布均衡呢？也就是我们常说的负载均衡？

利用一致性hash就能很好的解决上面两个问题。

基础介绍

产生背景

“存在即合理”，任何一种理论或技术的产生，必然有它的原因。了解它产生的背景、为了解决的问题有助于我们更好地把握AOP（Aspect-OrientedProgramming）的概念。
软件开发一直在寻求一种高效开发、护展、维护的方式。从面向过程的开发实践中，前人将关注点抽象出来，对行为和属性进行聚合，形成了面向对象的开发思想，其在一定程度上影响了软件开发的过程。鉴于此，我们在开发的过程中会对软件开发进行抽象、分割成各个模块或对象。例如，我们会对API进行抽象成四个模块：Controller,Service,Gateway,Command.这很好地解决了业务级别的开发，但对于系统级别的开发我们很难聚焦。比如、对于每一个模块需要进行打日志、代码监控、异常处理。以打日志为例，我只能将日志代码嵌套在各个对象上，而无法关注日志本身，而这种现象又偏离了OOP思想。

IOC全称Inversion of Control， 中文通常翻译成“控制反转”，它还有一个别名叫做依赖注入（Dependency Injection）。IOC是一种设计思想，DI是IOC在Spring中的具体实现方式。

为什么需要IoC？IoC的具体意义是什么？它到底有什么独到之处？

IOC容器初始化说起来很简单，就包括3个过程：

1. Resource，资源定位，比如通过xml文件配置bean，我们要先找到xml文件，并加载进来，然后再进行之后的操作；
2. BeanDefinition，把xml文件中定义好的bean加载进来后，我们就要对它进行解析，然后用一个数据结构来描述这个bean，这个数据结构就是BeanDefinition;
3. Registe，到这一步，bean已经定义好了，剩下的工作就是把bean注册一下，告诉其他人现在容器里面有我这一号人，你们要用的时候直接招呼一声就行了。