해시 함수가 O (1)이 아닌데도 O (1) 키로 사전의 요소에 액세스하는 이유는 무엇입니까?

해시 함수가 O (1)이 아닌데도 O (1) 키로 사전의 요소에 액세스하는 이유는 무엇입니까?

---

키로 컬렉션에 액세스하는 방법을 봅니다. 그러나 해시 함수 자체는 배후에서 많은 작업을 수행하지 않습니까?

매우 효율적인 멋진 해시 함수가 있다고 가정해도 여전히 많은 작업이 필요할 수 있습니다.

설명 할 수 있습니까?

---

그 HashFunc자체는이면에서 많은 작업을합니다.

그것은 확실히 사실입니다. 그러나 이러한 작업의 수 는 키가 삽입 된 해시 테이블 의 크기가 아니라 키 의 크기에 따라 달라집니다. 해시 함수를 계산하는 작업의 수는 10 개가있는 테이블의 키에 대해 동일합니다. 만 항목이 있습니다.

이것이 해시 함수 호출이 종종 O (1)로 간주되는 이유입니다. 이것은 고정 크기 키 (정수 값 및 고정 길이 문자열)에 대해 잘 작동합니다. 또한 실제 상한이있는 가변 크기 키에 대한 적절한 근사치를 제공합니다.

그러나 일반적으로 해시 테이블의 액세스 시간은 O (k)이며 k해시 키 크기의 상한선입니다.

---

O(1)즉석을 의미하지 않습니다. 데이터의 크기에 관계없이O(1) 일정 함을 의미 합니다 . 해시 함수는 일정 시간이 걸리지 만 그 시간은 컬렉션의 크기에 따라 확장되지 않습니다.

---

이는 컬렉션의 크기에 관계없이 구성원을 검색하는 데 거의 동일한 시간이 소요된다는 것을 의미합니다.

즉, 5 명의 회원이있는 사전은 그들 중 하나에 액세스하는 데 약 0.002ms가 걸리고 25 명의 회원이있는 사전은 비슷한 것을 취해야한다고 가정하겠습니다. Big O는 실행되는 실제 명령문이나 함수 대신 컬렉션 크기에 대한 알고리즘 복잡성을 의미합니다.

---

딕셔너리 / 맵이으로 구현 된 경우 HashMap, 키 충돌이없는 경우 검색을 위해 키 요소의 해시 코드를 정확하게 계산해야하기 때문에 최상의 경우 복잡성 을 갖습니다 O(1).

해시 맵은 있을 수 있습니다 최악의 경우 런타임 복잡성 의 O(n)이 경우에는 데이터를 보유하고있는 전체 배열의 선형 스캔을 저하하기 때문에 당신이 키 충돌 또는 아주 나쁜 해시 함수의 많은 경우입니다.

또한, O(1)의미하지 않는다 즉시 , 그것은 그것이 가지고 의미 상수의 양을. 따라서 딕셔너리에 대한 올바른 구현을 선택하는 것은 컬렉션의 요소 수에 따라 달라질 수 있습니다. 함수에 대해 매우 높은 상수 비용을 갖는 것은 항목이 몇 개만있는 경우 훨씬 더 나 빠지기 때문입니다.

이것이 사전 / 맵이 시나리오마다 다르게 구현되는 이유입니다. Java의 경우 여러 가지 구현이 있으며 C ++는 레드 / 블랙 트리 등을 사용합니다. 데이터 수와 최고 / 평균 / 최악의 경우 런타임 효율성에 따라 선택했습니다.

---

이론적으로는 여전히 O (n)입니다. 왜냐하면 최악의 경우 모든 데이터가 동일한 해시를 가지게되며 함께 묶여서 모든 데이터를 선형 적으로 처리해야하기 때문입니다.

---

게시물을 참조하십시오 "O (1) 액세스 시간"은 무엇을 의미합니까?

해시 함수의 작업 수는 컬렉션의 모든 요소에 대해 동일한 (일정) 시간이 소요되는 한 관련이 없습니다. 예를 들어, 2 개의 요소 모음에서 하나의 요소에 액세스하는 데는 .001ms가 걸리지 만, 2,000,000,000 개의 요소 모음에서 하나의 요소에 액세스하는데도 .001ms가 걸립니다. 해시 함수에는 수백 개의 if 문과 여러 계산이 포함될 수 있습니다.

---

문서에서 :

키를 사용하여 값을 검색하는 것은 T : System.Collections.Generic.Dictionary`2 클래스가 해시 테이블로 구현되기 때문에 O (1)에 가깝게 매우 빠릅니다.

따라서 O (1) 일 수 있지만 더 느릴 수 있습니다. 여기에서 해시 테이블 성능과 관련된 또 다른 스레드를 찾을 수 있습니다. 해시 테이블-배열보다 빠른 이유는 무엇입니까?

---

더 크고 더 큰 사전이 더 많은 메모리를 차지하고 캐시 계층 구조를 더 아래로 내려가 결국 디스크의 스왑 공간을 느리게한다는 사실을 고려하면 이것이 진정 O (1)라고 주장하기 어렵습니다. 딕셔너리의 성능은 더 커질수록 느려질 것이고 아마도 O (log N) 시간 복잡성을 줄 것입니다. 나를 믿지 않습니까? 1, 100, 1000, 10000 등의 사전 요소 (최대 1,000 억)에 대해 직접 시도하고 요소를 찾는 데 실제로 걸리는 시간을 측정합니다.

그러나 시스템의 모든 메모리가 랜덤 액세스 메모리이고 일정한 시간에 액세스 할 수 있다는 단순화 가정을하면 사전이 O (1)라고 주장 할 수 있습니다. 이 가정은 일반적으로 디스크 스왑 공간이있는 모든 시스템에 대해 사실이 아니지만 다양한 수준의 CPU 캐시를 고려할 때 여전히 논쟁의 여지가 있습니다.

참고 URL : https://stackoverflow.com/questions/37348446/why-is-accessing-an-element-of-a-dictionary-by-key-o1-even-though-the-hash-fun