哈希函数

out = f(in)

  1. in -> 无穷，out -> string 有限

    • md5： 0 - 2^64^-1
    • sha1： 0 - 2^128^-1

  2. same in -> same out 不随机

  3. different in -> same out （哈希碰撞）

  4. 离散性和均匀性 （输入有规律，输出无规律）

in 通过hash函数得到 out 再取模 %m 就可以的带 0 - (m-1) 范围的数

题

1
一个大文件 无符号整数 (2^32^-1 就是 0- 42亿范围）有40亿个数，1g内存求出现次数最多的数是哪一个？

如果使用hash表来做 key - value ,key是(4B),value是int(4B), 一个数就要8B，如果40亿个数都不一样，就需要 320亿B（32G）。

对数据a 先使用 hash函数得到数 b，然后 % 100得到 0-99范围的数，相同的数据进同一个文件，不同的数种类上进不同文件。对每一个小文件使用hash表，然后求出这100个数的最大值。不怕同一种数太多，怕不同种的数太多，内存不够。

哈希表

表 + 链表（ in通过hash函数得到 out 再取模 %m 就）当 某条链表太长触发扩容 机制。n个字符串 ，会触发logn次扩容，最坏是logN。每一次扩容的代价是O(N)，每个数全部要计算hash，扩容的代价O（N * logN）。单次插入代价O（N * logN）/ N 就是logN，通过设置链表长度特别小，使logN特别小，就是O(1)。在使用的时候认为是O(1).

jvm等虚拟机语言，可以做到在扩容时使用旧表，扩容完使用新表。离线计算。

开放地址法

题

1.设计RandomPool结构

1
2
3
4
5
6
7
8
【题目】
设计一种结构，在该结构中有如下三个功能:
insert(key):将某个key加入到该结构，做到不重复加入
delete(key):将原本在结构中的某个key移除
getRandom():等概率随机返回结构中的任何一个key。

【要求】
lnsert、 delete和getRandom方法的时间复杂度都是O(1)

使用2张hash表

map1 (str -> index), 存放”A” -> 0…

map2 (index->str), 存放0 -> “A”…

size,

getRandom()如果存放了26个数，要等概率返回，使用系统提供的随机数生成，生成0-25的数，返回map2这个位置的str

delete(key)删除时不能让index区域出现洞，保证连续性。删除时，让最后一条区域填补这个洞。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public static class Pool<K> {
    private HashMap<K, Integer> keyIndexMap;
    private HashMap<Integer, K> indexKeyMap;
    private int size;

    public Pool() {
        this.keyIndexMap = new HashMap<>();
        this.indexKeyMap = new HashMap<>();
        this.size = 0;
    }

    public void insert(K key) {
        // 没加过加入
        if (!this.keyIndexMap.containsKey(key)) {
            this.keyIndexMap.put(key, this.size);
            this.indexKeyMap.put(this.size, key);
        }
    }

    public void delete(K key) {
        if (this.keyIndexMap.containsKey(key)) {
            int deleteIndex = this.keyIndexMap.get(key);
            int lastIndex = --this.size;
            K lastKey = this.indexKeyMap.get(lastIndex);
            this.keyIndexMap.put(lastKey, deleteIndex);
            this.indexKeyMap.put(deleteIndex, lastKey);
            this.keyIndexMap.remove(key);
            this.indexKeyMap.remove(lastIndex);
        }
    }

    public K getRandom() {
        if (this.size == 0) {
            return null;
        }
        int random = (int) (Math.random() * this.size);
        return this.indexKeyMap.get(random);
    }
}

布隆过滤器

解决黑名单过滤、对100亿url(64Byte)进行黑名单过滤过滤，如果使用hashset,需要640G内存。

爬虫去重，多个线程爬url, 如果已经爬过，就不要再爬，爬虫之间不要爬同一个。

集合有添加、有查询，没有查询、极大程度减少内存使用，允许有一定程度失误率。如果一个数据不在布隆过滤器中，可能会误报，但一个数据在布隆过滤器中，一定不会误报。

位图

bitmap, 基础类型数组,int[],long[]每一个占32bit、64bit

bit[] 每一位占1bit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class BitMap {
    public static void main(String[] args) {
        int arr[] = new int[10]; // 32bit * 10 320 bits

        // arr[0] int 0  - 31
        // arr[1] int 32 - 64
        // arr[2] int 64 - 95

        int i = 178; //得到178个 bit

        int numIndex = i / 32;
        int bitIndex = i % 32;

        // 拿到178位 状态
        int s = ((arr[numIndex] >> bitIndex) & 1);

        // 把178位状态改为1
        arr[numIndex] = arr[numIndex] | (1 << bitIndex);

        // 把178位状态改为0
        arr[numIndex] = arr[numIndex] & (~(1 << bitIndex));
    }
}

基础

是一个超大的位数组和几个哈希函数,假设集合里面有 3 个元素 {x, y, z}，哈希函数的个数为 3。首先将位数组进行初始化，初始化状态的维数组的每个位都设置位 0。对于集合里面的每一个元素，将元素依次通过 3 个哈希函数进行映射，每次映射都会产生一个哈希值，这个值对应位数组上面的一个点，然后将位数组对应的位置标记为 1。

添加元素

将要添加的元素分别通过k个哈希函数计算得到k个哈希值，这k个hash值对应位数组上的k个位置，然后将这k个位置设置为1。

查询元素

将要查询的元素分别通过k个哈希函数计算得到k个哈希值，这k个hash值对应位数组上的k个位置，如果这k个位置中有一个位置为0，则此元素一定不存在集合中，如果这k个位置全部为1，则这个元素可能存在。

hash函数到底多少个，bitmap到底多长。

优缺点

优点

  • 相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数（即hash函数的个数）
  • Hash 函数相互之间没有关系，方便由硬件并行实现
  • 布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势
  • 布隆过滤器可以表示全集，其它任何数据结构都不能。

缺点

  • 误算率（False Positive）是其中之一。随着存入的元素数量增加，误算率随之增加（误判补救方法是：再建立一个小的白名单，存储那些可能被误判的信息）。但是如果元素数量太少，则使用散列表足矣。
  • 一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位列阵变成整数数组，每插入一个元素相应的计数器加 1, 这样删除元素时将计数器减掉就可以了。然而要保证安全的删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

重要参数

n = 样本量， P = 失误率 单样本大小

m = - ( n * lnP / ln2^2^ ) 需要多少空间 0.0001失误率 ，100亿url,需要^26G^

k = （ln2 * (m/n) ）= 0.7 * (m/n) 向上取整

P真 = （1 - e^a^）(a = - n*k真/m真)

一致性哈希

数据服务器怎么组织， 数据种类均匀分配。有3台服务器、一个数据同算hash然后取模方法，觉定这个数据在哪个服务器存储。hash key怎么选择，让高、中、低频的数据均匀分配的key，身份证之类。上面的算法好像可以把图片均衡地分配到不同的服务器,但增加和减少服务器时，如果要重新算hash会造成数据迁移。

概念

决分布式缓存的问题。 在移除或者添加一个服务器时，能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系。一致性哈希解决了简单哈希算法在分布式哈希表中存在的动态伸缩等问题 。

一致性hash算法会建立一个有2^32个槽点(0 - 2^32-1^)的hash环，假设现在有A、B、C三台服务器，以A为例，会进行hash(A)%2^32^，得到一个0 - 2^32-1^之间的数，然后映射到hash环上

接下来，我们以m1为例，我们照样算出hash(m1)%2^32^的值，然后映射到hash环上，然后以该点出发，顺时针遇到的第一个服务器，即为数据即将存储的服务器。

如果这个时候在A - C之间插入了服务器D，请求获取getKey(m1)时，顺时针获得的服务器是D，从D上获取数据理所当然会失败，因为数据存在A上缓存。这样看缓存好像还是失效了。

虽然增加了节点D后，m1的缓存失效了，但是，分布在 A-B，B-C 以及 D-A上面的数据仍然有效，失效的只是C-D段的数据(数据存在A节点，但是顺时针获取的服务器是D)。这样就保证了缓存数据不会像hash算法那样大面积失效，同样起到减轻数据库压力的效果。

一致性Hash算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。

hash偏斜

A、B、C服务节点，如果接近于将hash环平均分配那固然理想，但是如果他们hash值十分相近,就会导致某一段直接会被大量分配，给某一节点大量分配，如果这时这个节点被删除，会有大量请求涌向相邻的节点，给这个节点带来巨大压力，这部分缓存也就失效了，导致了缓存雪崩。

如何保证节点的负载均衡？如何保证在添加节点后的负载均衡？

虚拟节点

如果我们的节点足够多，就应该可以防止服务器节点分布不均的问题了。

以A节点为例，虚拟构造出(A0,A1,A2….AN)，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。只要是落在这些虚拟节点上的数据，都存入A节点。读取时也相同，顺时针获取的是A0虚拟节点，就到A节点上获取数据，这样就能解决数据分布不均的问题。

虚拟节点读写大概流程为: 数据读写 -> 虚拟节点 -> 真实节点 -> 读写