2024.12.20 해시테이블

해시 테이블(Hash Table)

1. 해시가 뭘까?

2024.12.17 포스팅의 1번 문제의 의문으로 인해 선생님이 해시테이블에 대해 알아보라고 했다.

처음에 해쉬라는 것을 들었을 때 맨 처음 떠올렸던 것은 해시브라운,,,, 아니면 인스타 해시테그 정도,,,,

 

어림도 없지. 

해시 함수 (짧게는 그냥 해시)는 임의의 길이를 갖는 임의의 데이터를 고정된 길이의 데이터로 매핑하는

단방향 함수를 말한다. 쉽게 말해, 아무리 큰 숫자를 넣더라도 정해진 크기의 숫자가 나오는 함수이다.

 

예를 들면 어떤 숫자를 10으로 나누었을 때 그 나머지를 구하는 함수도 해시 함수이다.

이러한 해싱(Hashing)의 과정에는, 해시 함수(Hash Function)와 해시 테이블(Hash Table)이 사용된다.

 

2. 해시테이블

위에서 설명한 해시를 사용한 자료구조를 말한다.

배열의 색인(Index)에 해시값을 사용하는 자료 구조로 정렬을 하지 않고도 빠른 검색, 빠른 삽입이 가능하다.

해시값이 충돌하는 경우가 발생하여 같은 색인이 만들어질 수도 있는데,

 

하나는 배열의 각각의 색인을 연결 리스트로 만들어서 새로 입력이 될 때마다 같은 해시를 가진다 하더라도 색인이 연결리스트로 구현되어 있기 때문에 원하는 데이터의 접근이 가능한 개별 체이닝(Separate Chaining)과 다음에 위치한 색인들 중 비어있는 곳에 넣는 방식인 오픈 어드레싱(Open Addressing) 등이 있다.

 

개별 체이닝(Separate Chaining)

해시테이블의 기본방식인 개별 체이닝은 충돌이 생기면 그림처럼 연결리스트로 연결하는 방식이다.

사과와 복숭아는 사과의 다음 아이템이 복숭아로 서로 연결 리스트로 연결되어있다.

 

 

 

오픈 어드레싱(Open Addressing)

오픈 어드레싱은 충돌이 발생하면 탐사를 통해 빈공간에 들어가는 방식이다.

그래서 무한하게 저장할 수 있는 체이닝 방식과 다르게 전체 슬롯 개수 이상은 저장할 수 없다.

빈공간을 찾아서 순차적으로 탐사하기 때문에 특정 위치가 선점되어 있으면 다음 위치를 확인하는 방식이다.

그래서 개별 체이닝 방식과 다르게 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장이 없다.

 

 

어쨋든 이렇게 충돌을 해결한다 해도 결과적으로 충돌로 인한 성능 저하를 막을 수는 없다.

수용률이 일정량을 넘어서게 되면 저장/조회 성능이 모두 점점 떨어지고 수용률이 일정량을 넘어가게되는 경우는

아예 리스트 자체의 크기를 키운 뒤에 재배열하는 방법을 사용한다.

 

 

아무튼 2024.12.17 포스팅의 1번 문제로 돌아가서 말하자면,

딕셔너리가 내부적으로 해시테이블을 사용하는 점을 고려하면... 궁금하면 500원!

https://www.fluentpython.com/extra/internals-of-sets-and-dicts/