HashTable은 충돌을 어떻게 처리합니까?

HashTable은 충돌을 어떻게 처리합니까?

---

학위 수업 HashTable에서 새 키 항목이 다른 항목과 충돌하면 '다음 사용 가능한'버킷에 새 항목을 배치 한다는 것을 들었습니다 .

HashTable충돌 키로 다시 호출 할 때이 충돌이 발생하면 어떻게 올바른 값을 반환할까요?

나는 유형 Keys이 있다고 가정하고 Java가 생성 한 기본값을 반환합니다.StringhashCode()

자체 해싱 함수를 구현하고 조회 테이블 (예 : a HashMap또는 Dictionary)의 일부로 사용하는 경우 충돌을 처리하기위한 전략은 무엇입니까?

소수와 관련된 메모도 보았습니다! Google 검색에서 정보가 명확하지 않습니다.

---

해시 테이블은 두 가지 방법 중 하나로 충돌을 처리합니다.

옵션 1 : 각 버킷에 해당 버킷에 해시 된 요소의 링크 된 목록이 포함되도록합니다. 이것이 잘못된 해시 함수가 해시 테이블에서 조회를 매우 느리게 만들 수있는 이유입니다.

옵션 2 : 해시 테이블 항목이 모두 가득 차면 해시 테이블이 보유한 버킷 수를 늘린 다음 테이블의 모든 요소를 ​​재배포 할 수 있습니다. 해시 함수는 정수를 반환하고 해시 테이블은 해시 함수의 결과를 가져 와서 버킷에 도달 할 수 있도록 테이블의 크기에 맞게 수정해야합니다. 따라서 크기를 늘리면 운이 좋으면 객체를 다른 버킷으로 보낼 수있는 모듈로 계산을 다시 해시하고 실행합니다.

Java는 해시 테이블 구현에서 옵션 1과 2를 모두 사용합니다.

---

"새 키 항목이 다른 항목과 충돌하면 해시 테이블이 '다음 사용 가능한'버킷에 새 항목을 배치합니다."에 대해 이야기 할 때 해시 테이블의 충돌 해결 에 대한 개방형 주소 지정 전략 에 대해 이야기하고 있습니다.

---

충돌을 해결하기 위해 해시 테이블에 대한 몇 가지 전략이 있습니다.

첫 번째 종류의 큰 방법은 키 (또는 그에 대한 포인터)를 관련 값과 함께 테이블에 저장해야합니다. 여기에는 다음이 추가로 포함됩니다.

• 별도의 체인

• 개방 주소 지정

• 통합 해싱
• 뻐꾸기 해싱
• Robin Hood 해싱
• 2-choice 해싱
• Hopscotch 해싱

---

충돌을 처리하는 또 다른 중요한 방법은 Dynamic resizing 이며, 여기에는 여러 가지 방법이 있습니다.

• 모든 항목을 복사하여 크기 조정
• 증분 크기 조정
• 단조로운 키

---

편집 : 위의 내용은 wiki_hash_table 에서 빌려 왔으며 더 많은 정보를 얻으려면 가야합니다.

---

충돌을 처리하는 데 사용할 수있는 여러 기술이 있습니다. 그들 중 일부를 설명하겠습니다

연결 : 연결 에서는 배열 인덱스를 사용하여 값을 저장합니다. 두 번째 값의 해시 코드도 동일한 인덱스를 가리키면 해당 인덱스 값을 연결된 목록으로 바꾸고 해당 인덱스를 가리키는 모든 값은 연결된 목록에 저장되고 실제 배열 인덱스는 연결된 목록의 머리를 가리 킵니다. 그러나 배열의 인덱스를 가리키는 해시 코드가 하나만있는 경우 값은 해당 인덱스에 직접 저장됩니다. 값을 검색하는 동안 동일한 논리가 적용됩니다. 충돌을 피하기 위해 Java HashMap / Hashtable에서 사용됩니다.

선형 프로빙 : 이 기술은 저장할 값보다 테이블에 더 많은 인덱스가있을 때 사용됩니다. 선형 프로빙 기술은 빈 슬롯을 찾을 때까지 계속 증가한다는 개념에서 작동합니다. 의사 코드는 다음과 같습니다.

index = h(k) 

while( val(index) is occupied) 

index = (index+1) mod n

이중 해싱 기술 : 이 기술에서는 두 개의 해싱 함수 h1 (k) 및 h2 (k)를 사용합니다. h1 (k)의 슬롯이 점유되면 두 번째 해싱 함수 h2 (k)가 인덱스를 증가시키는 데 사용됩니다. 의사 코드는 다음과 같습니다.

index = h1(k)

while( val(index) is occupied)

index = (index + h2(k)) mod n

Linear probing and double hashing techniques are part of open addressing technique and it can only be used if available slots are more than the number of items to be added. It takes less memory than chaining because there is no extra structure used here but its slow because of lot of movement happen until we find an empty slot. Also in open addressing technique when an item is removed from a slot we put an tombstone to indicate that the item is removed from here that is why its empty.

For more information see this site.

---

I strongly suggest you to read this blog post which appeared on HackerNews recently: How HashMap works in Java

In short, the answer is

What will happen if two different HashMap key objects have same hashcode?

They will be stored in same bucket but no next node of linked list. And keys equals () method will be used to identify correct key value pair in HashMap.

---

I've heard in my degree classes that a HashTable will place a new entry into the 'next available' bucket if the new Key entry collides with another.

This is actually not true, at least for the Oracle JDK (it is an implementation detail that could vary between different implementations of the API). Instead, each bucket contains a linked list of entries prior to Java 8, and a balanced tree in Java 8 or above.

