Hash，从认识到理解，Hash是什么？散列是什么？映射是什么？哈希函数散列函数是什么？有了地址值为什么还需要哈希值？

这纯属个人的学习认识，有错的地方，希望各位指正。

散列函数也就是哈希函数；可以简单来说是一种映射关系，也就是y=f(x)，

可以说是一种可以满射但非单射的映射关系，比如MD5，这种128位的密码加密算法，也是解决不了单射，也就是有碰撞。128位是超大的数据，我算过64位就是16EB了，所以128位是人类根本用不完的，但确是可以用完的有限的。所以我说哈希是一种非单射且满射的对应关系，但是我们还是在努力的避免哈希碰撞，也就是想努力的实现单射状态（或双射）。

每当我们存入一个key，这个key就是x，根据key算出哈希值y，然后存储数据。

哈希为什么存在？（有了地址值为什么还需要哈希值）

这次我总算明白了，比如，Map<>  map = new Map<>(); 这个map在内存中只会有一个地址值（也就是整个Map使用一个地址值），而要寻找里面的Map的某个对象]怎么办？那就是使用哈希算法，由key（也就是），算出一个哈希值y，这个y就保存在对象头，相同的key一定得到相同的y。但是不同的key，也会得到一样的y。这也许和计算机只有0和1有关。如果得到相同的key，那可以用链表结构存储。

redis中集群分布，对哈希的理解：

RedisCluster采用的分区，所有的键根据哈希函数(CRC16[key]&16383)映射到[0,16383)区间内，编程上叫槽。

我先抛开CRC16[]这个算法，假设z=CRC16[key]&16383，y=CRC16[]，那么z=y&16383.。

先来说一下二进制运算符号&（and） |（或） ^

&： 0&0=0  1&0=0  0&1=0  1&1=1；（有0都为0，双1才为1）

|： 0&0=0  1&0=1  0&1=1  1&1=1；（有1都为1，双0才为0）

^： 0&0=0  1&0=1  0&1=1  1&1=0；（ 不同为1，同为0）

 

        z=y&16383；

16384是2的14次方，也就是这个哈希算法要用14位存储。

16383的二进制是：11111111111111。所以任何的数与它进行&运算都会得到一个14位以内的二进制数，而且最大就是16383，因为&运算，只有1&1才为1，其他都为0。所以这里运算出来的数是0~16384。

假如Redis集群有三台主机，每台主机分配一个槽，可以说是y区间，凡是落在这个区间的就归这台主机保存。

比如一条查询数据的信息，这整个信息会有一个key（也就是x），然后根据这里的哈希算法得到一个y，这个y肯定落在[0,16383]这个闭区间内，然后再分配给具体的主机保存。

总结：

1.任何长度的文件，都可以生成固定位数的hash值。

2.一般hash是不可逆的，也就是根据x可以算出y，根据y不能算出x。

3.key一样，hash值就一样。也就是相同的x，得到的y是一样的。

4.key不一样，hash值也可能一样，也就是不同的x，也可以得到一样的y。这也就是hash碰撞

它的模型可能如下：