Hash table

Hash table它大概可以说是效能最快的搜索方法。

首先看下Hash table 最基本的定义。
一段Array当成Hash table header，后面接上linked-list，大概是这个样子:

假设我的Hash table size 是N，那就有A[0]-A[N-1]的header。
后面有value 用linked-list接着，所以它的资料量，可能会远比N要大，或比N都要小，都不一定。

那我的value到底要放在哪？

所以，有一个Hash function H()，根据传入的值算出Hash table index，假设要寻找一个value的时候，利用H(value)会算出一个值 --k,然后有了k之后，开始从Hash table A[N]数组的第k行往后找。

从A[k]开始找，一个一个找到一样的，那就OK。找不到一直遇见NULL，那就找不到。

假设Hash function 把一大堆的数据放进来，如果把数值平均分配打散的话，那后面的长度可能3个也可能4个，单基本上差不多，不会说把全部的放在一条中，或者说其中一个有十万个，其他的一个或者几个。那就不是一个hash table了，代表你的hash function做的很差，或者说数据都机会总在前面几行，后面为null，那也说明你的tash function做的很差。

所以说，如果Array够大，Hash function能够平均分配，Linked-list长度是有限制的，大概可能4个或者5个，所以我要找的时候，只要找到k值，从第k条，开始往后找，那我比对个1-5次可能就找到了

那它的Complexity:O(1)

也就是说跟你的N大或者小，是无关的，大概找个几次就可以找到。

Hash table 设计上有几点要注意的:###

1. Hash table size N
N最好不要是2的倍数，10的倍数，因为这样会让所有的数据，可能会全部偏到一边去，hash table 某一边有一堆值，另外一边可能是null，或者个别几个值，容易造成不平均。
所以最好的table能够是质数或者是2^n -1。

2. Hash function H()
function 最好能够吧数据平均的分散，计算也不要太复杂。
比如有许多现成的Hash funcitons，如FNV-1,MD5等等

3.Hash table的变形
参考Linear probing,Quadratic probing,Double hashing.

Hash table它的Complexity:O(1),基本已经到常数了，基本有很难比这个更快的搜索方式了。

那到底在找一个数据的时候，选择什么样的方式呢？

首先要看数据量。

顺序查找(Sequential Search)

小数据量(几十，几百)，虽然慢，但是够了。一个for 就好。简单方便。

二叉搜索树(Binary Search)

数据够大，且已经排序好了，上篇也讲到了，数据大道几十亿的时候，搜索也就几十次，那顺序查找Sequential Search可能得很久，虽然写起来有一点点复杂，可能比for复杂，但是也复杂不到哪去。

Hash table

数据量大，杂乱无排序是比较好的选择，不会比Binary Search慢，数量大的时候，甚至可能比较快

Database

数据库，肯定不会陌生，选择它的前择，数据是结构化的，数据量最好不要超过百万，几百万可能还可以，但是数据几千万的时候，可能会撑不住，效能会明显下降。

Search engine

那数据真的达到几千万或者上亿的时候，可以考虑搜索引擎，但是绝大数人对付这么大的数据的几率是比较低的。

根据数据结构和需求可能会运用到其他算法，如最近的一个一聊天的项目，需要敏感字过滤，然后采用了AC多模式匹配算法，可能还会有更多的状况需要运用到不同的算法，比如我们常见的冒泡排序，快速排序等等，但是这里只是用搜索来理解一下算法的基本概念。

SP

然后就暂时这样吧，算法的理解我暂时也就仅此而已，理解的不是很深，因为一般项目中很少会接触大数据的处理，毕竟我只是个搞android的，希望点东西，能够帮助你简单的理解算法。