什么是Hash？什么是Hash表？什么是Hash冲突？

HASH

  哈希（散列）是指：任意长度的输入经过hash算法转化为固定长度的输出。

    public static String strToHashKey(String k) {
        String tmpKey;
        try {
            final MessageDigest mDigest = MessageDigest.getInstance("MD5");
            mDigest.update(k.getBytes());
            tmpKey = bytesToHexString(mDigest.digest());
        } catch (NoSuchAlgorithmException e) {
            tmpKey = String.valueOf(k.hashCode());
        }
        return tmpKey;
    }

    private static String bytesToHexString(byte[] b) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < b.length; i++) {
            String hex = Integer.toHexString(0xFF & b[i]);
            if (hex.length() == 1) {
                sb.append('0');
            }
            sb.append(hex);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        String str = "TEST_HASH_01_STR";
        String str2 = "TEST_HASH_02_STR";
        String str3 = "TEST_HASH_03_STR";
        String str4 = "TEST_HASH_04_STR";

        System.out.println(str + "的hash值= " + strToHashKey(str));
        System.out.println(str2 + "的hash值= " + strToHashKey(str2));
        System.out.println(str3 + "的hash值= " + strToHashKey(str3));
        System.out.println(str4 + "的hash值= " + strToHashKey(str4));
    }

控制台输出
--------------------------------------------------------
TEST_HASH_01_STR的hash值= 488ffb5451eca9a66e5841f2d33127c7
TEST_HASH_02_STR的hash值= 4f637e42de1540f7f51687a1e776a5aa
TEST_HASH_03_STR的hash值= 2008b46e01406eb4a44d3176a23cdec2
TEST_HASH_04_STR的hash值= 3e8eb32d529479a488201c53232e79df

哈希的使用

Hash取模 (hash(输入) % n)

  现在有3个服务器，要做负载均衡，就可以对请求的ip地址或者用户的id等使用Hash函数，然后将计算得出的Hash值对机器数取模，余数为几，就把请求分配到相应的服务器上。

Hash%机器数量

  缺点：新增服务器或者服务器宕机的时候，绝大多数请求基本上都需要重新映射到另一个节点。这种变动有时候是不能接受的。比如在Web负载均衡的场景下，session会保存在每个节点里。当然，如果你是“无状态”的服务，那不会存在这个问题。因为如果增加或者删除了一个节点，就会导致几乎所有的数据都需要重新迁移。

一致性Hash

  尽可能降低分布式环境下，通过哈希定位运算确认元素位置的集群服务受机器数的影响，避免使用固定值取模，改为范围定位的方式。

上面的取模运算的除数是机器数，而一致性Hash的除数是2^32（int类型的最大值）。从0到232 - 1,首尾相连构成了一个环。

一致性哈希

我们先对服务器节点的IP进行Hash，然后除以2^32
得到服务器节点在这个Hash环中的位置。如果有请求进来了，同样进行Hash然后处于2^32求余。如果落在Hash环上，然后顺时针找到第一个节点，这个节点就负责处理这个请求。

优点：解决因为横向伸缩导致的大规模数据变动。
缺点：一致性Hash算法在节点数量较少的时候，会出现分布不均匀的问题。
解决方案就是在Hash环上增加虚拟节点。

虚拟节点

哈希的应用

  1.密码学和数字签名。
  2.文件的完整性检查。
  3.基于HASH的数据结构。

哈希算法的特点

  1.不可逆：不可以根据hash值计算出原值。
  2.效率高，HASH运算能快速计算出结果。
  3.冲突少，优秀的哈希算法具备的特点。

哈希算法

（1）MD4

  MD4（RFC 1320）是 MIT 的Ronald L. Rivest在 1990 年设计的，MD 是 Message Digest（消息摘要） 的缩写。它适用在32位字长的处理器上用高速软件实现——它是基于 32位操作数的位操作来实现的。

（2）MD5

  MD5（RFC 1321）是 Rivest 于1991年对MD4的改进版本。它对输入仍以512位分组，其输出是4个32位字的级联，与 MD4 相同。MD5比MD4来得复杂，并且速度较之要慢一点，但更安全，在抗分析和抗差分方面表现更好。

（3）SHA-1及其他

  SHA1是由NIST NSA设计为同DSA一起使用的，它对长度小于264的输入，产生长度为160bit的散列值，因此抗穷举（brute-force）性更好。SHA-1 设计时基于和MD4相同原理，并且模仿了该算法。

什么是Hash表？什么又是Hash冲突？

HASH表

  哈希表是基于数组的一种存储方式，它主要由哈希函数和数组构成。当要存储一个数据的时候，首先用一个函数计算数据的地址，然后再将数据存进指定地址位置的数组里面。这个函数就是哈希函数，而这个数组就是哈希表。

哈希冲突

  哈希是通过对数据进行再压缩，转为为固定长度的输出。但由于通过哈希函数产生的哈希值是有限的，而数据可能比较多，导致经过哈希函数处理后仍然有不同的数据对应相同的值。

哈希冲突的影响因素

装填因子（装填因子=数据总数 / 哈希表长）、哈希函数、处理冲突的方法

HASH冲突的解决方案

三种解决hash冲突的方法.jpg

1.开放地址方法

（1）线性探测

  按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上往后加一个单位，直至不发生哈希冲突。

（2）再平方探测

  按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上先加1的平方个单位，若仍然存在则减1的平方个单位。随之是2的平方，3的平方等等。直至不发生哈希冲突。

（3）伪随机探测

  按顺序决定值时，如果某数据已经存在，通过随机函数随机生成一个数，在原来值的基础上加上随机数，直至不发生哈希冲突。

2.链式地址法（HashMap的哈希冲突解决方法）

对于相同的值，使用链表进行连接。使用数组存储每一个链表。

优点：

（1）拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；

（2）由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；

（3）开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；

（4）在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。

缺点：
  指针占用较大空间时，会造成空间浪费，若空间用于增大散列表规模进而提高开放地址法的效率。

3.建立公共溢出区

  建立公共溢出区存储所有哈希冲突的数据。

4.再哈希法

  对于冲突的哈希值再次进行哈希处理，直至没有哈希冲突。