前不久做了一個(gè)優(yōu)惠劵的分享功能，其中一個(gè)功能就是生成一個(gè)優(yōu)惠劵分享短鏈接。生成的短鏈接要求每個(gè)鏈接都是唯一的，并且長度盡可能短。在網(wǎng)上查了一下相關(guān)的思路，發(fā)現(xiàn)了一個(gè)不錯(cuò)的算法。這個(gè)算法的思路就是用[a-za-z0-9]建立一個(gè)長度為62的矩陣，然后把矩陣打亂，再生成一個(gè)全局唯一的數(shù)字，再把這個(gè)數(shù)字用矩陣內(nèi)的元素表示轉(zhuǎn)換成62進(jìn)制,生成的鏈接長度最大才11位。所以短鏈接的生成關(guān)鍵點(diǎn)就變成了如何生成一個(gè)全局唯一的數(shù)字和實(shí)現(xiàn)進(jìn)制的轉(zhuǎn)換。
1、生成全局唯一的數(shù)字
這本質(zhì)是一個(gè)分布式id的問題。如果簡單處理的話可以借用redis的incr操作這樣每次取到的id都是單調(diào)遞增且唯一的。另外一種方式是借用mysql,這里不是借用mysql的主鍵的auto_incr特性。而是每一臺(tái)應(yīng)用來請求時(shí)分配一個(gè)范圍比如 s1 [100-200], s2 來請求的時(shí)候就分配 [201-301]，本質(zhì)是利用樂觀鎖進(jìn)行一個(gè)cas操作。
如果不想借助外部去生成id的話，可以用uuid算法。uuid長度12個(gè)字節(jié)組成由，以下幾個(gè)部分組成。
- 4個(gè)字節(jié)表示的unix timestamp,
- 3個(gè)字節(jié)表示的機(jī)器的id
- 2個(gè)字節(jié)表示的進(jìn)程id
- 3個(gè)字節(jié)表示的計(jì)數(shù)器
uuid是一類算法的統(tǒng)稱，具體有不同的實(shí)現(xiàn)。優(yōu)點(diǎn)是每臺(tái)機(jī)器可以獨(dú)立產(chǎn)生id，理論上保證不會(huì)重復(fù)，所以天然是分布式的，缺點(diǎn)是生成的id太長，不僅占用內(nèi)存，而且索引查詢效率低。
還有一個(gè)叫twitter snowflake算法，本質(zhì)上看起來與uuid有些類似。
總的來說redis,mysql解決方案就比較簡單直接可以滿足大部分的場景，如果要保證高性能和高可用的話uuid和twitter snowflake算法就更合適，實(shí)現(xiàn)起來相對復(fù)雜一些。
2、進(jìn)制轉(zhuǎn)換
這個(gè)操作就相對簡單了。直接上代碼：
|
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
/** * 短鏈接生成 */public class tinyurl { public static final char[] array = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p', 'a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'z', 'x', 'c', 'v', 'b', 'n', 'm', 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p', 'a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'z', 'x', 'c', 'v', 'b', 'n', 'm'}; public static map<character, integer> charvaluemap = new hashmap<character, integer>(); //初始化map static { for (int i = 0; i < array.length; i++) charvaluemap.put(array[i], i); } public static void main(string[] args) { for (int i = 0; i < 100; i++) { long number = long.max_value - i; string decimalstr = numberconverttodecimal(number, 62); system.out.println(number + " 轉(zhuǎn)換成 " + decimalstr); long tonumber = decimalconverttonumber(decimalstr, 62); system.out.println(decimalstr + " 轉(zhuǎn)換成 " + tonumber); } } /** * 把數(shù)字轉(zhuǎn)換成相對應(yīng)的進(jìn)制,目前支持(2-62)進(jìn)制 * * @param number * @param decimal * @return */ public static string numberconverttodecimal(long number, int decimal) { stringbuilder builder = new stringbuilder(); while (number != 0) { builder.append(array[(int) (number - (number / decimal) * decimal)]); number /= decimal; } return builder.reverse().tostring(); } /** * 把進(jìn)制字符串轉(zhuǎn)換成相應(yīng)的數(shù)字 * @param decimalstr * @param decimal * @return */ public static long decimalconverttonumber(string decimalstr, int decimal) { long sum = 0; long multiple = 1; char[] chars = decimalstr.tochararray(); for (int i = chars.length - 1; i >= 0; i--) { char c = chars[i]; sum += charvaluemap.get(c) * multiple; multiple *= decimal; } return sum; } } |
這里面有個(gè)小優(yōu)化就是用charvaluemap記錄每個(gè)字符對應(yīng)的數(shù)值，這是一個(gè)用空間換時(shí)間的策略優(yōu)化，把o(n)的時(shí)間降為o(1)。
另外通常我們要記錄短網(wǎng)址與長網(wǎng)址的對應(yīng)的關(guān)系，相對于直接存儲(chǔ)短網(wǎng)址的而言，存儲(chǔ)對應(yīng)的數(shù)值id會(huì)更省空間。
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
