해시 테이블 : 충돌, 크기 조정, 해싱

Big O 표기법을 이해하고 있다고 가정합니다. 예제는 JavaScript에 있습니다. 정보 참고자료 Gayle Laakmann McDowell의 "코딩 인터뷰 크래킹"

해시 테이블 이해

사전, 해시 맵, 해시 테이블에 대해 들어보셨든 본질적으로 모두 동일합니다. 이 블로그에서는 단순화를 위해 이 데이터 구조를 해시 테이블로 참조하겠습니다.

해시 테이블이 무엇인지부터 정의해 보겠습니다. 해시 테이블은 매우 효율적인 조회를 위해 키-값 쌍 형식으로 키를 값에 매핑하는 데이터 구조입니다. 이를 구현하는 방법에는 여러 가지가 있습니다.

---

해시 테이블의 주요 구성 요소

연결된 목록 배열과 해싱 함수를 사용하여 해시 테이블을 구현할 수 있습니다. 해싱 함수가 무엇인지 자세히 알아보겠습니다.

해싱 함수란 무엇입니까?

해싱 함수는 해시 테이블의 중요한 구성 요소입니다. 이는 입력(또는 '키')을 받아 일반적으로 정수 형식의 고정 크기 바이트 문자열을 반환하는 함수 형태의 알고리즘입니다. 출력을 해시 코드 또는 간단히 해시라고 합니다.

해시 테이블의 맥락에서 해싱 함수의 주요 목적은 원하는 값을 찾을 수 있는 버킷/슬롯 배열의 유효한 인덱스에 해시 코드를 매핑하는 것입니다. 우리의 경우 이러한 버킷/슬롯은 연결된 목록이 됩니다.

좋은 해싱 함수의 특징:

• 결정적: 주어진 입력에 대해 항상 동일한 해시 출력을 생성해야 합니다.
• 균일 분포: 예상 입력을 출력 범위 전체에 걸쳐 최대한 균등하게 매핑해야 합니다.
• 효율적: 계산이 빨라야 합니다.
• 눈사태 효과: 입력의 작은 변화로 인해 해시 출력이 크게 달라집니다.

연결리스트 배열을 사용하는 이유는 무엇입니까?

해시 테이블 구현에서 연결 목록 배열을 사용하는 것은 체이닝이라고 알려진 일반적인 기술입니다. 이 접근 방식은 다음과 같은 몇 가지 장점을 제공합니다.

1. 충돌 처리: 연결 목록 배열을 사용하는 주된 이유는 충돌을 효율적으로 처리하기 위한 것입니다. 두 개의 키가 해시되어 동일한 인덱스에 매핑되면 해당 인덱스의 연결 목록에 새 키-값 쌍을 추가하기만 하면 됩니다.
2. 공간 효율성: 해시 테이블이 기본 배열의 크기보다 더 많은 항목을 저장할 수 있게 해줍니다. 각 배열 슬롯은 연결된 목록을 통해 여러 항목을 보유할 수 있습니다.

Array:  [0] -> (key1, value1) -> (key2, value2)
        [1] -> (key3, value3)
        [2] -> (key4, value4) -> (key5, value5) -> (key6, value6)
        [3] -> Empty
        [4] -> (key7, value7)

이 예에서 키 1과 2는 인덱스 0으로 해시되고 키 4, 5, 6은 모두 인덱스 2로 해시됩니다.

---

키-값 쌍 삽입

이제 해시 함수와 체이닝을 사용하는 이유를 잘 이해했으므로 키-값 쌍을 해시 테이블에 삽입하는 흐름을 살펴보겠습니다.

1. 키(모든 값)를 삽입할 때 먼저 키의 해시 코드(일반적으로 int 또는 long)를 계산합니다. 무한한 키 개수와 유한한 정수 개수가 있을 수 있으므로 두 개의 서로 다른 키가 동일한 해시 코드를 가질 수 있습니다.

2. 해시 코드를 배열의 인덱스에 매핑합니다. 해시 코드를 배열에 매핑하는 일반적인 방법은 모듈러스 연산자를 사용하는 것입니다. (예: 해시(키) % array.length)). 이 방법을 사용하면 두 개의 서로 다른 해시 코드가 동일한 인덱스에 매핑될 수 있습니다.

3. 인덱스에는 키와 값의 연결된 목록이 있습니다. 이 인덱스에 키-값 쌍을 저장합니다. 키에 동일한 해시 코드가 있거나 해시 코드가 동일한 인덱스에 매핑되면 충돌이 발생합니다.

키-값 쌍에 액세스

해시 테이블 구현에서는 키-값 쌍에 액세스하는 것이 매우 효율적입니다. 간단히 키에서 해시 코드를 계산한 다음 해시 코드에서 인덱스를 계산하고 마지막으로 이 키가 있는 값을 연결 목록에서 검색합니다.

좋은 구현을 가정하고 키-값 쌍에 액세스(삽입 및 삭제도 포함)하는 데 가 소요됩니다. $O(1)$O(1) .

---

What Makes a Hash Table Implementation "Good"?

A well-implemented hash table should balance efficiency, space utilization, and collision handling. Here are the key factors that contribute to a good hash table implementation:

A Good Hash Function

The heart of any hash table is its hash function. A good hash function should:

• Be quick to compute
• Minimize collisions

Optimal Load Factor

The load factor is the ratio of filled slots to total slots in the hash table. Maintaining an appropriate load factor is crucial:

A typical sweet spot is between 0.6 and 0.75

