[자료구조] 해시 테이블에 관하여

초안 : 2021년 1월 3일

1차 수정 : 2023년 4월 10일

 

해시테이블이란?

해시 테이블(Hash Table)은 키(Key)와 값(Value)으로 이루어진 데이터를 저장하기 위한 자료구조 중 하나입니다. 해시 테이블은 일반적으로 배열(Array)과 연결 리스트(Linked List)를 조합하여 구현됩니다.

 

해시 테이블의 핵심 아이디어는 키를 해시 함수(Hash Function)에 넣어서 고유한 해시 코드(Hash Code)를 생성하고, 이 해시 코드를 배열의 인덱스로 사용하여 값을 저장하는 것입니다. 이렇게 하면 키와 값 쌍을 빠르게 찾을 수 있습니다.

 

해시 테이블의 장점은 검색, 삽입, 삭제 등의 연산이 O(1)의 시간 복잡도로 수행된다는 것입니다. 하지만 해시 함수의 충돌이 발생할 경우 해결하는 방법이 필요합니다. 충돌이 발생하면 다른 인덱스에 값을 저장해야 하는데, 이 때 충돌을 해결하는 방법에 따라 해시 테이블의 성능이 달라집니다.

해시 테이블은 검색이 빈번하게 일어나는 경우, 대량의 데이터를 저장해야 하는 경우, 빠른 검색이 필요한 경우 등에 사용됩니다. 예를 들어, 전화번호부나 우편번호 검색 시스템 등에서 사용될 수 있습니다.

 

출처 : https://en.dict.naver.com/#/search?range=all&query=hash

 

 

해시란 데이터를 "잘게 부수고 다시 뭉쳐"(해시브라운 같이) 테이블내의 주소로 바꿔준다...

 

 

- 해시 테이블 : 데이터의 해시 값을 테이블 내의 주소로 이용하는 궁극의 탐색 알고리즘

 

- 암호화 : 해시는 입력받은 데이터를 완전히 새로운 모습으로 바꾼다! 해시를 통해 변환된 데이터는 원본의 모습을 알아볼 수 없을 정도로 완전히 달라진다.

 

- 데이터 축약 : 해시는 길이가 서로 다른 입력 데이터에 대해 일정한 길이의 출력을 만들수 있다.

 

 

 

해시테이블?

데이터를 담을 테이블을 미리 크게 확보해 놓은 후 입력받은 데이터를 해시하여 테이블 내의 주소를 계산, 이 주소에 데이터를 담는 것. 

 

 

해시테이블 클러스터 현상

삽입되는 데이터들이 고루 분포안되고 서로 모여져 있는 현상 

 

 

해시함수의 한계 : 충돌

해시 함수가 서로 다른 입력값에 대해 동일한 해시테이블 주소를 반환하는 것을 충동이라 한다.

 

 

해시테이블의 충돌을 해결하는 방법에는 크게 두가지로

 

1. 개방 해싱(Open Hashing) : 해시테이블의 주소 바깥에 새로운 공간을 할당

2. 폐쇠 해싱(Closed Hashing) ) : 처음 주어진 해시 테이블 공간에서 해결하려는 것 

 

체이닝 : 해시 함수가 서로 다른 키에 대해 같은 주소값을 반환해서 충돌이 발생하면, 각 데이터를 해당 주소에 있는 링크드 리스트에 삽입하여 문제해결 하는 기법.

 

출처 : https://coding6467.tistory.com/14

체이닝의 성능을 더 끌어내려면?? 연결 리스트말고 이진탐색트리조합도 좋음.