2
이제 많은 분들이 HashDoS에 대해 들어 보셨을 것입니다. 이것을 발견 한 연구원은 their video에서 Hastable의 최악의 경우의 복잡도가 O(n^2)이라고 주장합니다. 어떻게 이럴 수있어?HashDoS : Hashtable의 최악의 경우의 복잡성은 어떻게 O (n^2)가 될 수 있습니까?
A
답변
8
질문에 잘못된 단어가 사용되었습니다. 연구원은 "Hashtables의 최악의 경우의 복잡성은 O (n^2)"라고 주장하지 않습니다.
What they claim은 "n 개의 요소를 테이블 [...]에 삽입하는 복잡성은 O (n^2)로 이동합니다." 따라서 단일 연산의 복잡성은 O (n)입니다. 어떤 의미가 있습니다 : 모든 키가 같은 해시를 가졌다면, 모두 배열이나 링크 된 목록 인 동일한 버킷에 들어가므로 선형 적으로 검색해야합니다.
+0
따라서이 주장은 단순히 좋은 해시 함수를 사용하는 중요성을 강조하는 역할을합니다. 좋은 해시 함수는 약한 해시 함수보다 상각 된 O (1) 시간에 도달 할 수있는 좋은 기회입니다. 전자의 경우, 해시 테이블이 O (n)의 최악의 경우에 도달 할 수있는 입력은 거의 없습니다. –
+0
@PeterO. 사실 그게 여기서 도움이되지 않을거야. 공격자는 해시 함수/라이브러리에 액세스 할 때 충돌을 생성하기 위해 보낼 데이터를 미리 알고 이러한 충돌을 생성하는 데이터 (이 경우 POST 매개 변수의 키)를 보냅니다. 무작위 해시 구현은 공격자가이 충돌 키 목록을 미리 계산할 수 없도록하고 허용 된 키 수를 제한하여 극단적 인 'n^2'를 완화합니다. –
+0
@MikeNakis :이 경우 해시 함수가 해결할 수없는 문제입니다. 해시 충돌은 유한 길이의 해시 코드에서 불가피합니다. –
가능한 복제본 [해시 테이블의 시간 복잡성] (http://stackoverflow.com/questions/3949217/time-complexity-of-hash-table) –
나는 이것이 중복이라고 생각하지 않습니다. 질문은 O (n^2)에 관한 질문이며 이전 질문에서 다루지 않았습니다. –
그것은 중복이 아니며 단순히 물어 보는 자료를 읽거나 이해하지 못하는 경우입니다. Mike는 아래에서 올바른 것입니다 - 하나의 요소를 삽입하기위한 O (n)과 n 개의 요소 집합을 삽입하기위한 O (n^2) * (충돌을 생성하는 경우)입니다. 이것은 정확히 슬라이드에 명시되어있는 것입니다. –