一、HashMap 和 HashSet  -- 无序表
他俩唯一的区别是一个是 K-V，另一个是 K。

1. HashMap
如果K是基础类型，那么传入是拷贝的一份值放入哈希表里面，不管有多大，按值传递。
如果K是自定义类型，可能有非常多的数据项。在从换入哈希表的时候，哈希表会拷贝地址放进去，而不是把里面的所有内容那个拷贝一份放进去。
比较是否是同一个值，比较的“基础类的值”和“自定义类的地址”。

二、TreeMap 和 TreeSet  -- 有序表
一个是K-V，另一个是K。
有序表要求K是可以比较的，也就是继承Comparable。
    - firstKey:我最小
    - lastKey:我最大
    - floorKey(8):小于等于8里面，离8最近的数字是谁
    - ceilingKey(8):大于等于8里面，离8最近的数字是谁
以上操作都是(lgn)级别的时间复杂度。
红黑树、AVL数、size-balance-tree、跳表。时间复杂度都一样，只是底层实现结构不一样。

如果K是基础类型，按值排序。
如果K是引用类型，需要传入比较器。
TreeSet<Node> set = new TreeSet<>(new NodeComparable());
--------------------
哈希函数：
*1. 能把数据几乎均匀的离散到整个区域上。
2. same in --> same out(不随机，固定的输入就会有固定的输出)
3. 哈希冲突概率极低。
4. 无论输入的多少，输出都是有限值
算法逻辑：初始值 ---哈希函数---> out集合 ---%m---> 取余运算，得到自己的坐标
整个过程，保证out集合均匀分布，取余之后，然后还要把证坐标空间均匀分布。（个人认为bit数据集的原因）

实战：对于一个最大32G的数据，我们只有1G的内存可以用，需要找出里面次数最大的数字。
利用哈希函数将32G的数据均匀分在100个小包里面，对于这100个小包，相同的数据一定在一个包。
那么我们只需要找出这100个小包里面的次数最多的值，然后比较这100个里面谁最多即可，就解决了数据量大的问题。
这里我们利用了哈希函数会对数据进行均匀分配的特性。

经典的哈希表原理：
每次使用哈希表，时间复杂度是O(logN)，因为比如有N数据的时候，我们扩容需要logN次。
每次扩容都需要把原来的数据更新到新的扩容表上，所以是N。
总的就是NlogN，那么平均到N个数据的话，一次就是logN。
1. 数据量N不会过多的时候，logN是特别小的一个常数。
2. 对于虚拟机语言，如JVM可以通过离线扩容技术进行再次加速。
    也就是当数据量大的时候，用户接着用；在用户不用的时候，JVM继续进行扩容，不会占用用户的时间。
所以在以上两个加速下，O(logN)是接近于O(1)的，时间复杂度是很低的。

Java的改进：数据+链表+红黑树。
其他语言也有各自的改进。

--------------------
布隆过滤器：
解决类似于黑名单系统、爬虫、去重的一个工具。功能需求：加入集合、是否在集合里面。
作用： 在大数据量下，可以减少一定的使用内存，且允许有一定的失误率。
算法原理： 和多线程结合，爬虫过的数据，会计入黑名单，然后每次爬取的时候，会去黑名单里面看是否已经爬取过了。
失误： 本来是白的，误报为黑的，可以通过人为的方式，让失误率很低。
比如有个url是白的，误报为黑色，然后访问不到了，但是我们可以通过别的url访问到这个白的。
这个失误率不可避免，只是可以设计的很低。

通过 ”位图“ 实现 ———— bitArr，bitMap
做出一个数组，每个位置只有1bit。

通过位图的实现，一个url进行k次哈希运算，然后把对应的k个位置描黑，如果已经是黑的，那么保持黑的。
这时候就会有一定的失误率，就是一个白的url计算完k次之后，对应的位置都是黑色，因为之前其他url描黑的。
导致了这个白色，我们误判成黑色，这是不可避免的失误率。

以上数据有：N个数据集，m个bit位可用，k次哈希计算。
当N>>m的时候，这个冲突是极大的，所以这两个的关系要合理。
k可以理解为在多少个位置按下属于这个数据的指纹，
当指纹较少或者较多，容易出现较高的失误率，所以这个是一个和N、m相关的值。

----------------------------

一致性哈希原则：

用于进行负载均衡和数据快速迁移。
比如一个公司有三台服务器，通过哈希计算，可以让三台服务器的哈希值彼此均匀。
然后形成一个环，如imgs的ConsistencyHash图所示。
在对一个数据进行计算的时候，会得到一个哈希值，然后顺时针找哈希值最近的一个服务器，把数据放进去。
那么当添加新的服务器的时候，我们虽然保证了之前的三个均匀分布在数据环上，但是这个新的加进去后。
就会有两个服务器分担较少的部分，另外两个还是原来的环长度部分，从而出现负载不均衡情况。

那么我们可以对一个服务器，对它计算出1000个哈希值如：
服务器A，对应的哈希值是：[a1, a2,..., a1000]
服务器B，对应的哈希值是：[b1, b2,..., b1000]
服务器C，对应的哈希值是：[c1, c2,..., c1000]
那么这3000个虚拟节点均匀的放在换上，保证我们随机圈主一部分，里面的ai、bi、ci都是差不多相等的。
从而使得数据会进到临近的ai或者bi或者ci。
当我们需要加入新的服务器的时候，我们也可以对这个服务器也生成1000个虚拟节点均匀的放入环中。
对插入位置的顺时针的第一个虚拟节点的数据重新计算，进行数据前移。
并且这个虚拟节点的个数不一定都是一样的，我们可以设置不同的虚拟节点个数，从而控制他们的环上面的权重。

综上所述：哈希一致性就是通过虚拟节点技术，使用哈希值的均匀分布特性。
使得这些虚拟节点代表这个的服务器，均匀分布在数值环上，从而实现数据集的均匀存储，实现负载均衡。
并且有新的服务器进来的时候，也只需要生成指定数量的虚拟节点，然后均匀防止在环上，完成数据迁移即可。