hash
Hash(哈希)
Hash ：散列，通过关于键值(key)的函数，将数据映射到内存存储中一个位置来访问。这个过程叫做Hash，这个映射函数称做散列函数，存放记录的数组称做散列表(Hash Table),又叫哈希表。JAVA函数hashCode()即请求对象的哈希值。
Hash的优点
先分类再查找，通过计算缩小范围，加快查找速度。
例：
集合：｛13,19,25,27，17｝
若是采用数组或链表结构：
访问其中的一个元素（如18），需要遍历整个集合的元素，时间复杂度为O(n).
而采用哈希表时:
假如散列函数为H[key] = key % 5；则集合元素对应的hash值分别为｛3,4,0,2,2｝。
访问元素（18）只需要在Hash值为2的集合中寻找即可.
如果访问没有哈希冲突的元素，例如访问（25），可以直接访问哈希值为（0）的值。
故hash时间复杂度最差才为O(n),最优情况下只需要O(1);
由上面的例子，我们可以想象，如果由大量的数据，采用数组或是链表存储时，访问需要遍历，耗费的时间非常多，而Hash表通过哈希计算，可以直接定位到数据所在位置（发生哈希冲突时，哈希值相同，可以定位到较小范围）大大加快了 查找的速度，节省了大量时间。
散列函数（Hash函数）
Hash通过Hash函数，将Key值映射为地址，Address = F[key];
常见的几种Hash函数：直接定址法、数字分析法、平方取中法、折叠法、随机数法、除留余数法
-
直接定址法：取Key或者Key的某个线性函数值为散列地址。Hash(k) = k，或者Hash(k) = a*k + b, (a\b均为常数).
如下例所示：a = 1/100,b = -5.
Key Hash(Key) 1005200 10047 3009800 30093 1506400 15059 7604300 76038 -
数字分析法：需要知道Key的集合，并且Key的位数比地址位数多，选择Key数字分布均匀的位。如下：
Hash(Key) 取六位：
列数 ： 1 (2) 3 (4) 5 (6) (7) 8 (9) 10 11 12 (13)
key1： 5 2 4 2 7 5 8 5 3 6 5 1 3
key2： 5 4 4 8 7 7 7 5 4 8 9 5 1
key3： 3 1 5 3 7 8 5 4 6 3 5 5 2
key4： 5 3 6 4 3 2 5 4 5 3 2 6 4
其中(2、4、6、7、9、13) 这6列数字无重复，分布较均匀，取此六列作为Hash(Key)的值。
Hash(Key1) :225833
Hash(Key2):487741
Hash(Key3):138562
Hash(Key4):342554
-
平方取中法：取Key平方值的中间几位作为Hash地址。因为在设置散列函数时不一定知道所有关键字，选取哪几位不确定。一个数的平方的中间几位和数本身的每一位都有关，这样可以使随机分布的Key，得到的散列地址也是随机分布的 。如下：
Key Key值平方 Hash地址(5位) 111112113 12345901655324769 01655 010111101 00102234363432201 34363 210222134 44193345623513956 45623 -
折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。 当Key的位数较多的时候数字分布均匀适合采用这种方案.
具体的叠加方法有两种，移位法和折叠法：
例子：若Key为下列数串，地址位数为7，两种方法的Hash(key)分别如下：
Key：7982374 | 1861215 | 9892154 | 56923
移位折叠法： 折叠折叠法： 第一段 7982374 d1-dr 7982374 d1-dr 第二段 1861215 d(r+1)-d(2r) 5121681 d(2r)-d(r+1) 第三段 9892154 d(2r+1)-d(3r) 4512989 d(3r)-d(2r+1) 第四段 + 56923 d(3r+1)-d(end) + 32965 d(end)-d(3r+1) 结果： 19792666 17650009 Hash(key): 9792666 7650009 -
随机数法：伪随机探测再散列
具体实现：建立一个伪随机数发生器，Hash(Key) = random(Key). 以此伪随机数作为哈希地址。
-
除留余数法：取关键字被某个除数 p 求余，得到的作为散列地址。
即 H(Key) = Key % p；
例子如下：
Key P Hash(Key) (4位) 11076302 1000 6302 13635279 1000 5279 41076553 1000 6553 76553027 1000 3027
以上就是6种构造哈希函数的方法，选择时要本着尽量减少产生冲突的原则，根据Key值的位数，分布情况，范围大小做出更优的选择。
哈希冲突
不管选用何种散列函数，不可避免的都会产生不同Key值对应同一个Hash地址的情况，这种情况叫做哈希冲突。
哈希冲突的处理
当冲突发生时，我们需要想办法解决冲突，一般常用的方法有：开放定址法、单独链表法、双散列法、再散列法以及建业公共溢出取等方法。
-
开放定址法：
当冲突发生时，探测其他位置是否有空地址 (按一定的增量逐个的寻找空的地址)，将数据存入。根据探测时使用的增量的取法，分为：线性探测、平方探测、伪随机探测等。
新的Hash地址函数为 Hash_new (Key) = (Hash(Key) + d i) mod m；i = 1，2...k (k<= m-1).m表示集合的元素数，i表示已经探测的次数。
-
线性探测(Linear Probing)
d i = a * i + b; a\b为常数。
相当于逐个探测地址列表，直到找到一个空置的，将数据放入。
-
平方探测(Quadratic Probing)
d i = a * i 2 (i <= m/2) m是Key集合的总数。a是常数。
探测间隔 i2 个单元的位置是否为空，如果为空，将地址存放进去。
-
伪随机探测
d i = random(Key);
探测间隔为一个伪随机数。
例子：
Key集合为(15,36,25,46,75)，采用除留余数法，模10 ，冲突时采用线性探测法d i = i;
如图，15和36放入时无冲突发生，分别对应地址 5 和6 。
但是当25放入时，Hash(25) = 25%10 = 5,和Key= 15发生冲突，则令d 1 = 1,Hash(25) = (25 + 1) %10 = 6.
此时已然与Key = 36发生冲突，令d 2 = 2，Hash(25) = (25+2) %10 = 7,无冲突，放入。
此后46,75也发生冲突，解决方法同上。
-
-
链表法
将散列到同一个位置的所有元素依次存储在单链表中，或者也有存储在栈中。具体实现根据实际情况决定这些元素的数据存储结构。
如下图所示：
首页Hash地址为 i 的结点，均插入到以 T[i] 为头指针的单链表中。T 中各分量的初值均应为空指针。
在拉链法中，装填因子 α 可以大于 1，但一般均取 α ≤ 1。
装填因子(载荷因子)
散列表的载荷因子定义为：
α = 填入表中的元素个数 / 散列表的长度.
α 是散列表装满程度的标志因子。由于表长是定值，α 与“填入表中的元素个数”成正比，所以，α 越大，表明填入表中的元素越多，产生冲突的可能性就越大；反之，α 越小，标明填入表中的元素越少，产生冲突的可能性就越小。实际上，散列表的平均查找长度是载荷因子α 的函数，只是不同处理冲突的方法有不同的函数。
对于开放定址法，荷载因子是特别重要因素，应严格限制在0.7-0.8以下。超过0.8，查表时的CPU缓存不命中（cache missing）按照指数曲线上升。因此，一些采用开放定址法的hash库，如Java的系统库限制了荷载因子为0.75，超过此值将resize散列表。
相关阅读
Android开发之内容提供者——创建自己的ContentProvid
转载请注明出处：http://blog.csdn.net/dmk877/article/details/50387741苦心人天不负卧薪尝胆三千越甲可吞吴,有志者天不负釜底抽
介绍 RIP 简述RIP环路的形成 RIP防环机制 RIP和OSPF对比 OSPF 关键字 简介 邻居建立过程 七类LSA OSPF防环 OSPF和BGP和MPLS
build Variants创建不同配置的app（图文详解）
现象描述 开发一个app避免不了在多种环境下运行，比如开发环境、测试环境、正式环境，而根据不同环境要配置不同的变量，在以前，我都是通
本文转自：https://blog.csdn.net/misayaaaaa/article/details/53786215第一章全部题目(第一章基础较多)http://blog.csdn.net/misa
Handler是 Android中用来更新UI 的一套消息处理机制。Handler 允许线程间发送Message或Runnable对象进行通信。在Android中UI修改