해시맵의 get/put 복잡성

해시맵의 get/put 복잡성

우리는 그렇게 말하는 것에 익숙하다.HashMap get/put동작은 O(1)입니다.단, 해시 구현에 따라 달라집니다.기본 개체 해시는 실제로 JVM 힙의 내부 주소입니다.우리가 주장하기에 충분하다고 확신하나요?get/putO(1)인가?

사용 가능한 메모리의 문제도 있습니다.javadocs에서 들은 바로는HashMap하중 계수는 0.75여야 합니다.JVM에 메모리가 부족하여 로드 팩터가 제한을 초과하면 어떻게 됩니까?

따라서 O(1)는 보증되지 않는 것 같습니다.말이 되나요? 아니면 제가 놓친 게 있나요?

그것은 여러 가지에 달려 있다.보통 O(1)이고, 해시 자체는 일정한 시간이고...그러나 해시 맵에 동일한 해시 코드를 반환하는 항목이 여러 개 있을 경우 계산에 시간이 오래 걸릴 수 있습니다.get그들이 전화하는 것을 반복해야 할 것이다.equals짝을 찾기 위해 각자에게 묻습니다.

최악의 경우,HashMap는 같은 해시 버킷 내의 모든 엔트리를 통과하기 위해 O(n) 룩업을 합니다(예를 들어 모든 엔트리가 동일한 해시 코드를 가지고 있는 경우).다행히도, 제 경험상, 그 최악의 시나리오는 실생활에서는 잘 나타나지 않습니다.따라서 O(1)는 확실히 보장되지 않지만, 일반적으로 사용하는 알고리즘과 데이터 구조를 고려할 때 가정해야 합니다.

JDK 8에서는HashMap는 순서를 매길 때 키를 비교할 수 있도록 조정되어 있으면 밀도가 높은 버킷이 트리로 구현되므로 동일한 해시 코드를 가진 엔트리가 다수 있어도 복잡도는 O(log n)가 됩니다.물론 동등성과 순서가 다른 키 타입이 있으면 문제가 발생할 수 있습니다.

그래, 해시맵에 필요한 메모리가 부족하면 문제가 생길 거야어떤 데이터 구조를 사용하든 마찬가지입니다.

해시맵은 이미 언급되어 있습니다.O(n/m)평균으로 말하면n아이템의 수와m사이즈입니다.또한 원칙적으로 모든 것이 하나의 링크 리스트로 붕괴될 수 있다고 언급되어 왔다.O(n)쿼리 시간(이 모든 것은 해시를 계산하는 시간이 일정하다고 가정합니다).

하지만 자주 언급되지 않는 것은 적어도 가능성이 있다는 것이다.1-1/n(99.9%의 확률로 1000개 항목의 경우) 가장 큰 버킷이 다음보다 많이 채워지지 않습니다.O(logn)따라서 이진 검색 트리의 평균 복잡도와 일치합니다. (그리고 상수는 양호하며, 더 엄격한 경계는(log n)*(m/n) + O(1)).

