Hash Tables

Hash Tables

• Key-Value System : 특정한 값(Value)을 찾고자 할 때 그 값의 키(Key)로 접근할 수 있다.
• 데이터를 최대한 빠른 속도로 관리하도록 도와주는 자료구조
• 해시를 사용하면 메모리 공간이 많이 소모되지만 매우 빠른 속도로 데이터를 처리할 수 있다.

 

Hash Tables vs Arrays

예를 들어 특정 메뉴의 가격을 검색한다고 했을 때,

Array의 경우

menu = [
    { name: 'coffee', price: 10 },
    { name: 'burger', price: 15 },
    { name: 'tea', price: 5 },
    { name: 'pizza', price: 10 },
];

// loop를 돌면서 name == 'pizza'를 찾는다.
for()

• 선형검색(Linear Search)으로 원하는 값을 찾을 수 있다.
• 각각 아이템을 첫번째부터 끝까지 검색하는 방법
• *시간 복잡도 : O(N) *
  • 아이템이 많을 수록 찾는 시간도 오래 걸린다.

 

Hash table의 경우

menu = {
    coffee: 10,
    burger: 15,
    tea: 5,
    pizza: 10
};

// pizza
menu['pizza']

• 시간 복잡도 : O(1), 상수시간
  • 만약 Hash Collisions(해시충돌)이 일어난다면 선형검색도 같이 하게 되므로 언제나 상수시간 시간복잡도는 아니다.
• Hash Tables에서 어떤 값을 찾더라도 단 1개의 스텝만 소요된다.
• 아이템을 추가하거나 삭제할 때도 O(1)의 시간 복잡도를 가진다.

 

Hash Function

입력값이 같을 때 언제나 unique한 출력값을 만드는 함수

• Hash Function이 저장하려는 Key를 '특정한 값'로 바꾼다.
• 일반적으로 해시함수는 수학적 연산으로 이루어져 있으므로 O(1) 만에 값에 접근할 수 있다.

 

Hash Collisions

• 해시함수의 입력 값으로는 어떠한 값든 모두 들어갈 수 있지만, 해시 함수를 거쳐 생성되는 키(Key)의 경우의 수는 한정적이기 때문에 키(Key) 중복이 발생할 수 있다.
• 해시 테이블에서 키(Key)가 중복되는 경우 충돌(Collision)이 발생했다고 표현한다.

 

충돌을 처리하는 방법

1. 충돌을 발생시키는 항목을 해시 테이블의 다른 위치에 저장

선형 조사법

순차적으로 하나씩 확인하는 방식

• Index 5의 공간에 이미 값이 있다면, 다음 Index를 확인하여 비어있다면 값을 넣어준다.
• 단점 : 선형 조사법은 충돌이 발생하기 시작하면, 유사한 값을 가지는 데이터끼리 서로 밀집되는 집중 결합 문제가 존재한다.

 

이차 조사법

선형 조사법을 약간 변형한 형태로 키 값을 선택할 때 '완전 제곱수'를 더해 나가는 방식

• 데이터가 밀집되는 현상을 줄일 수 있기 때문에 해시 충돌이 적게 발생한다.
• 선형 조사법과 이차 조사법은 테이블이 가득 차게 되면 테이블의 크기를 확장 해줘야한다.

 

2. 해시 테이블의 하나의 버킷(Bucket)에 여러 개의 항목을 저장

체이닝(Chaining) 기법

연결 리스트를 활용해 특정한 키를 가지는 항목들을 연결하여 저장

• 연결 리스트를 사용한다는 점에서 삽입과 삭제가 용이하다.
• 테이블 크기 재설정 문제는 '동적할당'을 통해 손쉽게 해결할 수 있다. 다만, 동적할당을 위한 추가적인 메모리 공간이 소모된다는 단점이 있다.

• Index 5의 공간에 동적할당이 이루어진다면, 그곳에서 선형검색을 하게 된다.
• 이러한 이유로 Hash Tables의 시간 복잡도는 항상 상수시간일 수는 없다.