Skip to content

Commit b92e005

Browse files
crossoverJiecrossoverJie
committed
🐛 Fixing a bug.img
1 parent 338851e commit b92e005

4 files changed

Lines changed: 30 additions & 30 deletions

File tree

‎docs/algorithm/Consistent-Hash.md‎

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -17,30 +17,30 @@
1717

1818
一致 Hash 算法是将所有的哈希值构成了一个环，其范围在 `0 ~ 2^32-1`。如下图：
1919

20-
![](https://ws1.sinaimg.cn/large/006tNc79gy1fn8kbmd4ncj30ad08y3yn.jpg)
20+
![](https://i.loli.net/2019/06/26/5d13931ace0d988790.jpg)
2121

2222
之后将各个节点散列到这个环上，可以用节点的 IP、hostname 这样的唯一性字段作为 Key 进行 `hash(key)`，散列之后如下：
2323

24-
![](https://ws3.sinaimg.cn/large/006tNc79gy1fn8kf72uwuj30a40a70t5.jpg)
24+
![](https://i.loli.net/2019/06/26/5d13931b42d3941564.jpg)
2525

2626
之后需要将数据定位到对应的节点上，使用同样的 `hash 函数` 将 Key 也映射到这个环上。
2727

28-
![](https://ws3.sinaimg.cn/large/006tNc79gy1fn8kj9kd4oj30ax0aomxq.jpg)
28+
![](https://i.loli.net/2019/06/26/5d13931b811c782755.jpg)
2929

3030
这样按照顺时针方向就可以把 k1 定位到 `N1节点`，k2 定位到 `N3节点`，k3 定位到 `N2节点`。
3131

3232
### 容错性
3333
这时假设 N1 宕机了：
3434

35-
![](https://ws3.sinaimg.cn/large/006tNc79gy1fn8kl9pp06j30a409waaj.jpg)
35+
![](https://i.loli.net/2019/06/26/5d13931ba4a0869451.jpg)
3636

3737
依然根据顺时针方向，k2 和 k3 保持不变，只有 k1 被重新映射到了 N3。这样就很好的保证了容错性，当一个节点宕机时只会影响到少少部分的数据。
3838

3939
### 拓展性
4040

4141
当新增一个节点时:
4242

43-
![](https://ws1.sinaimg.cn/large/006tNc79gy1fn8kp1fc9xj30ca0abt9c.jpg)
43+
![](https://i.loli.net/2019/06/26/5d13931bc818391034.jpg)
4444

4545
在 N2 和 N3 之间新增了一个节点 N4 ，这时会发现受印象的数据只有 k3，其余数据也是保持不变，所以这样也很好的保证了拓展性。
4646

@@ -49,14 +49,14 @@
4949

5050
当节点较少时会出现数据分布不均匀的情况：
5151

52-
![](https://ws2.sinaimg.cn/large/006tNc79gy1fn8krttekbj30c10a5dg5.jpg)
52+
![](https://i.loli.net/2019/06/26/5d13931c0392a99489.jpg)
5353

5454
这样会导致大部分数据都在 N1 节点，只有少量的数据在 N2 节点。
5555

5656
为了解决这个问题，一致哈希算法引入了虚拟节点。将每一个节点都进行多次 hash，生成多个节点放置在环上称为虚拟节点:
5757

58-
![](https://ws2.sinaimg.cn/large/006tNc79gy1fn8ktzuswkj30ae0abdgb.jpg)
58+
![](https://i.loli.net/2019/06/26/5d13931c3e2f146589.jpg)
5959

6060
计算时可以在 IP 后加上编号来生成哈希值。
6161

62-
这样只需要在原有的基础上多一步由虚拟节点映射到实际节点的步骤即可让少量节点也能满足均匀性。
62+
这样只需要在原有的基础上多一步由虚拟节点映射到实际节点的步骤即可让少量节点也能满足均匀性。

‎docs/algorithm/LRU-cache.md‎

Lines changed: 7 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
![](https://ws1.sinaimg.cn/large/006tNc79gy1fq3fey7n97j31340o8myw.jpg)
1+
![](https://i.loli.net/2019/06/26/5d13931b1ef2443865.jpg)
22

33
## 前言
44
LRU 是 `Least Recently Used` 的简写，字面意思则是`最近最少使用`。
@@ -676,7 +676,7 @@ public class LRUMap<K, V> {
676676

677677
### 初始化时
678678

679-
![](https://ws1.sinaimg.cn/large/006tNc79gy1fq3h4xsf4cj30dh09hglr.jpg)
679+
![](https://i.loli.net/2019/06/26/5d13931b9416744111.jpg)
680680

681681
### 写入数据时
682682

@@ -685,24 +685,24 @@ LRUMap<String,Integer> lruMap = new LRUMap(3) ;
685685
lruMap.put("1",1) ;
686686
```
687687

688-
![](https://ws4.sinaimg.cn/large/006tNc79gy1fq3h892nalj30ef09jdg2.jpg)
688+
![](https://i.loli.net/2019/06/26/5d13931c136d238581.jpg)
689689

690690

691691
```java
692692
lruMap.put("2",2) ;
693693
```
694-
![](https://ws3.sinaimg.cn/large/006tNc79gy1fq3hayffy1j30jr0b6q3a.jpg)
694+
![](https://i.loli.net/2019/06/26/5d1393217488285452.jpg)
695695

696696

697697
```java
698698
lruMap.put("3",3) ;
699699
```
700-
![](https://ws4.sinaimg.cn/large/006tNc79gy1fq3hcfq95pj30gp0bot93.jpg)
700+
![](https://i.loli.net/2019/06/26/5d139321e34f996391.jpg)
701701

702702
```java
703703
lruMap.put("4",4) ;
704704
```
705-
![](https://ws1.sinaimg.cn/large/006tNc79gy1fq3hfl5r8ij30kn0b374s.jpg)
705+
![](https://i.loli.net/2019/06/26/5d139322609e214433.jpg)
706706

707707

708708
### 获取数据时
@@ -713,7 +713,7 @@ lruMap.put("4",4) ;
713713
Integer integer = lruMap.get("2");
714714
```
715715

716-
![](https://ws2.sinaimg.cn/large/006tNc79gy1fq3hjbou5pj30k70aj3yy.jpg)
716+
![](https://i.loli.net/2019/06/26/5d139322ea89567527.jpg)
717717

718718
通过以上几张图应该是很好理解数据是如何存放的了。
719719

‎docs/algorithm/guava-bloom-filter.md‎

Lines changed: 14 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11

2-
![](https://ws2.sinaimg.cn/large/006tNbRwly1fxjmn1eyr6j31hc0qr114.jpg)
2+
![](https://i.loli.net/2019/06/26/5d1393217483718447.jpg)
33

44
# 前言
55

@@ -50,11 +50,11 @@
5050

5151
还是在这个基础上，写入 1000W 数据试试：
5252

53-
![](https://ws1.sinaimg.cn/large/006tNbRwly1fxjn76zaoaj30fr07ejsh.jpg)
53+
![](https://i.loli.net/2019/06/26/5d139321d4ee464729.jpg)
5454

5555
执行后马上就内存溢出。
5656

57-
![](https://ws3.sinaimg.cn/large/006tNbRwly1fxjn7zovu8j30my07rq4o.jpg)
57+
![](https://i.loli.net/2019/06/26/5d139322c054a77994.jpg)
5858

5959
可见在内存有限的情况下我们不能使用这种方式。
6060

@@ -83,7 +83,7 @@
8383
8484
听起来比较绕，但是通过一个图就比较容易理解了。
8585

86-
![](https://ws3.sinaimg.cn/large/006tNbRwly1fxjo2ku62jj30ew0bzweu.jpg)
86+
![](https://i.loli.net/2019/06/26/5d1393234976c40998.jpg)
8787

8888
如图所示：
8989

@@ -269,13 +269,13 @@ public class BloomFilters {
269269

270270
执行结果如下：
271271

272-
![](https://ws3.sinaimg.cn/large/006tNbRwly1fxjow3df29j30le06d405.jpg)
272+
![](https://i.loli.net/2019/06/26/5d139324062c317953.jpg)
273273

274274
只花了 3 秒钟就写入了 1000W 的数据同时做出来准确的判断。
275275

276276
---
277277

278-
![](https://ws3.sinaimg.cn/large/006tNbRwly1fxjoxad1kmj30p8072dhe.jpg)
278+
![](https://i.loli.net/2019/06/26/5d139324c314174414.jpg)
279279

280280
当让我把数组长度缩小到了 100W 时就出现了一个误报，`400230340` 这个数明明没在集合里，却返回了存在。
281281

@@ -286,7 +286,7 @@ public class BloomFilters {
286286

287287
# Guava 实现
288288

289-
![](https://ws2.sinaimg.cn/large/006tNbRwly1fxjp1vluy8j30lj04iab8.jpg)
289+
![](https://i.loli.net/2019/06/26/5d13932a2cbfa10136.jpg)
290290

291291
刚才的方式虽然实现了功能，也满足了大量数据。但其实观察 `GC` 日志非常频繁，同时老年代也使用了 90%，接近崩溃的边缘。
292292

@@ -325,7 +325,7 @@ public class BloomFilters {
325325

326326
也是同样写入了 1000W 的数据，执行没有问题。
327327

328-
![](https://ws2.sinaimg.cn/large/006tNbRwly1fxjp57ga3oj30ma052gmt.jpg)
328+
![](https://i.loli.net/2019/06/26/5d13932aa240376389.jpg)
329329

330330
观察 GC 日志会发现没有一次 `fullGC`，同时老年代的使用率很低。和刚才的一对比这里明显的要好上很多，也可以写入更多的数据。
331331

@@ -336,7 +336,7 @@ public class BloomFilters {
336336
构造方法中有两个比较重要的参数，一个是预计存放多少数据，一个是可以接受的误报率。
337337
我这里的测试 demo 分别是 1000W 以及 0.01。
338338

339-
![](https://ws3.sinaimg.cn/large/006tNbRwly1fxjp9reomaj30yq0cqjv9.jpg)
339+
![](https://i.loli.net/2019/06/26/5d13932b7b19733775.jpg)
340340

341341
`Guava` 会通过你预计的数量以及误报率帮你计算出你应当会使用的数组大小 `numBits` 以及需要计算几次 Hash 函数 `numHashFunctions` 。
342342

@@ -346,7 +346,7 @@ public class BloomFilters {
346346

347347
真正存放数据的 `put` 函数如下：
348348

349-
![](https://ws1.sinaimg.cn/large/006tNbRwly1fxjpg55hszj30so082abx.jpg)
349+
![](https://i.loli.net/2019/06/26/5d13932bf409b70520.jpg)
350350

351351
- 根据 `murmur3_128` 方法的到一个 128 位长度的 `byte[]`。
352352
- 分别取高低 8 位的到两个 `hash` 值。
@@ -361,23 +361,23 @@ bitsChanged |= bits.set((combinedHash & Long.MAX_VALUE) % bitSize);
361361

362362
重点是 `bits.set()` 方法。
363363

364-
![](https://ws2.sinaimg.cn/large/006tNbRwly1fxjpl6uih0j30m30dxmz9.jpg)
364+
![](https://i.loli.net/2019/06/26/5d13932c8cb9133569.jpg)
365365

366366
其实 set 方法是 `BitArray` 中的一个函数，`BitArray` 就是真正存放数据的底层数据结构。
367367

368368
利用了一个 `long[] data` 来存放数据。
369369

370370
所以 `set()` 时候也是对这个 `data` 做处理。
371371

372-
![](https://ws3.sinaimg.cn/large/006tNbRwly1fxjpnobodvj30iz06vwf7.jpg)
372+
![](https://i.loli.net/2019/06/26/5d13932d2faa229373.jpg)
373373

374374
- 在 `set` 之前先通过 `get()` 判断这个数据是否存在于集合中，如果已经存在则直接返回告知客户端写入失败。
375375
- 接下来就是通过位运算进行`位或赋值`。
376376
- `get()` 方法的计算逻辑和 set 类似，只要判断为 0 就直接返回存在该值。
377377

378378
### mightContain 是否存在函数
379379

380-
![](https://ws2.sinaimg.cn/large/006tNbRwly1fxjprkzulxj30o408wabk.jpg)
380+
![](https://i.loli.net/2019/06/26/5d13932db4fcf97015.jpg)
381381

382382
前面几步的逻辑都是类似的，只是调用了刚才的 `get()` 方法判断元素是否存在而已。
383383

@@ -398,4 +398,4 @@ bitsChanged |= bits.set((combinedHash & Long.MAX_VALUE) % bitSize);
398398

399399

400400

401-
**你的点赞与分享是对我最大的支持**
401+
**你的点赞与分享是对我最大的支持**

‎docs/contactme.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -29,5 +29,5 @@
2929

3030
**欢迎我的关注公众号一起交流：**
3131

32-
![](https://ws3.sinaimg.cn/large/006tKfTcgy1fsuvb4ebtmj30760760t7.jpg)
32+
![](https://crossoverjie.top/uploads/weixinfooter1.jpg)
3333

0 commit comments

Comments
 (0)