이 이론적인 한계에 필요한 것은 상당히 양호한 해시 함수를 사용하는 것입니다(Wikipedia 참조:유니버설 해싱그것은 다음과 같이 간단할 수 있다.a*x>>m해시 값을 제공하는 사용자는 사용자가 랜덤 상수를 어떻게 선택했는지 알 수 없습니다.

TL;DR: 매우 높은 확률로 해시맵의 최악의 경우 get/put 복잡도는 다음과 같습니다.O(logn).

기본 해시코드가 주소인지 잘 모르겠습니다.얼마 전에 해시코드 생성용 OpenJDK 소스를 읽었는데 조금 더 복잡한 것으로 기억합니다.여전히 좋은 분배를 보장하는 것은 아닐지도 모른다.그러나 해시맵에서 키로 사용하는 클래스는 기본 해시코드를 거의 사용하지 않기 때문에 이는 어느 정도 의미가 있습니다.이 클래스는 독자적인 실장을 제공하고 있기 때문에 좋을 것입니다.

게다가 (다시 말씀드리지만, 이것은 읽기 소스에 근거하고 있습니다) HashMap은 사용하기 전에 해시를 휘저어 단어 전체의 엔트로피를 맨 아래 비트로 혼합합니다.이것은 가장 허그한 해시맵을 제외한 모든 해시맵에 필요한 부분입니다.그렇게 하면 특별히 그렇게 하지 않는 해쉬를 처리하는 데 도움이 됩니다만, 일반적인 경우는 생각할 수 없습니다.

마지막으로 테이블이 과부하되면 병렬 링크 목록 세트로 퇴보하여 성능이 O(n)가 됩니다.특히 통과하는 링크의 수는 평균적으로 부하 계수의 절반입니다.

HashMap 연산은 hashCode 구현의 종속 요인입니다.이상적인 시나리오에서는 모든 오브젝트에 대해 고유한 해시 코드를 제공하는 양호한 해시 구현(해시 충돌 없음)을 가정해 보겠습니다.최선의 경우, 최악의 경우, 평균의 경우는 O(1)가 됩니다.hashCode의 부정한 실장에서는 항상 해시 콜리젼이 있는1개 또는 그 해시가 반환되는 시나리오를 생각해 봅시다.이 경우 시간 복잡도는 O(n)가 됩니다.

이제 메모리에 대한 질문의 두 번째 부분으로 넘어가면, JVM이 메모리 제약을 해결합니다.

동의:

• O(1)의 일반 상각 복잡도
• 나쁜 놈hashCode()구현 시 여러 충돌이 발생할 수 있습니다.즉, 최악의 경우 모든 객체가 같은 버킷으로 이동하기 때문에 각 버킷이 다음 버킷에 의해 백업되면 O(N)가 됩니다.List.
• Java 8 이후HashMap는 각 버킷에서 사용되는 노드(링크 리스트)를 TreeNodes(리스트가 8개보다 커지면 빨간색-검은색 트리)로 동적으로 치환하여 O(logN)의 퍼포먼스가 저하됩니다.

하지만 100% 정확성을 원한다면 이것이 완전한 진실은 아니다.의 실장hashCode()및 키의 종류Object(불변/캐시 또는 컬렉션) 또한 엄격한 용어로 실시간 복잡성에 영향을 미칠 수 있습니다.

다음 세 가지 경우를 가정해 보겠습니다.

1. HashMap<Integer, V>
2. HashMap<String, V>
3. HashMap<List<E>, V>

같은 복잡성을 가지고 있습니까?첫 번째 상각후 복잡도는 예상대로 O(1)이다.하지만 나머지 부분에서는 데이터 처리 능력의hashCode()즉, 알고리즘의 배열과 목록을 통과해야 할 수 있습니다.

우리는 모두 위의 arrays/lists의 사이즈는 k.를 취하다그리고나서,HashMap<String, V>그리고.HashMap<List<E>, V>와 비슷하게 O(k)상각 복잡함을 갖고 윌, O(k+logN)최악의 경우에 Java8.

*Note이를 사용하여String핵심은 좀 더 복잡한 사건, 왜냐하면 그것은 자바의 결과를 캐시 합니다 변하는 것이다.hashCode()개인 변수 에hash그래서 그것이 단 한번 계산됩니다.

/** Cache the hash code for the string */
    private int hash; // Default to 0

왜냐하면 Java's 하지만, 이상의 것 또한 자신의 가장 큰 사건을 겪고 있다.String.hashCode()구현 만약 조사하고 있다hash == 0컴퓨팅기 전에hashCode. 하지만 정말, 사각형 천이 출력 ahashcode0중에서"f5a5a608"로 여기에 memoization이 도움이 될지 안될 거다.

실제로, 그것은 O(1), 하지만 실제로 이것은 수학적으로non-sense 심각한 일반화 오류.그 O()표기법은 문제의 규모 무한대하는 경향이 있는 어떻게 이 알고리즘이 행동한다고 말한다.제한된 크기에 대한 O(1)알고리즘처럼 Hashmap get/put 작품.그 제한이 상당히 컴퓨터 메모리와 견해 의 주소 지정 지점에서 무한대에서 멀리 떨어져에서 크다.

하나는hashmap get/put은 O(1) 말한다 정말 시간이 get/put에 필요한 차별이 없어지고 그 hashmap에 있는 요소의 개수에 와서 hashmap 실제 계산을 시스템에 표시될 수 있는 의존하지 않는다 일정하다 해야 한다.문제가 그 크기를 넘어 더 큰 해시맵이 필요한 경우, 잠시 후 설명 가능한 다른 요소가 부족해질수록 한 요소를 설명하는 비트 수도 증가합니다.예를 들어 32비트 번호를 저장하기 위해 해시맵을 사용한 후 나중에 문제 크기를 증가시켜 해시맵에 2^32비트 이상의 요소가 포함되도록 하면 개별 요소는 32비트 이상으로 기술됩니다.

개개의 요소를 기술하는 데 필요한 비트 수는 log(N)입니다.여기서 N은 요소의 최대수이므로 get과 put은 실제로는 O(log N)입니다.

트리 세트(O(log n)와 비교하면 해시 세트는 O(long(max(n))이며, 특정 실장에서는 max(n)가 고정되어 있기 때문에 이 값은 O(1)인 것처럼 느껴집니다.이는 변하지 않고(비트로 측정되는 오브젝트의 사이즈는), 해시 코드를 계산하는 알고리즘이 빠릅니다.

마지막으로, 데이터 구조에서 요소가 O(1)인 경우, 뜬금없이 정보를 생성합니다.n개의 요소의 데이터 구조를 가지고 있기 때문에 나는 n개의 다른 방법으로 하나의 요소를 선택할 수 있다.이를 통해 로그(n) 비트 정보를 인코딩할 수 있습니다.이것을 제로비트(O(1)의 의미)로 부호화할 수 있는 경우는, 무한 압축 ZIP 알고리즘을 작성했습니다.

언급URL : https://stackoverflow.com/questions/4553624/hashmap-get-put-complexity