해시를 기반으로 한 균일 한 난수 생성

Question

문자열과 긴 숫자로 구성된 키를 기반으로 올바른 의사 난수가 필요합니다. 동일한 키를 사용하여 쿼리 할 때 동일한 임의의 숫자를 가져와야하며, 키가 길면 1 씩 떨어져도 약간 다른 키를 사용하여 쿼리하면 매우 다른 숫자를 가져야합니다.이 코드를 시도했습니다. 난수는 고유하지만 비슷한 수의 경우에는 상관 관계가있는 것처럼 보입니다.

import java.util.Date; 
import java.util.Random; 
import org.apache.commons.lang3.builder.HashCodeBuilder; 

public class HashKeyTest { 
    long time; 
    String str; 
    public HashKeyTest(String str, long time) { 
     this.time = time; 
     this.str = str; 
    } 

    @Override 
    public int hashCode() { 
     return new HashCodeBuilder().append(time).append(str).toHashCode(); 
    } 

    public static void main(String[] args) throws Exception { 
     for(int i=0; i<10; i++){ 
      long time = new Date().getTime(); 
      HashKeyTest hk = new HashKeyTest("SPY", time); 
      long hashCode = (long)hk.hashCode(); 
      Random rGen = new Random(hashCode); 
      System.out.format("%d:%d:%10.12f\n", time, hashCode, rGen.nextDouble()); 
      Thread.sleep(1); 
     } 
    } 
} 

해결책 I 함께. 이것은 꽤 잘 작동하지만, 이것이 장황 할 필요가 있는지 궁금합니다.

import java.io.ByteArrayOutputStream; 
import java.io.IOException; 
import java.io.ObjectOutputStream; 
import java.io.Serializable; 
import java.nio.ByteBuffer; 
import java.security.MessageDigest; 
import java.security.NoSuchAlgorithmException; 
import java.util.Random; 

public class HashKeyTest implements Serializable{ 

    long time; 
    String str; 

    public HashKeyTest(String str, long time) { 
     this.time = time; 
     this.str = str; 
    } 

    public double random() throws IOException, NoSuchAlgorithmException { 
     ByteArrayOutputStream bos = new ByteArrayOutputStream(); 
     ObjectOutputStream out = new ObjectOutputStream(bos); 
     out.writeObject(this); 
     byte[] bytes = bos.toByteArray(); 
     MessageDigest md5Digest = MessageDigest.getInstance("MD5"); 
     byte[] hash = md5Digest.digest(bytes); 
     ByteBuffer bb = ByteBuffer.wrap(hash); 
     long seed = bb.getLong(); 

     return new Random(seed).nextDouble(); 
    } 

    public static void main(String[] args) throws Exception { 
     long time = 0; 
     for (int i = 0; i < 10; i++) { 
      time += 250L; 
      HashKeyTest hk = new HashKeyTest("SPY", time); 
      System.out.format("%d:%10.12f\n", time, hk.random()); 
      Thread.sleep(1); 
     } 
    } 
} 

Answer 1

당신은 "동일한 키를 사용하여 쿼리 할 때 동일한 난수를 가져야하고 약간 다른 키를 사용하여 쿼리하면 매우 다른 수를 얻어야합니다"라고 말했습니다. 귀하의 질문을 올바르게 이해한다면 임의의 숫자가 아니라 암호 해시 코드와 같은 것을 원할 것입니다.

SHA 또는 MD5와 같은 해시 함수를 통해 가져온 데이터를 전달해야합니다. 이렇게하면 입력과 관련하여 임의적으로 보이는 무언가를 얻을 수 있지만 입력이 같을 때는 항상 동일 할 것이며 입력이 매우 적게 변하는 경우에도 크게 다를 것입니다.

편집 :

SHAHashValue v = ComputeSHA(yourObject); 
Random r = new Random(v); 
the_random_value = r.getNext(); 

여기 아이디어는 무작위로 발전기를 초기화 시드로 SHA 해시 값을 사용하는 것입니다 이 지속적으로 두 배의 값이 (의사 코드) 같은 것을 시도 얻을 수있다. 이것은 여러분이 가지고있는 것입니다 만, HashBuilder가 다른 값의 관점에서 무엇을 생산하는지 모르겠습니다. SHA 해시를 대신 사용하면 상황을 개선 할 수 있습니다.

또한 0과 1 사이의 double에 대한 "매우 다른"값이 즉시 나타나지 않을 수도 있습니다.

Answer 2

내가 이해하는 것은 :

