[n531] 해쉬 테이블

해시 테이블이란 무엇인가

• 해시 테이블 : 키를 이용하여 데이터 값에 접근이 가능한 구조를 의미한다. 
• 해시 함수 : 키에 따라 특정 해시값이 나올 수 있도록 매칭하는 함수이다.
• 해시 : 이 해시 함수에 키를 넣었을 때 나오는 값이다.
• 해싱 : 검색을 하기 위해 어떤 자료 구조를 해시화 한다. 
• 해싱을 하면 키를 통해 값을 검색하기 때문에 데이터 양이 많아도 성능이 빠르다. 
• 예를 들어, 파이썬의 딕셔너리는 해시테이블 개념을 바탕으로 구현되어 있다. 
• 해시 테이블은 시간 복잡도가 O(1)로, 하나의 키를 통해 하나의 값이 한번에 나오기 때문에 검색/삽입/삭제가 유용하다.

중간에 해시 함수를 통해 키와 값이 서로 매칭되는 것을 확인할 수 있다. 즉, 동일한 입력값에 동일한 출력값을 매번 출력해야 한다. 

for key in dict.keys():
  print(dict[key])

for key, value in dict.items():
  print('(키',key,':','값',value,')')

 

 

해시 충돌

해시가 들어가는 공간이 작은 경우 충돌이 일어날 수 있다. 

 

충돌 방지 방법 (1). Chaining

아래의 경우, John Smith와 Sandra Dee를 넣었을 때 충돌이 일어난다. 이 충돌을 방지하기 위해, 연결 리스트를 활용하여 John Smith의 엔트리와 Sandra Dee의 엔트리를 연결한다. 즉, 키와 해시값을 계산을 했을 때 같은 해시값이 존재한다면 충돌이 일어나므로 리스트로 연결한다. 

 

충돌 방지 방법 (2). Open Addressing

비어 있는 공간을 발견할 때까지 계속해서 배열 위치를 검색함으로서 충돌을 미리 방지한다. 

 

참고할 내용

[자료구조] 해시 테이블 (Hash Table)

 

본 컨텐츠는 코드 스테이츠 AI 부트캠프 렉쳐 노트를 참고 하였습니다.