Skip to content

Commit ed255ff

Browse files
crossoverJiecrossoverJie
committed
抢红包算法
1 parent a8eeaf5 commit ed255ff

2 files changed

Lines changed: 138 additions & 2 deletions

File tree

‎MD/ConcurrentHashMap.md‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,7 @@
1212
`ConcurrentHashMap` 采用了分段锁技术，其中 `Segment` 继承于 `ReentrantLock`。不会像 `HashTable` 那样不管是 `put` 还是 `get` 操作都需要做同步处理，理论上 ConcurrentHashMap 支持 `CurrencyLevel` (Segment 数组数量)的线程并发。每当一个线程占用锁访问一个 `Segment` 时，不会影响到其他的 `Segment`。
1313

1414
## get 方法
15-
ConcurrentHashMap 的 get 方法是非常高效的，因为整个过程都不需要加锁。
15+
`ConcurrentHashMap` 的 `get` 方法是非常高效的，因为整个过程都不需要加锁。
1616

1717
只需要将 `Key` 通过 `Hash` 之后定位到具体的 `Segment` ，再通过一次 `Hash` 定位到具体的元素上。由于 `HashEntry` 中的 `value` 属性是用 `volatile` 关键词修饰的，保证了内存可见性，所以每次获取时都是最新值([volatile 相关知识点](https://github.com/crossoverJie/Java-Interview/blob/master/MD/Threadcore.md#%E5%8F%AF%E8%A7%81%E6%80%A7))。
1818

@@ -35,7 +35,7 @@ ConcurrentHashMap 的 get 方法是非常高效的，因为整个过程都不需
3535
}
3636
```
3737

38-
虽然 HashEntry 中的 value 是用 volatile 关键词修饰的，但是并不能保证并发的原子性。所以 put 操作时仍然需要加锁处理。
38+
虽然 HashEntry 中的 value 是用 `volatile` 关键词修饰的，但是并不能保证并发的原子性，所以 put 操作时仍然需要加锁处理。
3939

4040
首先也是通过 Key 的 Hash 定位到具体的 Segment，在 put 之前会进行一次扩容校验。这里比 HashMap 要好的一点是：HashMap 是插入元素之后再看是否需要扩容，有可能扩容之后后续就没有插入就浪费了本次扩容(扩容非常消耗性能)。
4141

‎src/main/java/com/crossoverjie/red/RedPacket.java‎

Lines changed: 136 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,136 @@
1+
package com.crossoverjie.red;
2+
3+
import java.util.LinkedList;
4+
import java.util.List;
5+
6+
/**
7+
* Function: 模拟微信红包生成，以分为单位
8+
*
9+
* @author crossoverJie
10+
* Date: 03/01/2018 16:52
11+
* @since JDK 1.8
12+
*/
13+
public class RedPacket {
14+
15+
/**
16+
* 生成红包最小值 1分
17+
*/
18+
private static final int MINMONEY = 1 ;
19+
20+
/**
21+
* 生成红包最大值 200人民币
22+
*/
23+
private static final int MAXMONEY = 200 * 100 ;
24+
25+
/**
26+
* 小于最小值状态
27+
*/
28+
private static final int LESS = -1 ;
29+
/**
30+
* 大于最大值
31+
*/
32+
private static final int MORE = -2 ;
33+
34+
/**
35+
* 正常值
36+
*/
37+
private static final int OK = 1 ;
38+
39+
/**
40+
* 最大的红包是平均值的 TIMES 倍，防止某一次分配红包较大
41+
*/
42+
private static final double TIMES = 2.1F ;
43+
44+
private int recursiveCount = 0 ;
45+
46+
private List<Integer> splitRedPacket(int money,int count){
47+
List<Integer> moneys = new LinkedList<>() ;
48+
49+
//计算出最大红包
50+
int max = (int) ((money / count) * TIMES) ;
51+
max = max > MAXMONEY ? MAXMONEY : max ;
52+
53+
for (int i = 0 ; i< count ; i++){
54+
//随机获取红包
55+
int redPacket = randomRedPacket(money,MINMONEY,max,count - i) ;
56+
moneys.add(redPacket);
57+
//总金额每次减少
58+
money -= redPacket ;
59+
}
60+
61+
return moneys ;
62+
}
63+
64+
private int randomRedPacket(int totalMoney, int minMoney, int maxMoney, int count) {
65+
//只有一个红包直接返回
66+
if (count == 1){
67+
return totalMoney ;
68+
}
69+
70+
if (minMoney == maxMoney){
71+
return minMoney ;
72+
}
73+
74+
//如果最大金额大于了剩余金额 则用剩余金额 因为这个 money 每分配一次都会减小
75+
maxMoney = maxMoney > totalMoney ? totalMoney : maxMoney ;
76+
77+
//在 minMoney到maxMoney 生成一个随机红包
78+
int redPacket = (int) (Math.random() * (maxMoney - minMoney) + minMoney) ;
79+
80+
int lastMoney = totalMoney - redPacket ;
81+
82+
int status = checkMoney(lastMoney,count - 1) ;
83+
84+
//正常金额
85+
if (OK == status){
86+
return redPacket ;
87+
}
88+
89+
if (LESS == status){
90+
recursiveCount ++ ;
91+
System.out.println("recursiveCount==" + recursiveCount);
92+
return randomRedPacket(totalMoney,minMoney,redPacket,count) ;
93+
}
94+
95+
if (MORE == status){
96+
recursiveCount ++ ;
97+
System.out.println("recursiveCount===" + recursiveCount);
98+
return randomRedPacket(totalMoney,redPacket,maxMoney,count) ;
99+
}
100+
101+
return redPacket ;
102+
}
103+
104+
/**
105+
* 校验剩余的金额的平均值是否在 最小值和最大值这个范围内
106+
* @param lastMoney
107+
* @param count
108+
* @return
109+
*/
110+
private int checkMoney(int lastMoney, int count) {
111+
double avg = lastMoney / count ;
112+
if (avg < MINMONEY){
113+
return LESS ;
114+
}
115+
116+
if (avg > MAXMONEY){
117+
return MORE ;
118+
}
119+
120+
return OK ;
121+
}
122+
123+
124+
public static void main(String[] args) {
125+
RedPacket redPacket = new RedPacket() ;
126+
List<Integer> redPackets = redPacket.splitRedPacket(20000, 100);
127+
System.out.println(redPackets) ;
128+
129+
int sum = 0 ;
130+
for (Integer red : redPackets) {
131+
sum += red ;
132+
}
133+
System.out.println(sum);
134+
}
135+
136+
}

0 commit comments

Comments
 (0)