Java HashMap의 충돌 해결

Java HashMap의 충돌 해결

---

Java HashMap는 put메소드를 사용 하여 K / V 쌍을 HashMap. 내가 put방법 을 사용 했고 이제 10과 17 로 HashMap<Integer, Integer>하나의 항목이 있다고 가정 해 봅시다 .keyvalue

여기에 10,20을 삽입하면 HashMap동일한 키 10 때문에 충돌로 인해 이전 항목이이 항목으로 대체됩니다.

키가 충돌 HashMap하면 이전 K / V 쌍이 새 K / V 쌍으로 바뀝니다.

그래서 내 질문은 언제 HashMap체인 충돌 해결 기술을 사용합니까?

linkedlist키가 10이고 값이 17,20 인 a 를 형성하지 않은 이유는 무엇 입니까?

---

쌍을 삽입 한 (10, 17)다음 을 삽입하면 (10, 20)기술적으로 충돌이 발생하지 않습니다. 주어진 키의 이전 값을 새 값으로 바꾸는 것입니다 10(두 경우 모두 10은 10과 같고 10의 해시 코드는 항상 10이기 때문입니다).

충돌은 여러 키가 동일한 버킷에 해시 될 때 발생합니다. 이 경우 해당 키를 구분할 수 있는지 확인해야합니다. 체인 충돌 해결은이를 위해 사용되는 기술 중 하나입니다.

예를 들어,의 그 두 개의 문자열 가정하자 "abra ka dabra"및 "wave my wand"수율 해시 코드 100와 200각각을. 총 어레이 크기가 10이라고 가정하면 둘 다 동일한 버킷 ( 100 % 10및 200 % 10)에있게됩니다. 체인을 사용하면 할 때마다 map.get( "abra ka dabra" );키와 관련된 올바른 값을 얻게됩니다. 자바에서 해시 맵의 경우 equals메소드 를 사용하여 수행합니다 .

---

A의 HashMap키를 포함하는, 목적 hashCode()및 equals(Object)방법에 관한 것이다.

맵에 새 항목을 삽입하면이 항목 hashCode이 이미 알려져 있는지 확인합니다 . 그런 다음이 해시 코드를 사용하여 모든 개체를 반복하고 .equals(). 경우 동일한 개체가 발견, 새로운 값이 이전을 대체합니다. 그렇지 않은 경우 맵에 새 항목이 생성됩니다.

일반적으로 맵에 대해 이야기 하면 두 오브젝트가 동일 하지만 서로 다를 때 충돌 을 사용 hashCode합니다. 내부적으로 목록에 저장됩니다.

---

실제로 연결 목록을 만들 수 있습니다. 그것은 뿐이다 Map계약이 항목을 대체하는 것이 필요합니다

V put(K key, V value)

지정된 값을이 맵의 지정된 키와 연결합니다 (선택적 작업). 맵에 이전에 키에 대한 매핑이 포함 된 경우 이전 값이 지정된 값으로 대체됩니다. (맵 m은 m.containsKey (k)가 true를 반환하는 경우에만 키 k에 대한 매핑을 포함한다고합니다.)

http://docs.oracle.com/javase/6/docs/api/java/util/Map.html

지도가 값 목록을 저장하려면 Multimap. Google은 다음과 같습니다. http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Multimap.html

Map과 유사하지만 여러 값을 단일 키에 연결할 수있는 컬렉션입니다. 키는 같지만 값이 다른 put (K, V)를 두 번 호출하면 멀티 맵에는 키에서 두 값으로의 매핑이 포함됩니다.

편집 : 충돌 해결

조금 다릅니다. 충돌은 두 개의 다른 키가 동일한 해시 코드를 가지거나 다른 해시 코드를 가진 두 개의 키가 기본 배열의 동일한 버킷에 매핑 될 때 발생합니다.

HashMap의 소스를 고려하십시오 (비트 및 조각 제거됨).

public V put(K key, V value) {
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    // i is the index where we want to insert the new element
    addEntry(hash, key, value, i);
    return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
    // take the entry that's already in that bucket
    Entry<K,V> e = table[bucketIndex];
    // and create a new one that points to the old one = linked list
    table[bucketIndex] = new Entry<>(hash, key, value, e);
}

의 Entry클래스 HashMap가 목록처럼 작동 하는 방법에 대해 궁금한 사람들을 위해 를 구현하는 HashMap자체 정적 Entry클래스를 정의하는 것으로 밝혀졌습니다 Map.Entry. 소스 코드를 보면 직접 확인할 수 있습니다.

HashMap 용 GrepCode

---

우선, 당신은 해싱의 개념이 약간 잘못되었고 Sanjay 씨에 의해 수정되었습니다.

그리고 예, Java는 실제로 충돌 해결 기술을 구현합니다. 이때 두 개의 키가 동일한 값으로 해시되면 (사용되는 내부 배열의 크기가 유한하고 어떤 시점에서 hashcode () 메서드가 두 개의 다른 키에 대해 동일한 해시 값을 반환하므로) 버킷에 연결된 목록이 형성됩니다. 모든 정보가 키-값 쌍을 포함하는 Map.Entry 객체로 입력되는 위치입니다. 키를 통해 객체에 액세스하려면 항목이 이러한 목록에있는 경우 최악의 경우 O (n)이 필요합니다. 이러한 목록의 각 키와 함께 전달한 키 간의 비교는 equals () 메서드에 의해 수행됩니다.

그러나 Java 8에서 연결된 목록은 트리로 대체됩니다 (O (log n)).

---

There is difference between collision and duplication. Collision means hashcode and bucket is same, but in duplicate, it will be same hashcode,same bucket, but here equals method come in picture.

Collision detected and you can add element on existing key. but in case of duplication it will replace new value.

---

Your case is not talking about collision resolution, it is simply replacement of older value with a new value for the same key because Java's HashMap can't contain duplicates (i.e., multiple values) for the same key.

In your example, the value 17 will be simply replaced with 20 for the same key 10 inside the HashMap.

If you are trying to put a different/new value for the same key, it is not the concept of collision resolution, rather it is simply replacing the old value with a new value for the same key. It is how HashMap has been designed and you can have a look at the below API (emphasis is mine) taken from here.

public V put(K key, V value)

Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced.

---

On the other hand, collision resolution techniques comes into play only when multiple keys end up with the same hashcode (i.e., they fall in the same bucket location) where an entry is already stored. HashMap handles the collision resolution by using the concept of chaining i.e., it stores the values in a linked list (or a balanced tree since Java8, depends on the number of entries).

---

It isn't defined to do so. In order to achieve this functionality, you need to create a map that maps keys to lists of values:

Map<Foo, List<Bar>> myMap;

Or, you could use the Multimap from google collections / guava libraries

---

There is no collision in your example. You use the same key, so the old value gets replaced with the new one. Now, if you used two keys that map to the same hash code, then you'd have a collision. But even in that case, HashMap would replace your value! If you want the values to be chained in case of a collision, you have to do it yourself, e.g. by using a list as a value.

---

When multiple keys end up in same hash code which is present in same bucket. When the same key has different values then the old value will be replaced with new value.

Liked list converted to balanced Binary tree from java 8 version on wards in worst case scenario.

Collision happen when 2 distinct keys generate the same hashcode() value. When there are more collisions then there it will leads to worst performance of hashmap.

Objects which are are equal according to the equals method must return the same hashCode value. When both objects return the same has code then they will be moved into the same bucket.

ReferenceURL : https://stackoverflow.com/questions/19691920/collision-resolution-in-java-hashmap