Java 해시맵 검색은 정말 O(1)인가?

Java 해시맵 검색은 정말 O(1)인가?

나는 SO re Java 해시맵과 그들의 해시맵에 대한 흥미로운 주장을 본 적이 있다.O(1)조회 시간왜 그런지 누가 설명해줄래?이 해시맵들이 내가 산 해시 알고리즘과 크게 다르지 않다면, 항상 충돌을 포함하는 데이터 집합이 존재해야 한다.

이 경우 조회 내용은O(n)O(1).

누군가가 그들이 O(1)인지 그리고 만약 그렇다면, 어떻게 이것을 성취하는지 설명할 수 있을까?

해시맵의 특별한 특징은 균형 잡힌 나무와는 달리, 그 행동은 확률론적이라는 것이다.이러한 경우, 일반적으로 최악의 사건이 발생할 확률 측면에서 복잡성에 대해 말하는 것이 가장 도움이 될 것이다.해시 맵의 경우, 물론 지도가 얼마나 꽉 찬지와 관련하여 충돌하는 경우가 있다.충돌은 추정하기가 꽤 쉽다.

p_collision = n / 용량

따라서 적은 수의 원소라도 있는 해시 맵은 적어도 한 번의 충돌을 경험할 가능성이 높다.큰 O 표기법은 우리가 좀 더 설득력 있는 일을 할 수 있게 해준다.임의의 고정 상수 k에 대해 이를 준수하십시오.

O(n) = O(k * n)

우리는 해시 맵의 성능을 향상시키기 위해 이 기능을 사용할 수 있다.대신에 우리는 최대 두 번의 충돌의 가능성에 대해 생각해 볼 수 있다.

p_{collision x 2} = (n/용량)²

이것은 훨씬 더 낮다.추가 충돌 1회 처리 비용은 빅O 성능과 무관하기 때문에 알고리즘을 실제로 바꾸지 않고도 성능을 향상시킬 수 있는 방법을 찾아냈다!우리는 이것을 일반에게 전달할 수 있다.

p_{collision x k} = (n/용량)^k

그리고 이제 우리는 임의의 충돌 횟수를 무시할 수 있고 결국 우리가 생각하는 것보다 더 많은 충돌이 일어날 가능성이 사라지게 된다.알고리즘의 실제 구현을 변경하지 않고도 정확한 k를 선택함으로써 임의로 아주 작은 수준으로 확률을 얻을 수 있었다.

우리는 해시맵이 높은 확률의 O(1) 액세스 권한을 가지고 있다고 말하면서 이것에 대해 이야기한다.

최악의 경우 동작과 평균(예상) 런타임을 혼동하는 것 같다.전자는 일반적으로 해시 테이블에 대한 O(n)이지만(즉, 완벽한 해시를 사용하지 않음) 실제로는 거의 관련이 없다.

모든 신뢰할 수 있는 해시 테이블 구현은 절반 정도 괜찮은 해시와 결합되어 매우 좁은 분산 범위 내에서 예상 사례에서 매우 작은 요인(2, 사실)과 함께 O(1)의 검색 성능을 가진다.

Java에서 HashMap은 어떻게 작동하는가?

• 사용.hashCode해당 버킷 [bufficient bukets 컨테이너 모델]을 찾으십시오.
• 각 버킷은 해당 버킷에 있는 항목의 목록(또는 Java 8에서 시작하는 트리)이다.
• 다음을 사용하여 항목을 하나씩 검사한다.equals비교해서
• 항목을 더 추가하면, 특정 부하율에 도달하면 해시맵의 크기가 조정된다.

그래서 때로는 몇 가지 항목과 비교를 해야 할 때도 있겠지만, 일반적으로 O(n)보다는 O(1)에 훨씬 가깝다.
실용적인 목적을 위해서는 그것만 알면 된다.

o(1)는 각 조회가 단일 항목만 검사하는 것을 의미하지 않는다는 것을 의미하지 않으며, 이는 검사된 항목의 평균 수가 컨테이너의 항목 수 w.r.t.를 일정하게 유지함을 의미한다는 것을 의미한다는 것을 기억한다.따라서 100개의 항목이 있는 컨테이너에서 항목을 찾는 데 평균 4개의 비교를 한다면, 10000개의 항목이 있는 컨테이너에서 항목을 찾는 데도 평균 4개의 비교를 해야 하며, 그 외의 항목 수(특히 해시 테이블이 재시동하는 지점 주변, 그리고 매우 작은 숫자가 있는 경우 항상 약간의 분산이 있어야 한다.)항목 berr).

따라서 버킷당 평균 키 수가 고정된 경계 내에 있는 한 충돌로 인해 컨테이너가 o(1) 작동을 방해하지 않는다.

이게 오래된 질문인 건 알지만 사실 새로운 답이 있어.

해시지도는 사실 그렇지 않다니 네 말이 맞아.O(1), 엄밀히 말하면, 원소의 수가 임의로 커짐에 따라, 결국 일정한 시간에 검색할 수 없게 되기 때문이다(그리고 O-Notation은 임의적으로 커질 수 있는 숫자의 관점에서 정의된다).

은 그 다음이 O(n)--버킷을 선형 리스트로 구현해야 한다는 규정이 없기 때문이다.

사실, Java 8은 버킷을 다음과 같이 구현한다.TreeMaps한 번 임계값을 초과하면 실제 시간이 된다.O(log n).

O(1+n/k)어디에k버킷 수입니다.

구현이 설정된 경우k = n/alpha그렇다면 그렇다.O(1+alpha) = O(1)그 이후alpha상수다.