• 개체는 두 개의 인스턴스 변수가 - 긴 time과 당신이 원하는 임의의 숫자
• 를 계산하기 위해 고려 될 필요가 문자열 str을 난수는 time 부분에 매우 민감합니다.
• 동일한 time + str 조합은 동일한 난수를 생성해야합니다.
• 두 개의 서로 다른 time + str 조합이 동일한 난수를 생성하면 정상입니다.

게시 한 코드에서 HashCodeBuilder()은 (는) time 일 때처럼 민감하지 않습니다.

다른 사람들이 제안한 것 외에도 하나의 아이디어는 time 자체를 일관된 방식으로 변경할 수 있습니다.

time (long 키의 일부)의 마지막 숫자를 가져 와서 번호 중간으로 옮길 수 있습니다.

이

@Override 
public int hashCode() { 
    return (new org.apache.commons.lang.builder.HashCodeBuilder() 
      .append(time+((time%10)*100000000)).append(str).toHashCode()); 
} 

(코드는 정확히 중간에 마지막 자리를 이동하지 않고, 질문의 맥락에서 비슷한하고있다)

을하지만이 종류의 느린 것 : 예를 들면, 당신의 hashCode()이 될 수 있습니다 . 따라서 비트 연산자로 변환 할 수 있습니다.

@Override 
public int hashCode() { 
    return (new org.apache.commons.lang.builder.HashCodeBuilder() 
      .append(time+((time & 63l) << 57)).append(str).toHashCode()); 
} 

시간 (time & 63l) 전면에있는 그 비트 방식 퍼팅의 마지막 6 개 비트를 추출하는 등의 종류 (57 종류의 랜덤는. 난 그냥 그 비트 더 중요한 위치를 이동하려는). 이것은 "중간에서 어딘가에 자리 이동"과 정확히 일치하지 않지만 개념적으로는 비슷합니다.

마지막 5 비트 (time & 31l) 만 추출하면 더 많은 차이가 발생합니다. 다른 값을 시도해 볼 수 있습니다.

1339343005559:-1084202043:0.339762681480 
1339343005585:1801482883:0.323979029483 
1339343005586:559968862:0.786162684846 
1339343005587:-681545159:0.241820545267 
1339343005588:-580881900:0.692788956755 
1339343005590:1231057354:0.624686671170 
1339343005591:-10456667:0.530394885899 
1339343005592:1700819920:0.894868466104 
1339343005593:459305899:0.149584882259 
1339343005595:-2023722143:0.289584988289 

가 예상대로 키의 long 부분에 작은 변화에 대한 더 많은 차이를 보여줍니다 질문에 게시 코드의 경우, time & 63l 버전은 다음과 같은 출력을 반환합니다.

Answer 3

난 그냥 "임의의"번호로 키의 해시 자체를 사용합니다.합리적인 해시 구현을 가정하면 언급 한 모든 속성을 갖게됩니다.

Answer 4

다소 놀라운 결과입니다. 나는 씨앗의 작은 차이가 난수의 흐름에 큰 차이를 야기한다고 생각했을 것이다. 반성에서, 내가 왜 그렇게 생각하는지 모르겠다.

그래도 쉽게 고칠 수 있습니다.

아마도 가장 간단한 것은 난수 생성기를 사용하기 전에 난수 생성기를 조금 워밍업시키는 것일 수 있습니다. 다른 씨앗에서 생성 된 비트 스트림은 비슷하지만 매우 빠르게 분기되므로 비트 스트림의 초기 부분을 버리기 만하면됩니다. 더 발산을 위해,

rGen.nextLong(); 

을 또는 : 즉시 당신이 Random를 만들 줄 뒤에이 추가

for (int j = 0; j < 10; ++j) rGen.nextLong(); 

빠른 테스트는이 숫자의 훨씬 넓은 다양성을 얻을 수 있음을 보여준다.

또 다른 옵션은 난수 생성기로 java.security.SecureRandom을 사용하는 것입니다. 이것은 유사한 입력으로부터 다른 출력을 생성하는 더 나은 작업을 수행합니다. 그것을 바이트 배열로 채 웁니다. 당신은 (str + time).getBytes()과 같은 것을 말하면서 하나를 만들 수 있습니다.

추가 옵션은 시드를 가져 와서 SHA-256과 같은 암호화 해시를 사용하여 해시 한 다음 시드의 일부를 시드로 사용하는 것입니다. 해싱은 매우 비슷한 입력을 받아 매우 다른 출력을 생성하므로 적절하게 다른 임의의 비트 스트림을 제공합니다.