Go Map의 순회는 왜 무작위 인가?

출처 를 읽고

1

해싱은 객체(예: 문자열)를 정수로 매핑하는 프로그래밍 기법입니다. 컴퓨터 과학에서 가장 자주 사용되는 데이터 구조 중 하나인 해시 테이블의 필수 구성 요소입니다.

일반적으로 해시 테이블은 키와 관련된 값을 조회하거나 저장하는 데 일정한 시간이 필요하다는 속성을 가지고 있습니다. 사용자 식별자를 사용하여 이름과 전화번호를 검색하는 경우 성능 저하 없이 수백만, 수천만 명의 사용자까지 확장할 수 있습니다.
그러나 해시 테이블의 최악의 경우, 복잡성은 선형적이므로 키를 조회할 때마다 대부분의 값을 거쳐야 할 수 있습니다. 다행히도 최악의 경우는 일반적으로 가능성이 낮으며, 너무 많은 객체가 동일한 값으로 해시하는 경우에만 발생합니다. 실제로 해시 함수는 해시 값을 균일하게(의사 무작위로) 분산시키기 위해 선택됩니다.

Java나 C++와 같은 대부분의 프로그래밍 언어는 결정론적 해시 함수를 사용합니다.
즉, 문자열이 주어지면 전 세계의 모든 Java 소프트웨어에서 항상 동일한 정수로 해시됩니다. 그리고 전반적으로 결정론적 해싱은 꽤 잘 작동합니다.
안타깝게도 결정론적 해싱은 안전하지 않습니다. 웹 애플리케이션을 개발 중인데 해커가 어떤 해시 함수를 사용하는지 알고 있다면 서비스 거부 공격을 일으켜 애플리케이션을 다운시킬 수 있습니다. 해시 테이블이 최악의 성능으로 돌아가도록 하는 것만으로도 충분합니다.

2

이는 매우 심각한 문제입니다. 프로그래밍 언어의 기본 해시 함수(예: Java의 String.hashCode)에 의존하는 경우 애플리케이션이 위험에 처할 수 있다는 의미입니다. 이 문제에 대해 알렉산더 클링크와 줄리안 월데는 잘 작성된 보안 권고문을 발표했습니다.

해결 방법은 비교적 간단합니다. 프로그래밍 언어가 무작위 해싱을 채택해야 합니다. 무작위 해싱에서는 소프트웨어가 초기화될 때마다 새로운 해시 함수가 무작위로 선택됩니다. 그렇다고 해서 공격이 불가능한 것은 아니지만 공격이 훨씬 더 어려워집니다.

이 문제는 새로운 것이 아닙니다. 2003년에 크로스비와 왈라흐가 이 문제를 제기했고 많은 책임 있는 공급업체가 제품을 수정했습니다. 아쉽게도 무작위 해싱을 채택한 유일한 프로그래밍 언어는 Ruby와 Perl뿐이었습니다. 다른 언어들은 더 꺼려합니다.

그렇다면 Java의 해시 함수를 해킹하는 것이 얼마나 쉬울까요? Java는 반복 해시 함수를 사용합니다. 반복 해시 함수는 반복할 때마다 이전 해시 값과 다음 문자로부터 새로운 해시 값을 계산합니다. Java의 문자열은 다음과 같은 함수를 사용하여 해시됩니다.
F(y,c) = 31 y + c.
여기서 y는 이전 해시 값이고 c는 현재 문자 값입니다. 따라서 문자 65, 66(아스키에서는 "AB"에 해당)으로 구성된 문자열의 해시값은 65 + 66의 31배인 2081입니다.

3

Java는 왜 31이라는 숫자를 사용하나요? 선택은 다소 임의적이지만(31은 이상적이지 않을 수도 있습니다), 홀수이기 때문에 압축 함수 F가 순열화되어 해시값을 보다 균일하게 분배하는 데 도움이 됩니다.

Java에서 32비트 이상 충돌하는 합리적인 문자열을 구성하는 것은 상당히 어렵습니다. 그러나 적당한 해시 테이블은 해시 값의 처음 몇 비트만 사용합니다. 처음 16비트만 고려해 보겠습니다. Java에서 문자열 "Ace", "BDe", "AdF" 및 "BEF"가 모두 동일한 해시 값을 갖는다는 것을 확인하는 것은 어렵지 않습니다.

물론 4개의 문자열이 충돌한다고 해서 해시 테이블이 깨지지는 않습니다. 하지만 해시 함수는 반복되기 때문에 충돌 횟수를 늘릴 수 있습니다. 실제로 이 네 개의 충돌하는 문자열 중 길이가 같은 두 개의 시퀀스도 충돌합니다. 즉, 길이가 6인 16개의 문자열을 모두 충돌하는 것으로 구성할 수 있습니다("AceAce","AceBDe","AceAdF","AceBEF","BDeAce","BDeBDe","BDeAdF","BDeBEF", "AdFAce","AdFBDe","AdFAdF", "AdFBEF","BEFAce","BEFBDe","BEFAdF" 및 "BEFBEF"). 길이 9의 문자열은 64개까지 계속 사용할 수 있습니다.

4

이것이 해시 테이블의 성능에 얼마나 나쁜 영향을 미치나요? 충돌하는 모든 문자열을 Java 해시 테이블 컨테이너에 삽입해 보았습니다. 비교를 위해 무작위로 선택한 문자열을 해시 테이블이나 트리맵(트리 구조)에 삽입해 보았습니다. 그 결과, 작은 비용(0.006초)이 소요되어야 할 것이 엄청난 비용(30초)으로 변했습니다. 초당 수천 개의 쿼리를 처리할 수 있는 서버가 초당 몇 개의 쿼리를 처리하려고 하면 금방 수렁에 빠질 수 있습니다.

표

Number of Strings	Hash Table: Average Time (s)	Hash Table: Worst Time (s)	Tree: Average Time (s)
16384	0.002	1.1	0.005
65536	0.006	30	0.03

5

이 테스트에서는 Java 6을 실행하는 1.8GHz 인텔 코어 i7이 탑재된 MacBook Air를 사용하고 있습니다. 내 코드를 사용할 수 있습니다.

프로그래밍 언어가 랜덤 해싱을 채택하지 않는 이유는 무엇인가요? 잠재적인 문제는 언어 설계자가 결정론을 좋아한다는 것입니다. 그들은 재현 가능한 버그를 훨씬 선호합니다. 그럼에도 불구하고 전문 프로그래머라면 누구나 이 문제를 알고 있어야 합니다.