개방 주소법은 해시 충돌이 발생하면 테이블 내의 새로운 주소를 탐사(Probe)한 후, 비어있는 곳에 충돌된 데이터를 입력하는 방식이다. 해시 함수를 통해서 얻은 인덱스가 아니라 다른 인덱스를 허용한다는 의미로 개방 주소(Open Address)라고 한다.
선형 탐사법(Linear Probing)
선형 탐사법(Linear Probing)은 말 그대로 선형으로 순차적으로 탐사하는 방법이다.
선형 탐사법은 충돌이 났을 때 정해진 n 칸만큼의 옆 방을 주는 방법이다.
만약에 n=1이라면 2번 인덱스를, n=3이라면 4번 인덱스에 값을 저장할 것이다.
선형 탐사법의 단점은 특정 해시 값의 주변이 모두 채워져있는 일차 군집화(Primary Clustering)문제에 취약하다는 것이다.
제곱 탐사법(Quadratic Probing)
제곱 탐사법(Quadratic Probing)은 선형 탐사법과 동일하지만 탐사하는 폭이 고정폭아닌 제곱으로 늘어난다는 것이 다르다.
이렇게 제곱 탐사법을 사용하면 충돌이 발생하더라도 데이터의 밀집도가 선형 탐사법보다 많이 낮기 때문에 다른 해시값까지 영향을 받아서 연쇄적으로 충돌이 발생할 확률이 많이 줄어든다.
그래도 결국 해시로 1이 여러번 나오면 계속 충돌이 나는 것은 피할 수 없다.
결국 데이터의 군집은 피할 수 없는 숙명이므로 이차 군집화(Secondary Clustering)현상이 일어난다.
이중해싱(Double Hashing)
이중 해싱은 말 그대로 해시 함수를 이중으로 사용하는 것이다.
하나는 기존과 마찬가지로 최초 해시를 얻을 때 사용하고, 다른 하나는 충돌이 났을 경우 탐사 이동폭을 얻기 위해 사용한다.
분리 연결법(Separate Chaining)
분리 연결법은 개방 주소법과는 다른 개념으로 접근하는 충돌 우회 방법이다. 분리 연결법은 해쉬 테이블의 버킷에 하나의 값이 아니라 링크드 리스트(Linked List)나 트리(Tree)를 사용한다.
분리 연결법을 사용하려면 해시 함수의 역할이 굉장히 중요하다. 결국 균일하지 못한 해시를 사용해서 특정 인덱스에 데이터가 몰리게 된다면 다른 곳은 텅텅 비어있는데 한 버킷에 저장된 리스트의 길이만 계속 길어지기 때문이다.
결국 내가 찾고자 하는 값이 리스트의 맨 마지막에 위치하고 있다면 링크드 리스트를 처음부터 끝까지 다 탐색해야하기 때문에
O(n)의 시간복잡도를 가지게 된다. 그렇기 때문에 최대한 저장하고 하는 데이터를 균일하게 퍼트려서 리스트의 길이를 어느 정도로 유지해주는 해시 함수의 역할이 중요한 것이다.
테이블 크기 재할당(Resizing)
해시 테이블은 고정적인 공간을 할당해서 많은 데이터를 담기 위한 자료구조인 만큼 언젠가 데이터가 넘치기 마련이다.
개방 주소법을 사용하는 경우에는 테이블이 실제로 꽉 차서 더이상 저장을 못하는 상황이 발생할 것이고, 분리 연결법을 사용하는 경우에는 테이블에 빈 공간이 적어지면서 충돌이 발생할 수록 각각의 버킷에 저장된 리스트가 점점 더 길어져서 리스트를 탐색하는 리소스가 너무 늘어난 상황이 발생할 것이다.
그렇기 때문에 해시 테이블은 꽉꽉 아낌없이 채우기보다는 어느 정도 비워져 있는 것이 성능 상 더 좋으며, 해시 테이블을 운용할 때는 어느 정도 데이터가 차면 테이블의 크기를 늘려줘야한다.
이건 특별한 알고리즘이라기보다는 그냥 기존 크기의 두 배 정도로 새로운 테이블을 선언해서 기존 테이블의 데이터를 그대로 옮겨 담는 방법을 사용한다. 분리 연결법을 사용한 해시 테이블의 경우 재해싱(Rehashing)을 통해 너무 길어진 리스트의 길이를 나누어서 다시 저장하는 방법을 사용하기도 한다.
JavaScript
개방 주소법(Open Address)
개방 주소법은 해시 충돌이 발생하면 테이블 내의 새로운 주소를 탐사(Probe)한 후, 비어있는 곳에 충돌된 데이터를 입력하는 방식이다. 해시 함수를 통해서 얻은 인덱스가 아니라 다른 인덱스를 허용한다는 의미로 개방 주소(Open Address)라고 한다.
선형 탐사법(Linear Probing) 선형 탐사법(Linear Probing)은 말 그대로 선형으로 순차적으로 탐사하는 방법이다.
선형 탐사법은 충돌이 났을 때 정해진 n 칸만큼의 옆 방을 주는 방법이다. 만약에 n=1이라면 2번 인덱스를, n=3이라면 4번 인덱스에 값을 저장할 것이다. 선형 탐사법의 단점은 특정 해시 값의 주변이 모두 채워져있는 일차 군집화(Primary Clustering)문제에 취약하다는 것이다.
제곱 탐사법(Quadratic Probing) 제곱 탐사법(Quadratic Probing)은 선형 탐사법과 동일하지만 탐사하는 폭이 고정폭아닌 제곱으로 늘어난다는 것이 다르다. 이렇게 제곱 탐사법을 사용하면 충돌이 발생하더라도 데이터의 밀집도가 선형 탐사법보다 많이 낮기 때문에 다른 해시값까지 영향을 받아서 연쇄적으로 충돌이 발생할 확률이 많이 줄어든다. 그래도 결국 해시로 1이 여러번 나오면 계속 충돌이 나는 것은 피할 수 없다. 결국 데이터의 군집은 피할 수 없는 숙명이므로 이차 군집화(Secondary Clustering)현상이 일어난다.
이중해싱(Double Hashing) 이중 해싱은 말 그대로 해시 함수를 이중으로 사용하는 것이다. 하나는 기존과 마찬가지로 최초 해시를 얻을 때 사용하고, 다른 하나는 충돌이 났을 경우 탐사 이동폭을 얻기 위해 사용한다.
분리 연결법(Separate Chaining)
분리 연결법은 개방 주소법과는 다른 개념으로 접근하는 충돌 우회 방법이다. 분리 연결법은 해쉬 테이블의 버킷에 하나의 값이 아니라 링크드 리스트(Linked List)나 트리(Tree)를 사용한다.
분리 연결법을 사용하려면 해시 함수의 역할이 굉장히 중요하다. 결국 균일하지 못한 해시를 사용해서 특정 인덱스에 데이터가 몰리게 된다면 다른 곳은 텅텅 비어있는데 한 버킷에 저장된 리스트의 길이만 계속 길어지기 때문이다.
결국 내가 찾고자 하는 값이 리스트의 맨 마지막에 위치하고 있다면 링크드 리스트를 처음부터 끝까지 다 탐색해야하기 때문에 O(n)의 시간복잡도를 가지게 된다. 그렇기 때문에 최대한 저장하고 하는 데이터를 균일하게 퍼트려서 리스트의 길이를 어느 정도로 유지해주는 해시 함수의 역할이 중요한 것이다.
테이블 크기 재할당(Resizing)
해시 테이블은 고정적인 공간을 할당해서 많은 데이터를 담기 위한 자료구조인 만큼 언젠가 데이터가 넘치기 마련이다.
개방 주소법을 사용하는 경우에는 테이블이 실제로 꽉 차서 더이상 저장을 못하는 상황이 발생할 것이고, 분리 연결법을 사용하는 경우에는 테이블에 빈 공간이 적어지면서 충돌이 발생할 수록 각각의 버킷에 저장된 리스트가 점점 더 길어져서 리스트를 탐색하는 리소스가 너무 늘어난 상황이 발생할 것이다.
그렇기 때문에 해시 테이블은 꽉꽉 아낌없이 채우기보다는 어느 정도 비워져 있는 것이 성능 상 더 좋으며, 해시 테이블을 운용할 때는 어느 정도 데이터가 차면 테이블의 크기를 늘려줘야한다.
이건 특별한 알고리즘이라기보다는 그냥 기존 크기의 두 배 정도로 새로운 테이블을 선언해서 기존 테이블의 데이터를 그대로 옮겨 담는 방법을 사용한다. 분리 연결법을 사용한 해시 테이블의 경우 재해싱(Rehashing)을 통해 너무 길어진 리스트의 길이를 나누어서 다시 저장하는 방법을 사용하기도 한다.
https://evan-moon.github.io/2019/06/25/hashtable-with-js/