[일반] 이틀전 코포 질문

[익명(182.231)]

세터들 멘탈 나가서 그런지 아직까지 에디토리얼이 없음

F번에서 서로 다른 수들의 XOR이 0이 되는 확률이 작아지도록 숫자를 해싱할 때 

그냥 아무 숫자나 랜덤으로 가져다가 매칭하면 되는거임? 아니면 따로 매칭하는 방법이 있음?

[익명(59.13)]

다운보트 500배

[대학원오지마세요(publfl)]

아무렇게나 해싱해도 되는데 해쉬 테이블만 크게 하면 됨. 그러니까 간단하게 말해서 각 숫자를 해싱할때 int범위가 아니고 long long int범위 내의 숫자로 해싱해주면 된다는 뜻임. 어짜피 충돌만 안일어나면 OK니까 최대한 충돌 안나게 해쉬테이블 크게잡아야지

[익명(182.231)]

ㄳㄳ 근데 이거 충돌 확률에 관한 글 같은거도 있을까요? 임의로 k개의 해시값을 뽑아서 xor했을 때 0이 되는 경우가 존재하지 않아야 한다는거잖음 모든 k에 대해 이런 확률이 얼마나됨?

[대학원오지마세요(publfl)]

증명은 없는데 대충 생각할수 있지 않나? n개의 숫자를 해싱했다고 하면, XOR은 F_2 위의 vector의 addition으로 표현되니 vector space의 dimension을 생각할 수 있고, 그러면 nulliy를 생각해보면 해시충돌이 일어나는 숫자 조합의 개수는 총 2^(n-dim)만큼이 되겠지. 그런데 우리가 볼껀 [L,R]형태의 구간들만 볼꺼니 전체 확인하는 구간 갯수는 n(n+1)/2개고, 따라서 해시충돌이 일어날 확률은 약 n(n+1)/2를 2^(n-dim)만큼 나눈 값이 되겠지. 여기서 dim은 64가 될꺼고(64bit int로 해싱했으니)

[대학원오지마세요(publfl)]

뭔가 수식이 이상한데 음 대충 충돌 일어날 확률이 1/2^dim이니까 충돌 날 확률이 n(n+1)/2를 2^dim으로 나눈 값. 이게 맞겠네 ㅈㅅ