• Too low (< 0.5): Wastes space
• Too high (> 0.8): Increases collision risk

Collision Resolution Techniques

Two primary methods for handling collisions are:

1. Chaining: Each table position stores a linked list of collided items. Simple to implement but can lead to slower lookups if chains become long.

2. Open Addressing: If a collision occurs, look for the next available slot. Keeps all data in the table but requires careful implementation to avoid clustering of stored data.

Note that chaining and open-addressing cannot coexist easily. Logically, it would not make sense to look for the next available slot but store collided items at a specific index.

Dynamic Resizing

As the number of elements grows, the hash table should resize to maintain performance:

Typically, the table size is doubled when the load factor exceeds a threshold. All elements need to be rehashed into the new, larger table.

This operation is expensive but infrequent, keeping the amortized time complexity at O(1).

---

JavaScript Implementation

This implementation will utilize resizing and chaining for collision resolution. We will assume that our keys are integers.

For the hash function + mapping, we will keep it very simple and simply perform the following given a key:

$$key\mathrm{\%}arraycapacity$$key%arraycapacity

Classical OOP

class HashNode {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.next = null;
    }
}

class HashTable {
    constructor(capacity = 16) {
        this.capacity = capacity;
        this.size = 0;
        this.buckets = new Array(this.capacity).fill(null);
        this.threshold = 0.75;
    }

    hash(key) {
        return key % this.capacity;
    }

    insert(key, value) {
        const index = this.hash(key);
        if (!this.buckets[index]) {
            this.buckets[index] = new HashNode(key, value);
            this.size++;
        } else {
            let currentNode = this.buckets[index];
            while (currentNode.next) {
                if (currentNode.key === key) {
                    currentNode.value = value;
                    return;
                }
                currentNode = currentNode.next;
            }
            if (currentNode.key === key) {
                currentNode.value = value;
            } else {
                currentNode.next = new HashNode(key, value);
                this.size++;
            }
        }

        if (this.size / this.capacity >= this.threshold) {
            this.resize();
        }
    }

    get(key) {
        const index = this.hash(key);
        let currentNode = this.buckets[index];
        while (currentNode) {
            if (currentNode.key === key) {
                return currentNode.value;
            }
            currentNode = currentNode.next;
        }
        return undefined;
    }

    remove(key) {
        const index = this.hash(key);
        if (!this.buckets[index]) {
            return false;
        }
        if (this.buckets[index].key === key) {
            this.buckets[index] = this.buckets[index].next;
            this.size--;
            return true;
        }
        let currentNode = this.buckets[index];
        while (currentNode.next) {
            if (currentNode.next.key === key) {
                currentNode.next = currentNode.next.next;
                this.size--;
                return true;
            }
            currentNode = currentNode.next;
        }
        return false;
    }

    resize() {
        const newCapacity = this.capacity * 2;
        const newBuckets = new Array(newCapacity).fill(null);
        this.buckets.forEach(head => {
            while (head) {
                const newIndex = head.key % newCapacity;
                const next = head.next;
                head.next = newBuckets[newIndex];
                newBuckets[newIndex] = head;
                head = next;
            }
        });
        this.buckets = newBuckets;
        this.capacity = newCapacity;
    }

    getSize() {
        return this.size;
    }

    getCapacity() {
        return this.capacity;
    }
}

Functional OOP

function createHashTable(initialCapacity = 16) {
    let capacity = initialCapacity;
    let size = 0;
    let buckets = new Array(capacity).fill(null);
    const threshold = 0.75;

    function hash(key) {
        return key % capacity;
    }

    function resize() {
        const newCapacity = capacity * 2;
        const newBuckets = new Array(newCapacity).fill(null);
        buckets.forEach(function(head) {
            while (head) {
                const newIndex = head.key % newCapacity;
                const next = head.next;
                head.next = newBuckets[newIndex];
                newBuckets[newIndex] = head;
                head = next;
            }
        });
        buckets = newBuckets;
        capacity = newCapacity;
    }

    return {
        insert: function(key, value) {
            const index = hash(key);
            const newNode = { key, value, next: null };

            if (!buckets[index]) {
                buckets[index] = newNode;
                size++;
            } else {
                let currentNode = buckets[index];
                while (currentNode.next) {
                    if (currentNode.key === key) {
                        currentNode.value = value;
                        return;
                    }
                    currentNode = currentNode.next;
                }
                if (currentNode.key === key) {
                    currentNode.value = value;
                } else {
                    currentNode.next = newNode;
                    size++;
                }
            }

            if (size / capacity >= threshold) {
                resize();
            }
        },

        get: function(key) {
            const index = hash(key);
            let currentNode = buckets[index];
            while (currentNode) {
                if (currentNode.key === key) {
                    return currentNode.value;
                }
                currentNode = currentNode.next;
            }
            return undefined;
        },

        remove: function(key) {
            const index = hash(key);
            if (!buckets[index]) {
                return false;
            }
            if (buckets[index].key === key) {
                buckets[index] = buckets[index].next;
                size--;
                return true;
            }
            let currentNode = buckets[index];
            while (currentNode.next) {
                if (currentNode.next.key === key) {
                    currentNode.next = currentNode.next.next;
                    size--;
                    return true;
                }
                currentNode = currentNode.next;
            }
            return false;
        },

        getSize: function() {
            return size;
        },

        getCapacity: function() {
            return capacity;
        }
    };
}

위 내용은 해시 테이블 : 충돌, 크기 조정, 해싱의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!