then how would the HashTable still return the correct Value if this collision occurs when calling for one back with the collision key?

It uses the equals() to find the actually matching entry.

If I implement my own hashing function and use it as part of a look-up table (i.e. a HashMap or Dictionary), what strategies exist for dealing with collisions?

There are various collision handling strategies with different advantages and disadvantages. Wikipedia's entry on hash tables gives a good overview.

---

Update since Java 8: Java 8 uses a self-balanced tree for collision-handling, improving the worst case from O(n) to O(log n) for lookup. The use of a self-balanced tree was introduced in Java 8 as an improvement over chaining (used until java 7), which uses a linked-list, and has a worst case of O(n) for lookup (as it needs to traverse the list)

To answer the second part of your question, insertion is done by mapping a given element to a given index in the underlying array of the hashmap, however, when a collision occurs, all elements must still be preserved (stored in a secondary data-structure, and not just replaced in the underlying array). This is usually done by making each array-component (slot) be a secondary datastructure (aka bucket), and the element is added to the bucket residing on the given array-index (if the key does not already exist in the bucket, in which case it is replaced).

During lookup, the key is hashed to it's corresponding array-index, and search is performed for an element matching the (exact) key in the given bucket. Because the bucket does not need to handle collisions (compares keys directly), this solves the problem of collisions, but does so at the cost of having to perform insertion and lookup on the secondary datastructure. The key point is that in a hashmap, both the key and the value is stored, and so even if the hash collides, keys are compared directly for equality (in the bucket), and thus can be uniquely identified in the bucket.

Collission-handling brings the worst-case performance of insertion and lookup from O(1) in the case of no collission-handling to O(n) for chaining (a linked-list is used as secondary datastructure) and O(log n) for self-balanced tree.

References:

Java 8 has come with the following improvements/changes of HashMap objects in case of high collisions.

• The alternative String hash function added in Java 7 has been removed.

• Buckets containing a large number of colliding keys will store their entries in a balanced tree instead of a linked list after certain threshold is reached.

Above changes ensure performance of O(log(n)) in worst case scenarios (https://www.nagarro.com/en/blog/post/24/performance-improvement-for-hashmap-in-java-8)

---

As there is some confusion about which algorithm Java's HashMap is using (in the Sun/Oracle/OpenJDK implementation), here the relevant source code snippets (from OpenJDK, 1.6.0_20, on Ubuntu):

/**
 * Returns the entry associated with the specified key in the
 * HashMap.  Returns null if the HashMap contains no mapping
 * for the key.
 */
final Entry<K,V> getEntry(Object key) {
    int hash = (key == null) ? 0 : hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

This method (cite is from lines 355 to 371) is called when looking up an entry in the table, for example from get(), containsKey() and some others. The for loop here goes through the linked list formed by the entry objects.

Here the code for the entry objects (lines 691-705 + 759):

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    final int hash;

    /**
     * Creates new entry.
     */
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }

  // (methods left away, they are straight-forward implementations of Map.Entry)

}

Right after this comes the addEntry() method:

/**
 * Adds a new entry with the specified key, value and hash code to
 * the specified bucket.  It is the responsibility of this
 * method to resize the table if appropriate.
 *
 * Subclass overrides this to alter the behavior of put method.
 */
void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    if (size++ >= threshold)
        resize(2 * table.length);
}

This adds the new Entry on the front of the bucket, with a link to the old first entry (or null, if no such one). Similarily, the removeEntryForKey() method goes through the list and takes care of deleting only one entry, letting the rest of the list intact.

So, here is a linked entry list for each bucket, and I very doubt that this changed from _20 to _22, since it was like this from 1.2 on.

(This code is (c) 1997-2007 Sun Microsystems, and available under GPL, but for copying better use the original file, contained in src.zip in each JDK from Sun/Oracle, and also in OpenJDK.)

---

It will use the equals method to see if the key is present even and especially if there are more than one element in the same bucket.

---

There are various methods for collision resolution.Some of them are Separate Chaining,Open addressing,Robin Hood hashing,Cuckoo Hashing etc.

Java uses Separate Chaining for resolving collisions in Hash tables.Here is a great link to how it happens: http://javapapers.com/core-java/java-hashtable/

---

다음은 자바로 구현 된 매우 간단한 해시 테이블입니다. 구현 put()및 에서만 가능 get()하지만 원하는 것을 쉽게 추가 할 수 있습니다. hashCode()모든 객체에 의해 구현되는 자바의 메소드 에 의존 합니다. 자신 만의 인터페이스를 쉽게 만들 수 있습니다.

interface Hashable {
  int getHash();
}

원하는 경우 키로 구현하도록 강제합니다.

public class Hashtable<K, V> {
    private static class Entry<K,V> {
        private final K key;
        private final V val;

        Entry(K key, V val) {
            this.key = key;
            this.val = val;
        }
    }

    private static int BUCKET_COUNT = 13;

    @SuppressWarnings("unchecked")
    private List<Entry>[] buckets = new List[BUCKET_COUNT];

    public Hashtable() {
        for (int i = 0, l = buckets.length; i < l; i++) {
            buckets[i] = new ArrayList<Entry<K,V>>();
        }
    }

    public V get(K key) {
        int b = key.hashCode() % BUCKET_COUNT;
        List<Entry> entries = buckets[b];
        for (Entry e: entries) {
            if (e.key.equals(key)) {
                return e.val;
            }
        }
        return null;
    }

    public void put(K key, V val) {
        int b = key.hashCode() % BUCKET_COUNT;
        List<Entry> entries = buckets[b];
        entries.add(new Entry<K,V>(key, val));
    }
}

참고 URL : https://stackoverflow.com/questions/4980757/how-do-hashtables-deal-with-collisions