hash算法实现
A. 哈希的算法是什么
哈希算法是一个广义的算法，也可以认为是一种思想，使用Hash算法可以提高存储空间的利用率，可以提高数据的查询效率，也可以做数字签名来保障数据传递的安全性。所以Hash算法被广泛地应用在互联网应用中。
哈希算法也被称为散列算法，Hash算法虽然被称为算法，但实际上它更像是一种思想。Hash算法没有一个固定的公式，只要符合散列思想的算法都可以被称为是Hash算法。
特点：
加密哈希跟普通哈希的区别就是安全性，一般原则是只要一种哈希算法出现过碰撞，就会不被推荐成为加密哈希了，只有安全度高的哈希算法才能用作加密哈希。
同时加密哈希其实也能当普通哈希来用，Git 版本控制工具就是用 SHA-1 这个加密哈希算法来做完整性校验的。一般来讲越安全的哈希算法，处理速度也就越慢，所以并不是所有的场合都适合用加密哈希来替代普通哈希。
B. Android APK hash值算法
无符号右移16位然后做异或运算
hash值计算公式:
对于key的hashCode做hash操作，无符号右移16位然后做异或运算。还有平方取中法，伪随机数法和取余数法。这三种效率都比较低。而无符号右移16位异或运算效率是最高的。集合中的初始化容量（必须是二的n次幂）//默认的初始容量是16--1<<4相当于1*2的4次方---1*16staticfinalintDEFAULT_INITIAL_CAPACITY=1<<4;1212staticfinalinthash(Objectkey){inth;/*
如果key等于null：可以看到当key等于null的时候也是有哈希值的，返回的是0.
如果key不等于null：首先计算出key的hashCode赋值给h，然后与h无符号右移16位后的二进制进行按位异或得到最后的hash值。
C. java 1.哈希算法的实现：
public class Test { /*创建类*/
public static void main(String[] args) {
System.out.println(dg(100));
}
static int dg(int i) { /*定义变量 */
int sum;
if (i == 1) /*假设条件*/
return 1;
else
sum = i + dg(i - 1); /*1~100的和的表达式*/
return sum; /*返回结果*/
}
}
这个脚本语言为 Internet 应用而生，它可以看作是 Haskell 和 Java 的结合。
D. 哈希算法是怎么实现的
哈希算法将任意长度的二进制值映射为较短的固定长度的二进制值，这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母，随后的哈希都将产生不同的值。要找到散列为同一个值的两个不同的输入，在计算上是不可能的，所以数据的哈希值可以检验数据的完整性。一般用于快速查找和加密算法。[1]
E. Hash算法原理
散列表,它是基于高速存取的角度设计的，也是一种典型的“空间换时间”的做法。顾名思义，该数据结构能够理解为一个线性表，可是当中的元素不是紧密排列的，而是可能存在空隙。
散列表（Hash table，也叫哈希表），是依据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
比方我们存储70个元素，但我们可能为这70个元素申请了100个元素的空间。70/100=0.7，这个数字称为负载因子。
我们之所以这样做，也是为了“高速存取”的目的。我们基于一种结果尽可能随机平均分布的固定函数H为每一个元素安排存储位置，这样就能够避免遍历性质的线性搜索，以达到高速存取。可是因为此随机性，也必定导致一个问题就是冲突。
所谓冲突，即两个元素通过散列函数H得到的地址同样，那么这两个元素称为“同义词”。这类似于70个人去一个有100个椅子的饭店吃饭。散列函数的计算结果是一个存储单位地址，每一个存储单位称为“桶”。设一个散列表有m个桶，则散列函数的值域应为[0,m-1]。
(5)hash算法实现扩展阅读:
SHA家族的五个算法，分别是SHA-1、SHA-224、SHA-256、SHA-384，和SHA-512，由美国国家安全局（NSA）所设计，并由美国国家标准与技术研究院（NIST）发布；是美国的政府标准。后四者有时并称为SHA-2。
SHA-1在许多安全协定中广为使用，包括TLS和SSL、PGP、SSH、S/MIME和IPsec，曾被视为是MD5（更早之前被广为使用的杂凑函数）的后继者。但SHA-1的安全性如今被密码学家严重质疑；
虽然至今尚未出现对SHA-2有效的攻击，它的算法跟SHA-1基本上仍然相似；因此有些人开始发展其他替代的杂凑算法。
应用
SHA-1, SHA-224, SHA-256, SHA-384 和 SHA-512 都被需要安全杂凑算法的美国联邦政府所应用，他们也使用其他的密码算法和协定来保护敏感的未保密资料。FIPS PUB 180-1也鼓励私人或商业组织使用 SHA-1 加密。Fritz-chip 将很可能使用 SHA-1 杂凑函数来实现个人电脑上的数位版权管理。
首先推动安全杂凑算法出版的是已合并的数位签章标准。
SHA 杂凑函数已被做为 SHACAL 分组密码算法的基础。
F. HashMap底层实现原理剖析
Hashmap是一种非常常用的、应用广泛的数据类型，最近研究到相关的内容，就正好复习一下。网上关于hashmap的文章很多，但到底是自己学习的总结，就发出来跟大家一起分享，一起讨论。
1.HashMap的数据结构：在java 中 数据结构，最基本 也就两种 一种数组 一种模拟指针。所有的数据结构都可以用这两个基本结构来构造的，hashmap也不例外。Hashmap实际上是一个数组和链表的结合体。数组的默认长度为16，
2.hashMap源码解析
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 初始化容量大小
static final int MAXIMUM_CAPACITY = 1 << 30; ///容器最大值
static final float DEFAULT_LOAD_FACTOR = 0.75f; //加载影子
static final Entry[] EMPTY_TABLE = {}; //null 的hashMap
transient Entry[] table = (Entry[]) EMPTY_TABLE;///动态扩大容器时使用的一个hashMap
transient int size;//当前数据量
int threshold;//扩大容器时的大小 为 capacity * load factor
final float loadFactor;//使用率阀值，默认为：DEFAULT_LOAD_FACTOR
存取元素 ：调用put方法
public V put(K key, V value) {
//判断当前table 为Null 第一次Put
if (table == EMPTY_TABLE) {
inflateTable(threshold); //初始化容器的大小
}
if (key == null)
return putForNullKey(value); //判断当前key 为null 将Null key添加到数组的第一个位置
int hash = hash(key); //将当前key进行hash 详情见下方
int i = indexFor(hash, table.length); //调用完hash算法后，详情见下方
for (Entry e = table[i]; e != null; e = e.next) { //循环判断当前数组下标为Entry的实体 将当前key相同的替换为最新的值
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i); //如果key都不同 则添加Entry.详情见下方
return null;
}
hashMap的hash算法剖析
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) { //判断当前k是否为string 和
return sun.misc.Hashing.stringHash32((String) k); //使用stringHash32算法得出key 的hash值
}
h ^= k.hashCode(); //调用key的hashCode 得出值 后使用"或"运算符
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
前面说过HashMap的数据结构是数组和链表的结合，所以我们当然希望这个HashMap里面的 元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表，这样就大大优化了查询的效率。
一个十进制数32768(二进制1000 0000 0000 0000)，经过上述公式运算之后的结果是35080(二进制1000 1001 0000 1000)。看出来了吗？或许这样还看不出什么，再举个数字61440(二进制1111 0000 0000 0000)，运算结果是65263(二进制1111 1110 1110 1111)，现在应该很明显了，它的目的是让“1”变的均匀一点，散列的本意就是要尽量均匀分布。使用上述算法后 "1"就变得很均匀了。
我们用table[index]表示已经找到的元素需要存储的位置。先判断该位置上有没有元素（这个元素是HashMap内部定义的一个类Entity， 基本结构它包含三个类，key，value和指向下一个Entity的next）,没有的话就创建一个Entity对象，在 table[index]位置上插入，这样插入结束；如果有的话，通过链表的遍历方式去逐个遍历，看看有没有已经存在的key，有的话用新的value替 换老的value；如果没有，则在table[index]插入该Entity，把原来在table[index]位置上的Entity赋值给新的 Entity的next，这样插入结束
}
indexFor 返回当前数组下标 ，
static int indexFor(int h, int length) {
return h & (length-1);
}
那么得到key 之后的hash如何得到数组下标呢 ？把h与HashMap的承载量（HashMap的默认承载量length是16，可以自动变长。在构造HashMap的时候也可以指定一个长 度。这个承载量就是上图所描述的数组的长度。）进行逻辑与运算，即 h & (length-1)，这样得到的结果就是一个比length小的正数，我们把这个值叫做index。其实这个index就是索引将要插入的值在数组中的 位置。第2步那个算法的意义就是希望能够得出均匀的index，这是HashTable的改进，HashTable中的算法只是把key的 hashcode与length相除取余，即hash % length，这样有可能会造成index分布不均匀。
首先来解释一下为什么数组大小为2的幂时hashmap访问的性能最高？
看下图，左边两组是数组长度为16（2的4次方），右边两组是数组长度为15。两组的hashcode均为8和9，但是很明显，当它们和1110“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，8和9会被放到同一个链表上，那么查询的时候就需要遍历这个链表，得到8或者9，这样就降低了查询的效率。同时，我们也可以发现，当数组长度为15的时候，hashcode的值会与14（1110）进行“与”，那么最后一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！
void addEntry(int hash, K key, V value, int bucketIndex) {
//// 若HashMap的实际大小 不小于 “阈值”，则调整HashMap的大小
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
//// 设置“bucketIndex”位置的元素为“新Entry”，// 设置“e”为“新Entry的下一个节点”
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
//将当前key 和value添加到Entry[]中
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry e = table[bucketIndex]; //将第一个就得table 复制个新的entry
table[bucketIndex] = new Entry<>(hash, key, value, e); //将当前新的Entry 复制个table[bucketIndex] 旧的table[bucketIndex] 和新的table[buckIndex]之间用next关联。第一个键值对A进来，通过计算其key的hash得到的index=0，记做:table[0] = A。一会后又进来一个键值对B，通过计算其index也等于0，现在怎么办？HashMap会这样做: B.next = A ,table[0] = B,如果又进来C,index也等于0,那么 C.next = B ,table[0] = C；这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起
size++; //容量加1
}
以上就是HashMap添加元素时的过程解析
那么如何get元素呢？
public V get(Object key) {
if (key == null) return getForNullKey(); //当前key是否为null 如果为null值返回table[0]这个value
Entry entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final EntrygetEntry(Object key) {
if (size == 0) { return null; } //判断容量是否大于0
int hash = (key == null) ? 0 : hash(key); //对当前key 进行hash hash后得到一个值
for (Entry e = table[indexFor(hash, table.length)]; //获取当前Entry 循环遍历
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
扩展问题:
1.当前我们的hashMap中越来越大的之后，"碰撞"就越来越明显，那么如何解决碰撞呢？扩容！
当hashmap中的元素个数超过数组大小capti*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能。比如说，我们有1000个元素new HashMap(1000), 但是理论上来讲new HashMap(1024)更合适，不过上面annegu已经说过，即使是1000，hashmap也自动会将其设置为1024。 但是new HashMap(1024)还不是更合适的，因为0.75*1000 < 1000, 也就是说为了让0.75 * size > 1000, 我们必须这样new HashMap(2048)才最合适，既考虑了&的问题，也避免了resize的问题
HashMap的两种遍历方式
第一种
Map map = newHashMap();
Iterator iter = map.entrySet().iterator();
while(iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Object key = entry.getKey();
Object val = entry.getValue();
}
效率高,以后一定要使用此种方式！
第二种
Map map = newHashMap();
Iterator iter = map.keySet().iterator();
while(iter.hasNext()) {
Object key = iter.next();
Object val = map.get(key);
}
效率低,以后尽量少使用！
归纳
简单地说，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，
也会根据hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。
G. Hash表及其应用
散列表，也叫做哈希表。
它基于数组的随机访问的特性，来拓展延伸，从而实现了散列表，为什么这样说呢，我们举一个例子来看看。
假设学校举行运动会，对100个进行编号，我们现在希望实现通过编号来快速找到某一个学生，该怎么实现呢，我们可以维护一个数组，将每一个学生的编号放到同样的数组下标内，比如1号放到数组下标为1的位置，接下来额以此类推，这样就能够实现快速随机访问，在O(1)的时间复杂度内就找到这个学生。
也许这样你看不出用到了散列思想，但这确实就是使用了散列的思想，将数组下标和学生编号进行了映射，只不过映射规则非常简单，就是f(n) = n。
但是现实时不会这么简单的，现在要求编号要复杂一点，用 6 位数字来表示。比如 051167，其中，前两位 05 表示年级，中间两位 11 表示班级，最后两位还是原来的编号 1 到 89。这个时候我们该如何存储选手信息，才能够支持通过编号来快速查找选手信息呢？
依然时通过散列的思想，我们可以截取编号的后两位作为数组下标，存储选手信息，当我们要查询时，也截取后两位作为数组下标，到数组内去查询，这样就能够实现快速查询。
其中，参赛选手的编号我们叫作键（key）或者关键字。我们用它来标识一个选手。我们把参赛编号转化为数组下标的映射方法就叫作散列函数（或“Hash 函数”“哈希函数”），而散列函数计算得到的值就叫作散列值（或“Hash 值”“哈希值”）。拿上面那个来说，关键字是051167，我们通过hash函数，即截取后两位，计算得到hash值67。
可以看到的是，hash函数是一个非常重要的东西，如何构造一个好的hash函数也是非常重要的，通过学习，我目前知道的是3点：
1：hash值是一个非负整数
2：如果key1==key2 hash(key1) == hash(key2)
3：如果key1!=key2 hash(key1) != hash(key2)
第一点很好理解，因为我们要维护成数组的下标，那么负数和非整数都是不行的；第二点也好理解，如果两个key相同，那么经过同一个hash函数计算，他们得到的值也必须要一样。第三点要好好理解一下，不同的key得到的hash值不一样，也就是这一点，引出了hash冲突这样一个概念。
因为即使最好的hash算法，也无法保证两个不一样的key得到的hash值一定不一样。
计既然无法解决，那么就要找其他的方法了。
经典的方法有链表法和开放寻址法。
开放寻址法：
这个比较好理解，就是如果计算得到的hash值在数组内已经有数据了，那我们就在紧接下一个寻找，如果没有数据，就插入到这个位置，这种方法不是非常好。
为了保证散列表的性能，我们会维护一个 装载因子 的概念。
装载因子： 填入表中的元素个数 / 散列表的长度
装载因子越小，发生散列冲突的概率就越小，性能就越好，如果装载因子越大，那么性能就会迅速下降，不过装载因子越小，那么需要消耗的内存就越大，如果不考虑性能，装载因子可以超越1.
链表法：
链表法比较常用
介绍了散列表的基本概念和一些散列冲突的解决方法，拿我们来看看究竟怎么样，才能设计一个优秀的企业级的散列表呢？
设计散列表，最关键的就是散列函数的设计，一个好的散列函数，既能够快速计算，也能够让散列冲突的概率较为小。既然要计算快速，那么这个散列函数就必然不能够太复杂，不然计算时间就较为耗时，其次也要保证计算出来的hash值要平均分布，否则一个槽出现的概率非常大，那么散列冲突的概率就大大提升。
我们之前说过，hash函数是有一个装载因子的概念的，对于动态的散列表，我们不断进行插入操作，它的装载因子势必会扩大，当装载因子过大时，hash表的性能就会下降，这个时候，就需要对hash表进行扩容，这样装载因子就会下降，对于数组的扩容，我们都可以很好的实现，不过对于散列表的扩容，就不是简单的移动数据这么简单了。
可以看到，当我们新建了一个数组后，原来hash表中的内容就要重新计算hash值，然后存放到新的哈市、表中，并不是简单的移动就能解决的。
不过，这样扩容，如果数据量很大，那么效率就必然很低下，怎么解决呢，我们可以不立刻拷贝数据到新的hash表里面，可以每新插入一个数据就将老的表里面的数据拿一个到新的表里面，这样就可以不一次性拷贝数据，效率就会得到提升。
接下啦看如何选择合适的hash冲突解决法：
当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是 Java 中的ThreadLocalMap使用开放寻址法解决散列冲突的原因。
基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。
this.hash = var1;
}
return var1;
}
H. 哈希表、哈希算法、一致性哈希表
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。它通过把关键码映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数（哈希函数），存放记录的数组叫做散列表。
优点：
哈希表可以提供快速的操作。
缺点：
哈希表通常是基于数组的，数组创建后难于扩展。
也没有一种简便的方法可以以任何一种顺序〔例如从小到大）遍历表中的数据项 。
综上， 如果不需要有序遍历数据，井且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。
1. 使用哈希函数将被查找的键转换为数组的索引。
2. 处理哈希碰撞冲突。
若关键字为 k ，则其值存放在 f(k) 的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系 f 为散列函数，按这个思想建立的表为散列表。
若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为 均匀散列函数 (Uniform Hash function)，这就是使关键字经过散列函数得到一个"随机的地址"，从而减少碰撞。
散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位。
一个好的散列函数一般应该考虑下列因素 ：
1.计算简单，以便提高转换速度。
2.关键词对应的地址空间分布均匀，以尽量减少冲突。
1. 直接寻址法
取关键字或者关键字的某个线性函数值作为哈希地址,即H(Key)=Key或者H(Key)=a*Key+b(a,b为整数),这种散列函数也叫做自身函数.如果H(Key)的哈希地址上已经有值了,那么就往下一个位置找,直到找到H(Key)的位置没有值了就把元素放进去。
2. 数字分析法
数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。
3. 平方取中法
取关键字平方后的中间几位作为散列地址。这种方法的原理是通过取平方扩大差别，平方值的中间几位和这个数的每一位都相关，则对不同的关键字得到的哈希函数值不易产生冲突，由此产生的哈希地址也较为均匀。该方法适用于关键字中的每一位都有某些数字重复出现频度很高的现象。
4. 折叠法
折叠法是将关键字分割成位数相同的几部分,最后一部分位数可以不同,然后取这几部分的叠加和(注意:叠加和时去除进位)作为散列地址。
数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐,然后相加;间界叠加是从一端向另一端沿分割界来回折叠,然后对齐相加。
该方法适用于关键字特别多的情况。
5. 随机数法
选择一个随机数,作为散列地址,通常用于关键字长度不同的场合。
6. 除留余数法
取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址.即H(Key)=Key MOD p,p<=m.不仅可以对关键字直接取模,也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选得不好，则很容易产生冲突。
对不同的关键字可能得到同一散列地址，即 k1≠k2 ，而 f(k1)=f(k2) ，这种现象称为碰撞(英语:Collision)。具有相同函数值的关键字对该散列函数来说称做同义词。
通过构造性能良好的散列函数，可以减少冲突，但一般不可能完全避免冲突，因此解决冲突是哈希法的另一个关键问题。 创建哈希表和查找哈希表都会遇到冲突，两种情况下解决冲突的方法应该一致。
下面以创建哈希表为例，说明解决冲突的方法。
1.开放寻址法
这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H(key)出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：Hi=(H(key)+di)%m i=1，2，…，m-1,其中H（key）为哈希函数，m 为表长，di称为增量序列，i为碰撞次数。增量序列的取值方式不同，相应的再散列方式也不同。增量序列主要有以下几种：
(1) 线性探测再散列
di=1，2，3，…，m-1
这种方法的特点是：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。
(2)二次探测再散列
di=12，-12，22，-22，…，k2，-k2( k<=m/2 )
这种方法的特点是：冲突发生时，在表的左右进行跳跃式探测，比较灵活。
(3)伪随机探测再散列
di=伪随机数序列。
线性探测再散列的 优点 是：只要哈希表不满，就一定能找到一个不冲突的哈希地址，而二次探测再散列和伪随机探测再散列则不一定。线性探测再散列容易产生“二次聚集”，即在处理同义词的冲突时又导致非同义词的冲突。
其实除了上面的几种方法，开放寻址法还有很多变种，不过都是对di有不同的表示方法。（如双散列探测法：di=i*h2(k)）
2.再哈希法
这种方法是同时构造多个不同的哈希函数：Hi=RHi（key），i=1，2,3，…,n。
当哈希地址H1=RH1（key）发生冲突时，再计算H2=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
3.链地址法(拉链法)
这种方法的基本思想是将所有哈希地址相同的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表（数组）中，因而查找、插入和删除主要在同义词链中进行。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。链地址法适用于经常进行插入和删除的情况。
拉链法的优点
与开放寻址法相比，拉链法有如下几个优点：
(1)拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
(2)由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
(3)开放寻址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中理论上可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；（散列表的装填因子定义为：α= 填入表中的元素个数 / 散列表的长度）
注：HashMap默认装填因子是0.75。
(4)在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放寻址法构造的散列表，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填入散列表的同义词结点的查找路径。这是因为各种开放寻址法中，空地址单元都被理解没有查找到元素。 因此在用开放寻址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。
拉链法的缺点
拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放寻址法较为节省空间，此时将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放寻址法中的冲突，从而提高平均查找速度。
4、建立公共溢出区
这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表(在这个方法里面是把元素分开两个表来存储)。
散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。
查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。
影响产生冲突多少有以下三个因素:
1. 散列函数是否均匀;
2. 处理冲突的方法;
3. 散列表的装填因子。
散列表的装填因子
定义为:α= 填入表中的元素个数 / 散列表的长度
α是散列表装满程度的标志因子。由于表长是定值，α与"填入表中的元素个数"成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大;α越小，填入表中的元素较少，产生冲突的可能性就越小。
实际上，散列表的平均查找长度是装填因子α的函数，只是不同处理冲突的方法有不同的函数。
这个HASH算法不是大学里数据结构课里那个HASH表的算法。这里的HASH算法是密码学的基础，了解了hash基本定义，就不能不提到一些着名的hash算法，MD5 和 SHA-1 可以说是目前应用最广泛的Hash算法，而它们都是以 MD4 为基础设计的。
Hash算法在信息安全方面的应用主要体现在以下的3个方面:
⑴ 文件校验
我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗 数据篡改 的能力，它们一定程度上能检测出数据传输中的信道误码，但却不能防止对数据的恶意破坏。
MD5 Hash算法的"数字指纹"特性，使它成为目前应用最广泛的一种文件完整性 校验和 (Checksum)算法，不少Unix系统有提供计算md5 checksum的命令。
⑵ 数字签名
Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在 数字签名 协议中，单向散列函数扮演了一个重要的角色。对 Hash 值，又称"数字摘要"进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。
⑶ 鉴权协议
如下的鉴权协议又被称作挑战--认证模式:在传输信道是可被侦听，但不可被篡改的情况下，这是一种简单而安全的方法。
一致性哈希表简称DHT，主要应用于分布式缓存中，可以用来解决分布式存储结构下动态增加和删除节点所带来的问题。比如，一个分布式的存储系统，要将数据存储到具体的节点上，如果采用普通的hash方法，将数据映射到具体的节点上，如key%N（key是数据的key，N是机器节点数），如果有一个机器加入或退出这个集群，则所有的数据映射都无效了，如果是持久化存储则要做数据迁移，如果是分布式缓存，则其他缓存就失效了。
判定哈希算法好坏的四个定义 ：
1、平衡性(Balance)：平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。
2、单调性(Monotonicity)：单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。
3、分散性(Spread)：在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。 分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。
4、负载(Load)：负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的， 因此好的哈希算法应能够尽量降低缓冲的负荷。
在分布式集群中，对机器的添加删除，或者机器故障后自动脱离集群这些操作是分布式集群管理最基本的功能。如果采用常用的hash取模算法，那么在有机器添加或者删除后，很多原有的数据就无法找到了，这样严重的违反了单调性原则。接下来主要说明一下一致性哈希算法是如何设计的。
以SpyMemcached的ketama算法来说，思路是这样的：
把数据用hash函数，映射到一个很大的空间里，如图所示。数据的存储时，先得到一个hash值，对应到这个环中的每个位置，如k1对应到了图中所示的位置，然后沿顺时针找到一个机器节点B，将k1存储到B这个节点中。
如果B节点宕机了，则B上的数据就会落到C节点上，如下图所示：
这样，只会影响C节点，对其他的节点A，D的数据不会造成影响。然而，这又会造成一个“雪崩”的情况，即C节点由于承担了B节点的数据，所以C节点的负载会变高，C节点很容易也宕机，这样依次下去，这样造成整个集群都挂了。
为此，引入了“虚拟节点”的概念：即把想象在这个环上有很多“虚拟节点”，数据的存储是沿着环的顺时针方向找一个虚拟节点，每个虚拟节点都会关联到一个真实节点，如下图所使用：
图中的A1、A2、B1、B2、C1、C2、D1、D2都是虚拟节点，机器A负载存储A1、A2的数据，机器B负载存储B1、B2的数据，机器C负载存储C1、C2的数据。由于这些虚拟节点数量很多，均匀分布，因此不会造成“雪崩”现象。
I. 加密、签名、证书的作用及运用场景
本文主要是简单介绍了常见的加密类型、各自的运用场景、为什么需要数字签名和数字证书、HTTPS涉及到的加密流程等。这里主要从使用者的角度出发，对算法本身不做过多介绍。
对称/非对称加密均属于 可逆加密，可以通过密钥将密文还原为明文 。
有时候，我们希望明文一旦加密后，任何人（包括自己）都无法通过密文逆推回明文，不可逆加密就是为了满足这种需求。
不可逆加密主要通过 hash算法实现：即对目标数据生成一段特定长度hash值 ；无论你的数据是1KB、1MB、1GB，都是生成特定长度的一个Hash值（比如128bit）。这里大家应该能感受到一点 不可逆 的味道，加密后128bit的hash值显然无法还原出1个G甚至更大的不规则数据的， hash可以看做是原来内容的一个摘要 。
常见算法：
小明给小红写信：
经过九转十八弯后，信的内容有可能：1. 被窥视 2. 被篡改（冒充小明发送假消息） ：
小红先 生成对称加密的密钥key1 ，然后通过一个安全的渠道交予小明。
传输数据时，小明 使用key1加密 ，而小红收到后再 使用key1解密 。
这时候 中间者既看不到原来的内容，也没办法篡改 （因为没有密钥）：
【对称加密】实现简单，性能优秀 ，算法本身安全级别高。然而对 密钥的管理 却是个很头疼的问题：一旦密钥交到对方手里，对方对密钥的保管能力 我方是没办法控制 的，一旦对方泄露的话，加密就形同虚设了。
相对而言，【非对称加密】的公钥就没有这个忧虑，因为 公钥 的设计就是为了 可以公开的 ，尽管对方泄露，我方也不会有任何损失。
小红生成一对公私钥，自己持有私钥（pri_key1），将公钥（pub_key1）交予小明。
传输数据时，小明使用 公钥加密 ，小红使用 私钥解密 。
因为 中间者没有私钥，公钥加密的内容是无法获取的 。此时达到了 防窥视 的效果：
然而因为 公钥是可以公开的 ，如果 中间者知晓公钥 的话，尽管没有办法看到原来的内容，却 可以冒充小明发送假消息 ：
这时小红在想，如果小明发送消息时，能带上 只有他自己才能生成 的数据（字符串），我就能 验证是不是小明发的真实消息 了。
通常这个 能证实身份的数据（字符串） 被称之为 数字签名（Signature）
小明再生成一对公私钥 ，自己持有私钥（pri_key2），将公钥交予小红（pub_key2）。
当小明传输数据时（可能很大），除了公钥加密明文之外，还要带上签名：(1) 对明文做一个hash摘要 (2)对摘要进行私钥加密，加密结果即签名（传输内容=内容密文+签名）
小红收到后：(1) 解密签名获取hash (2)解密内容密文，对解密后的明文进行hash；如果两个hash一致，说明验签通过。
尽管中间者修改了传输内容，但因为签名无法冒认（没有私钥），小红验签失败，自然不会认可这份数据：
通常 非对称加密要做到防窥视和防篡改，需要有两对公私钥 ：对方的公钥用于内容加密，自己的私钥用于签名（让对方验证身份）。
因为HTTP协议明文通信的安全问题，引入了HTTPS：通过建立一个安全通道（连接），来保证数据传输的安全。
服务器是 没办法直接将密钥传输到浏览器的 ，因为在 安全连接建立之前，所有通信内容都是明文的 ，中间者可窥视到密钥信息。
或许这时你想到了非对称加密，因为公钥是不怕公开的：
然而在第2步， 中间者可以截取服务器公钥，并替换成了自己的公钥 ，此时加密就没意义了：
为了 防止公钥被假冒，数字证书（digital certificate ）便诞生了 。
当服务器需要告诉浏览器公钥时，并不是简单地返回公钥，而是响应 包含公钥信息在内的数字证书 。
证书主要包含以下内容：
浏览器通过 【颁发机构的公钥】进行解密验签 ，验签通过即说明证书的真实性，可以放心取 证书拥有者的公钥 了。（ 常用CA机构的公钥都已经植入到浏览器里面 ）
数字证书只做一件事： 保证 服务器响应的 公钥是真实的 。
以上保证了 [浏览器⇒服务器] 是加密的，然而 [服务器⇒浏览器] 却没有（上图第4步）；另外一个是 性能问题 ，如果所有数据都使用非对称加密的话，会消耗较多的服务器资源，通信速度也会受到较大影响。
HTTPS巧妙地结合了非对称加密和对称加密，在保证双方通信安全的前提下，尽量提升性能。
HTTPS（SSL/TLS）期望 建立安全连接后，通信均使用【对称加密】 。
建立安全连接的任务就是让 浏览器-服务器协商出本次连接使用的【对称加密的算法和密钥】 ；协商过程中会使用到【非对称加密】和数字证书。
特别注意的是：协商的密钥必须是不容易猜到（足够随机的）：
其中比较核心的是随机数r3（pre-master secret），因为之前的r1、r2都是明文传输的， 只有r3是加密传输 的。至于为什么需要三个随机数，可以参考：
以上是一个比较简单的HTTPS流程，详细的可以参考文末的引用。
参考资料：
[1] 数字证书应用综合揭秘
[2] SSL/TLS协议运行机制的概述
[3] 图解SSL/TLS协议
[4] 《图解HTTP》