HashAlgorithm (3) 썸네일형 리스트형 해쉬 알고리즘hash algorithm-해쉬충돌Hash Crash Definition 해쉬함수를 사용할때 일어나는 문제중 하나 해쉬의입력값이 다름에도 불구하고, 출력값이 똑같이 나오는 경우를 얘기한다. 특징 해쉬충돌이 적게 일어날수록 좋은 해쉬 함수 완전히 아예 안일어나는 건 굉장히 어려움 매우 제한적으로 사용할떄만 해쉬충돌이 아예 안일어남. Example [input]->[output] 1번 해쉬 알고리즘 A->03 B->02 C->03 위와같은경우, A와 C의 출력값이 같으므로 해쉬 충돌이 일어남. 문제 해결법 대부분의 해쉬 알고리즘은 해쉬충돌이 일어날경우 다음 출력값으로 이동하며, 사용하지 않은 출력값을 찾음. 위의 예제의 경우, 03이 나왔는데 해쉬충돌이 일어나므로, 04를 출력하여 이곳에 C를 저장함. 해쉬 알고리즘hash algorithm-균일성uniformity Definition 해쉬함수를 평가할때 쓰이는 속성. 해쉬 출력값이 모두 같은 확율로 나올수록 좋은 해쉬 알고리즘이므로, 이를 균일성이 높다라고 표현함 Example [input]->[output] 1번 해쉬 알고리즘 A->03 B->02 C->03 2번 해쉬 알고리즘 A->01 B->02 C->03 예제 설명 위와 같은 해쉬값이 나온다면, 2번 알고리즘의 균일성이 1번 알고리즘보다 높다라고 표현할수있음. 결론 균일성이 높을수록, 해쉬 충돌이 일어나지 않는다는 뜻이므로, O(1) 의 time complexity가 나올 가능성이 높아짐. 추가 설명 균일성이 아주 높아서 해쉬충돌이 일어나지 않는 해쉬 알고리즘이 가능한가? 결론적으로 가능하지만, 아주 제한적으로만 가능함 균일성 측정 카이제곱 검정(chi-sq.. 해쉬 알고리즘hash algorithm 정의 임의의 크기를 가진 값을 고정크기의 값에 대응시키는 함수 특징 입력값이 같으면 출력값도 같아야함. 사용용도 암호화 해쉬 알고리즘을 이용한 데이터 스트럭쳐인 해쉬맵과 해쉬 테이블이 존재함. 길이가 긴 데이터 둘을 빨리 비교하기 위해 사용이 가능함. 단 다른 경우만 빨리 비교 가능 누출되면 곤란한 데이터의 원본을 저장하지 않기 위해 분류 암호학적 해쉬 함수cryptographic hash function : 암호화를 위해 사용 되는 해쉬함수 해쉬함수hash function : 해쉬함수의 성질을 이용하여 목적이 다르게 사용되는 해쉬함수 해쉬테이블은 해쉬알고리즘을 사용하여 데이터를 빠르게 저장하기 위해 만들어짐 해쉬함수의 성질 효율성efficiency 균일성uniformity 역상 저항성pre-image .. 이전 1 다음