3ldk

樓主要random既目的係咩先？
如果只係唔重複，sequence已經ok

方法一：搵個32 bit既block cipher，gen一條 ...
FlyingForever 發表於 2016-7-7 22:36

目的係唔想比人撞到
但又唔介意重複, 不過就希望重複既出現時間可以盡量延長

你個方法一睇落唔錯, 但下面有個更好既方法, 因為唔洗自己implement

3ldk

redeem code o個d唔需理會security既野一向用Hashids, 只要直接hash個auto increment 既id就得 ...
YuiNarusawa 發表於 2016-7-8 01:00

你依個簡直就係accepted answer
而且佢做到既比我所要求既更多, 本來我唔需要100% unique, 但佢都可以做到
更正既係, 仲可以decode, 咁即係我可以用sequence id save, 用random key 公開
基本上依個係最接近完美既方案

之所以話"最接近", 因為依個方法都有幾個缺點

1. 首先佢無辦法ensure個長度, 佢個網站聲稱無collision, 但我唔信, 因為依個世上有Pigeonhole principle, 所以我測試過, set一個好細既output長度, 再比一個好大既sequence, 最後發現, 原來所謂既無collision, 只不過係當唔夠位, 就不斷加大output長度

2. 同埋佢只係保證salt一樣既情況下係unique, 如果salt改左, 有機會有collision

3. 需要有一個auto increment id, 有時如果個application係唔需要db, 你都需要夾硬整個dummy table, insert dummy record, 全部只係為左想要一個auto increment id


當然, 優點完全可以蓋過以上缺點, 所以依D缺點其實都唔太緊要

梁炳

HashIds，完
http://hashids.org/

只要"random key"唔係指定長度，當然可以在algorithm確保無重覆
Salt係唔suppose會改的，要改就會全部都唔同哂，一樣係唔會重覆架
仲可以用來encode multiple values

FlyingForever

你依個簡直就係accepted answer
而且佢做到既比我所要求既更多, 本來我唔需要100% unique, 但佢都可以做 ...
3ldk 發表於 2016-7-8 20:50

而家先知有樣野叫hashids…
我個方法基本上一樣，不過佢提供左一個任意bit既block cipher，然後按input大細揀用幾多bit

你所講既「缺點」基本上冇可能避開：
1. 你都知道Pigeonhole principle，冇計
2. 無論你用咩algorithm，只要係沿用同一個模式，成個function就只depends on sequence number同salt
其中salt決定permutation of output space，sequence number決定用呢個permutation入面既第幾個output
假設你個space大細係2^32，然後你已經output左2^31個value
呢個時候你轉salt，然後繼續increment sequence number去做output
要係呢種情況下唔撞，只可能係新salt同舊salt既頭2^31個output一樣（次序可以唔同），尾2^31個output都一樣
由於salt可以係任意，意味住對所有salt，頭2^31個output都一樣，尾2^31個output都一樣
將2^31換成arbitrary number，你會發現要符合「轉salt都唔撞」既唯一方法，就係所有salt都用同一set permutation，即係冇salt
3. 成個function只有sequence number係會變既input，冇埋既話只能用random

rabbit82047

為左重複發明輪子, 所以將自己既諗法實作左

1. // Example usage:
   
2. // HashSequenceGenerator generator = new HashSequenceGenerator("0123456789", 5);
   
3. // System.out.println(generator.nextKey());
   
4. 
   
5. import java.util.Random;
   
6. 
   
