해쉬 테이블(Hash Table)

1. 해쉬 구조

• Hash Table : 키(Key)에 데이터(Value)를 저장하는 데이터 구조
  • Key를 통해 바로 데이터를 읽을 수 있기 때문에 속도가 빠르다는 장점이 있습니다.
  • Python 의 딕셔너리(Dictionary) 타입이 Hash Table의 예

2. 용어

• 해쉬(Hash) : 임의 값을 고정 길이로 변환 하는 것
• 해쉬 테이블(Hash Table) : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
• 해싱 함수(Hashing Function) : Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
• 해쉬 값(Hash Value) : Key를 통해 해싱 함수로 연산해서, 해쉬 값을 얻어내서, 이를 기반으로 해당 Key에 대한 데이터 위치를 찾을 수 있게 해 줌

3. 해쉬 테이블의 장/단점

• 장점
  • 데이터 저장/읽기 속도가 빠르다
  • Key 데이터의 중복 체크가 빠르다
• 단점
  • 해쉬 충돌을 방지 또는 해결 할 마련이 있어야 한다.(Key 중복)

해쉬 테이블은 해쉬 함수를 통해 Key값을 고정 길이의 값으로 변환하여 그 index에 데이터를 넣게됩니다.

이로 인해서 불필요한 공간을 만들 필요가 없게 되는데 아래 예시를 통해서 자세히 알아 보도록 하겠습니다.

 

먼저, 해쉬 테이블 이라는 개념이 나오게 되었던 직접 주소 테이블(Direct Address Table)에 대해서 알아보겠습니다.

 

직접 주소 테이블 

입력받은 value가 바로 key가 되는 데이터 매핑 방식입니다.

Data를 5,8 를 넣는다고 한다면 아래와 같을 것이다.

index	0	0	0	0	0	5	0	0	8
value	0	0	0	0	0	5	0	0	8

직접 주소 테이블은 찾고자는 value가 어디에 있는지 바로 확인을 할 수 있기 때문에 활용이 편리하지만, 공간의 효율성이 좋지 않다. 여기에서는 가장 큰 값이 8이라서 7개의 불필요한 데이터(0)이 만들어졌지만 만악에 100이었다면 불필요한 데이터가 99개 가 만들어졌을테다. 이는 엄청난 메모리 공간의 비효율성을 가져올 것이다.

이러한 단점을 보완하기 위해 해쉬 테이블 개념이 만들어졌다.

 

해쉬 테이블

해싱 함수를 아래와 같이 만들었다.

const hash_function = (key) => {
    return key % 5;
};

console.log(hash_function(5)); // 0
console.log(hash_function(8)); // 3

console.log(hash_function(1)); // 1
console.log(hash_function(100)); // 0

데이터 5와8을 넣게 되면

index	0			3
value	5			8

데이터 1과 100을 넣게 되면

index	0	1
value	100	0

와 같이 들어갈 것이다.

 

100과 같이 큰 값을 넣더라도 99개의 불필요한 데이터를 만들 필요가 없다.

직접 주소 테이블에서의 불필요한 공간이 생기지 않는 것을 볼 수 있다.

하지만 해쉬 테이블에도 큰 단점이 있는데 그것은 '해쉬 충돌'이다.

위의 데이터에서 5와 100은 해시 값이 똑같이 0으로 똑같기 때문에 index에 value를 넣을 때 충돌이 발생한다.

해쉬 테이블에서는 이 충돌(Collision)이 최대한 발생하지 않도록 해 주는게 중요하다.

 

4. 해쉬 충돌 해결

• Chaining 기법
  • 해쉬 테이블의 저장공간 외의 공간을 활용하는 기법
  • 충돌이 일어나면, 링크드 리스트 자료 구조를 활용하여, 링크드 리스트로 데이터를 추가로 뒤에 연결시켜 저장하는 기법
• Linear Probing 기법
  • 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법
  • 충돌이 일어나면 해당 Hash Value의 다음 Value부터 맨 처음 나오는 빈공간에 저장하는 기법