버킷 수(b라고 부름)가 일정하게 유지되는 경우(일반적인 경우), 조회 수는 실제로 O(n)이다.
각 nne가 된다.일반적인 방법(예: 링크된 목록) 중 하나로 충돌 분해능이 수행되는 경우 조회 값은 O(n/b) = O(n)이다.

O 표기법은 n이 점점 커지면 어떻게 되는지에 관한 것이다.특정 알고리즘에 적용하면 오도될 수 있고, 해시 테이블이 대표적이다.우리는 우리가 처리할 요소들의 수에 따라 버킷의 수를 선택한다.n이 b와 거의 같은 크기일 때, 룩업은 대략 일정한 시간이지만, O는 n → ∞로 한계의 관점에서 정의되기 때문에 O(1)라고 부를 수 없다.

해시 테이블 조회에 대한 표준 설명은 O(1)이며, 엄격한 최악의 성능이 아닌 평균 케이스 예상 시간을 가리킨다는 것을 우리는 규명했다.(Java의 해시맵과 같은) 체인과의 충돌을 해결하는 해시 테이블의 경우 이것은 기술적으로 해시 함수가 양호한 O(1+α)이며, 여기서 α는 표의 부하 계수다.저장 중인 개체 수가 테이블 크기보다 큰 상수 요인보다 크지 않은 한 여전히 일정함.

또한 엄격하게 말하면 어떤 결정론적 해시함수에 대해 O(n) 조회를 요구하는 입력을 구성할 수 있다고 설명되어 있다.하지만 평균 검색 시간과는 다른 최악의 경우 예상 시간을 고려하는 것도 흥미롭다.체인을 사용하면 O(1 + 가장 긴 체인의 길이), 예를 들어 α=1일 때 when(log n / log log n)이 된다.

만약 당신이 일정한 시간에 예상되는 최악의 경우를 찾는 이론적인 방법에 관심이 있다면, 당신은 다른 해시 테이블과 재귀적으로 충돌을 해결하는 동적 완벽한 해시에 대해 읽을 수 있다!

해싱 기능이 매우 좋은 경우에만 O(1)이다.Java 해시 테이블 구현은 불량 해시함수로부터 보호되지 않는다.

항목을 추가할 때 테이블을 증가시킬 필요가 있는지 여부는 조회 시간에 관한 문제이기 때문에 질문과 관련이 없다.

해시맵 내의 요소는 연결된 목록(노드)의 배열로 저장되며, 배열의 각 링크된 목록은 하나 이상의 키의 고유한 해시 값에 대한 버킷을 나타낸다.
해시맵에 항목을 추가하는 동안 키의 해시코드를 사용하여 배열에서 버킷의 위치를 결정한다.

location = (arraylength - 1) & keyhashcode

여기서 &는 비트 AND 연산자를 나타낸다.

예를 들면 다음과 같다.100 & "ABC".hashCode() = 64 (location of the bucket for the key "ABC")

가져오기 작업 중에는 키의 버킷 위치를 결정하는 동일한 방법을 사용한다.최상의 경우 각 키에는 고유한 해시코드가 있고 각 키에 대해 고유한 버킷이 생성된다. 이 경우 get 메소드는 버킷 위치를 결정하고 일정한 O(1) 값을 검색하는 데만 시간을 소비한다.

최악의 경우, 모든 키가 동일한 해시코드를 가지고 동일한 버킷에 저장되므로 전체 목록을 통과하여 O(n)로 이어진다.

자바 8의 경우 링크드 목록 버킷이 크기가 8 이상으로 커지면 트리맵으로 대체돼 최악의 경우 검색 효율이 O(log n)로 떨어진다.

이것은 알고리즘 자체가 실제로 변하지 않기 때문에 기본적으로 대부분의 프로그래밍 언어에서 대부분의 해시 테이블 구현에 적용된다.

표에 충돌이 없는 경우, 한 번만 조회하면 되기 때문에, 실행 시간은 O(1)이다.충돌이 있을 경우 두 번 이상 조회해야 하므로 O(n)로 성능이 저하된다.

충돌을 피하기 위해 선택하는 알고리즘에 따라 달라진다.구현 시 별도의 체인을 사용할 경우 모든 데이터 요소가 동일한 값으로 해시되는 최악의 경우 시나리오가 발생한다(예를 들어 해시 함수의 선택이 불량함).이 경우 데이터 조회는 링크된 리스트의 선형 검색(예: O(n))과 다르지 않다.그러나, 그러한 일이 일어날 확률은 무시할 수 있고 최상의 사례와 평균적인 사례들은 일정하게 유지된다.

이론적인 경우에만 해시코드가 항상 다르고 모든 해시코드에 대한 버킷도 다를 때 O(1)가 존재하게 된다.그렇지 않으면, 해시맵의 증가와 같이, 검색 순서는 일정하게 유지된다.

학문은 차치하고, 실제적인 관점에서는 해시맵스가 하찮은 성능 영향을 미치는 것으로 받아들여져야 한다(프로파일러가 달리 말하지 않는 한).

물론 해시맵의 성능은 주어진 개체에 대한 해시코드() 함수의 품질에 따라 달라진다.그러나 충돌 가능성이 매우 낮도록 기능을 구현하면 성능이 매우 우수할 것이다(이는 모든 경우에 엄밀히 말하면 O(1)는 아니지만 대부분의 경우 그러하다).

예를 들어 Oracle JRE의 기본 구현은 임의의 숫자(객체 인스턴스에 저장되어 있으므로 변경되지 않음)를 사용하는 것이지만, 또한 편향된 잠금을 비활성화하지만, 그것은 다른 논의 사항이다. 따라서 충돌 가능성은 매우 낮다.

참조URL: https://stackoverflow.com/questions/1055243/is-a-java-hashmap-search-really-o1