7. public class HashSequenceGenerator {
   
8.     private long seed, total;
   
9. 
   
10.     private char[] availableChars;
    
11. 
    
12.     // Character mapper for each character place, this will make the result key looks like random.
    
13.     private char[][] chars;
    
14. 
    
15.     private int length, seq;
    
16. 
    
17.     public HashSequenceGenerator(String availableChars, int length) {
    
18.         this(availableChars.toCharArray(), length, new Random().nextLong());
    
19.     }
    
20. 
    
21.     public HashSequenceGenerator(String availableChars, int length, long seed) {
    
22.         this(availableChars.toCharArray(), length, seed);
    
23.     }
    
24. 
    
25.     public HashSequenceGenerator(char[] availableChars, int length) {
    
26.         this(availableChars, length, new Random().nextLong());
    
27.     }
    
28. 
    
29.     public HashSequenceGenerator(char[] availableChars, int length, long seed) {
    
30.         this(availableChars, length, 0, seed);
    
31.     }
    
32. 
    
33.     public HashSequenceGenerator(char[] availableChars, int length, int seq, long seed) {
    
34.         this.seed = seed;
    
35.         this.availableChars = availableChars;
    
36. 
    
37.         initializeChars(availableChars, length, seed);
    
38. 
    
39.         this.total = (long)(Math.pow(availableChars.length, length));
    
40.         this.length = length;
    
41.         this.seq = seq;
    
42.     }
    
43. 
    
44.     // Result will be determined by seed
    
45.     private void initializeChars(char[] availableChars, int length, long seed) {
    
46.         Random random = new Random(seed);
    
47. 
    
48.         this.chars = new char[length][availableChars.length];
    
49. 
    
50.         for (char[] aChar : chars) {
    
51.             System.arraycopy(availableChars, 0, aChar, 0, aChar.length);
    
52.             shuffle(aChar, random);
    
53.         }
    
54.     }
    
55. 
    
56.     private int randomInteger(int min, int max, Random randomGenerator) {
    
57.         if (min == max) {
    
58.             return min;
    
59.         }
    
60.         return (int)((randomGenerator.nextDouble() * (max - min + 1)) + min);
    
61.     }
    
62. 
    
63.     private void shuffle(char[] chars, Random random) {
    
64.         for (int i = 0; i < chars.length; i++) {
    
65.             int idx = randomInteger(0, chars.length-1, random);
    
66. 
    
67.             if (i != idx) {
    
68.                 char c = chars[i];
    
69.                 chars[i] = chars[idx];
    
70.                 chars[idx] = c;
    
71.             }
    
72.         }
    
73.     }
    
74. 
    
75.     public String nextKey() {
    
76.         return encodeKeyNum(generateKeyNum(length, incrementSeq(), availableChars.length), chars);
    
77.     }
    
78. 
    
79.     private int incrementSeq() {
    
80.         int oldSeq = seq++;
    
81. 
    
82.         // Overflow, reset sequence number
    
83.         if (seq > total) {
    
84.             seq = 0;
    
85.         }
    
86. 
    
87.         return oldSeq;
    
88.     }
    
89. 
    
90.     // Sequence number mapper to make the end result looks random
    
91.     // Original remap formula: total / partition * (seq % partition) + (int) Math.floor(seq / partition)
    
92.     // will generate many repetitive character pattern for a range of sequence numbers which is not ideal.
    
93.     public int remap(int num, int length, int base) {
    
94.         int v = num;
    
95.         int[] vals = new int[length];
    
96. 
    
97.         for (int i = 0; i < vals.length; i++) {
    
98.             vals[i] = v % base;
    
99. 
    
100.             v = (v - vals[i]) / base;
     
101. 
     
102.             if (i > 0) {
     
103.                 vals[i] = (vals[0] + vals[i] + i) % base;
     
104.             }
     
105.         }
     
106. 
     
107.         // Key can be generated directly from here.
     
108.         int result = 0;
     
109. 
     
110.         for (int i = 0; i < vals.length; i++) {
     
111.             result += vals[i] * Math.pow(base, i);
     
112.         }
     
113. 
     
114.         return result;
     
115.     }
     
116. 
     
117.     private String encodeKeyNum(int keyNum, char[][] chars) {
     
118.         char[] keyChars = new char[length];
     
119. 
     
120.         for (int i = 0; i < keyChars.length; i++) {
     
121.             keyChars[keyChars.length - i - 1] =
     
122.                 chars[i][keyNum / ((int) Math.pow(chars[i].length, i)) % chars[keyChars.length-1].length];
     
123.         }
     
124. 
     
125.         return new String(keyChars);
     
126.     }
     
127. 
     
128.     private int generateKeyNum(int l, int s, int base) {
     
129.         return remap(s, l, base);
     
130.     }
     
131. }

複製代碼

又多個 utility class 用