[자료구조] 해쉬 테이블

 

💡해쉬 테이블(Hash Table)

- 해쉬 테이블은 키에 데이터를 저정하는 데이터 구조입니다.

- 나열의 구조인 stack이나 queue와 다르게 key를 통해 바로 데이터를 받아올 수 있습니다.

- 각 키는 해쉬 함수를 사용하여 고유한 해쉬 값으로 변환됩니다. 이 해쉬 값은 배열의 인덱스로 사용되어 해당 키와 연관된 값을 저장하거나 검색하는데 사용됩니다.

 

 

 

해쉬 테이블의 특징

장점

• 빠른 검색 속도 : 해시 함수를 사용하여 데이터를 매우 빠르게 검색할 수 있습니다. 해시 함수를 사용하면 키에 대한 값을 바로 찾아낼 수 있으므로, 대량의 데이터에 대한 검색 성능이 매우 우수합니다.
• 키 - 값 쌍 저장 : 해시 테이블은 키-값 쌍을 저장하기 때문에, 데이터를 효율적으로 검색할 수 있습니다. 키를 기준으로 값을 검색하므로, 값이 어디에 저장되어 있는지 쉽게 알 수 있습니다.
• 메모리 절약 : 해시 테이블은 인덱스를 사용하여 값을 저장하기 때문에, 메모리를 효율적으로 사용할 수 있습니다. 인덱스를 사용하면 데이터를 저장할 때 일정한 크기의 메모리 블록을 할당할 필요가 없습니다.

단점

• 해시 충돌 : 해시 함수가 서로 다른 두 개의 키를 같은 해시 값으로 변환할 수 있는 경우, 해시 충돌이 발생합니다. 충돌이 발생하면 검색 성능이 저하되서 이를 해결하기 위해서는 충돌 해결 기법을 사용해야 합니다.
• 해시 함수 선택 : 해시 함수는 충돌을 최소화하기 위해 신중하게 선택해야 합니다. 잘못된 해시 함수를 선택하면 충돌이 더 많이 발생하여 검색 성능이 저하될 수 있습니다.

 

 

해쉬 충돌과 리해싱

 

해쉬 충돌이란?

-해쉬 충돌(hash colision)은 키가 들어갈 자리가 없는 경우에 발생하는 개념입니다.

위와 같이 B와 C라는 키 값이 해시 함수를 통과하면 값은 해쉬 값을 받게되서 해쉬 충돌이 일어납니다. 또한 데이터가 많은데 공간은 제약 되어 있다면 충돌이 일어날 수 밖에 없는 상황이 만들어 집니다.

 

예를 들어, 데이터가 100개가 있고 공간이 90개까지밖에 없다면 해쉬테이블의 원리상 무조건 충돌이 일어날 수 밖에 없습니다. 더 많은 공간을 사용하면 좋지만 메모리가 한정되어있어서 그렇지 못할경우가 더 많이 있습니다. 

 

알고리즘을 설계할 때 충돌을 어떻게 최소화할 수 있는지, 어떤 방식으로 처리할지 생각을 하고 설계를 해야합니다.

 

 

Chaining 기법

- Chaining 기법은 해쉬 테이블 저장공간 외의 공간을 활용하는 기법입니다.

- 충돌이 일어나면, Linked List로 데이터를 뒤에 추가로 연결시켜서 저장하는 방법입니다.

- 모든 값을 넣을 수 있는 장점이 있는 반면에 데이터가 많은 경우 한 공간에 많은 데이터가 저장되므로 검색의 입장에선 좋지 않은 부분도 있습니다.

 

 

 

Open Addressing 기법

 

 

- 오픈 어드레싱 방법은 충돌 발생 시 테이블 공간을 탐색해 빈 공간을 찾아가는 방식입니다.

- 체이닝 방식은 버킷의 크기에 관계없이 연결리스트에 데이터를 줄줄이 달아놓음으로써 무한정 저장할 수 있는 반면, 오픈 어드레싱 방식은 전체 테이블 내 슬롯 개수 이상은 저장이 불가능하다.

- 이 방식은 충돌이 일어나면 다른 테이블 공간을 탐사해 빈 공간을 찾고 거기에 데이터를 집어넣음으로써 해결한다. 물론 이때 넣는 위치의 인덱스는 원래 key를 해시 함수에 넣어 얻은 인덱스와 다르다. 따라서 개별 체이닝과 달리 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장이 없다.

- 오픈 어드레싱은 해쉬 테이블에 저장되는 데이터들이 고르게 분포되지 않는 클러스터링의 문제를 갖고 있습니다. 클러스터링이 생기면 탐색 시간이 오래걸려 효율이 떨어집니다.

- 오픈 어드레싱은 무조건 빈 버킷에 데이터를 하나씩만 삽입하는 방식이기 때문이다. 따라서 기준이 되는 로드 팩터 비율을 넘어서면 정해놓은 비율에 따라 더 큰 크기의 또 다른 버킷을 생성한 뒤 새 버킷에 복사하는 리해싱(Rehashing) 작업이 일어난다.

 

 

 

 

 

 

📖 Reference

- 파이썬과 자료구조(해쉬 테이블) : https://velog.io/@2seunghye/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EA%B3%BC-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%ED%95%B4%EC%89%AC-%ED%85%8C%EC%9D%B4%EB%B8%94

 

- HashTable 충돌 : https://seong6496.tistory.com/371