hash（散列表）

应用场景

1、Hash主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做Hash值. 也可以说，Hash就是找到一种数据内容和数据存放地址之间的映射关系。

2、查找：哈希表，又称为散列，是一种更加快捷的查找技术。我们之前的查找，都是这样一种思路：集合中拿出来一个元素，看看是否与我们要找的相等，如果不等，缩小范围，继续查找。而哈希表是完全另外一种思路：当我知道key值以后，我就可以直接计算出这个元素在集合中的位置，根本不需要一次又一次的查找！

举一个例子，假如我的数组A中，第i个元素里面装的key就是i，那么数字3肯定是在第3个位置，数字10肯定是在第10个位置。哈希表就是利用利用这种基本的思想，建立一个从key到位置的函数，然后进行直接计算查找。

3、Hash表在海量数据处理中有着广泛应用。

哈希表

时间复杂度

几乎O（1）

散列函数

• 除法散列法
• 平方散列法
• 斐波那契散列法
  实际中运用的的散列函数没有这么简单， 下面来看看几个实际运用的散列方法
  String类的hashCode方法如下所示：

 public int hashCode() { 
    int h = hash; 
    if (h == 0 && value.length > 0) { 
        char val[] = value; 
        for (int i = 0; i < value.length; i++) { 
            h = 31 * h + val[i]; 
        } 
        hash = h; 
    } 
    return h; 
}

Double类的hashCode方法：

public int hashCode() { 
    return Double.hashCode(value); 
} 

public static int hashCode(double value) { 
    long bits = doubleToLongBits(value); 
    return (int)(bits ^ (bits >>> 32)); 
}

我的另外一篇博客Redis struct 有讲过Redis的散列函数， 里面详细讲了实际运用中的散列函数， 其中比较出名的murmurhash方法很值得看一下。

冲突

• 建立公共溢出区
• 开放地址法
• 再哈希法
• 链地址法（最常用， 包括Redis， STL）

哈希表扩展

1.可以参考Redis struct 有讲过Redis的中哈希扩展方法， STL中hashset底层用得也是hashtable， 源码对比之后个人觉得Redis的处理更具实用性， 从触发扩展条件到扩展方式都有差别；

高级应用

1. 字典树（http://www.jianshu.com/p/40b55883aa41）
2. 分布式哈希
3. 一致性哈希
   第一次看到这个，是在分布式存储的一本书上， 也是一种在分布式领域很好用的结构， 避免了大量数据拷贝的问题, 详情请看
   一致性HASH算法详解