[Python] 알고리즘 : 해시 테이블(Hash Table)

🔹 해시테이블이란?

• key-value 로 이루어진 자료 구조
• 내부적으로 배열을 사용하여 데이터를 저장하며 입력 키 값으로부터 얻은 해시값을 인덱스로 사용하기 때문에,
  데이터를 빠른 속도로 검색하거나 처리한다.
• 평균 시간복잡도 : O(1)

🔹 해시란?

• 해시 : 해시 함수 또는 해시 알고리즘(임의 길이의 데이터를 고정된 길이의 데이터로 매핑)에 의해 얻어지는 값(위키백과)
• 해시 충돌 : 해시 함수가 서로 다른 두 입력값에 대해 동일한 출력을 만듦.
  즉, 두 개 이상의 다른 KEY가 동일한 인덱스로 매핑될 경우 해시 충돌이 발생, 해시 테이블의 성능을 저하
• 방지하기 위한 해시충돌 알고리즘이 있다.

 

🔹 파이썬에서의 구현

파이썬에서는 key-value의 형태로 이루어진 dictionary 자료 구조가 해시 테이블

key를 인덱스로 활용하여 value 값을 얻을 수 있다.

 

 

1) 검색

파이썬에서 인덱스를 통해 원소에 접근할 때,

리스트형은 숫자만을 이용해 원소에 접근 가능.

아래 예의 경우 a['1']로 접근하면, 에러 발생 (TypeError: list indices must be integers or slices, not str)

a = [1,2,3,4]
print(a[1])

>>1

 

딕셔너리형은 문자열과 같은 특정 입력값을 인덱스로 사용할 수 있다

 

a = {'1':1,'2':2,1:3}

print(a['1'])
print(a[1])

>> 1

>> 3

 

아래와 같이 딕셔너리 생성 후, Apple 요소의 값을 확인

dict = {'Apple':1000,'Bacon':1200,'Carrot':800}
print(dict['Apple'])

 

>> 1000

 

 

2) 중복 key -> 무시❗

 

중복된 key 값이 들어오면, 마지막으로 입력된 value값만 남는다.

dict = {'Apple':1000,'Bacon':1200,'Carrot':800}
print(dict)
dict = {'Apple':1000,'Bacon':1200,'Carrot':800,'Apple':3000}
print(dict['Apple'])
print(dict)

>> {'Apple': 1000, 'Bacon': 1200, 'Carrot': 800}

>> 3000

>>{'Apple': 3000, 'Bacon': 1200, 'Carrot': 800}

 

3) 예제 문제

https://programmers.co.kr/learn/courses/30/lessons/42576

코딩테스트 연습 - 완주하지 못한 선수

이 문제는 동일한 key값이 입력으로 발생한다.

요소의 입력 순서를 요하지 않기 때문에, 두 입력 데이터(리스트)의 값을 비교하여 풀 수 있다.

collections의 Counter 함수를 활용하거나, 나의 경우 itertools의 zip_longest 함수를 활용해 풀었다.