[Python] 해시(Hash)란 무엇인가(feat. Dictionary 자료구조) | LIM

📚 해시함수

해시함수란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 이때 매핑 전 원래 데이터의 값을 키(key), 매핑 후의 데이터의 값을

해시값(hash value), 매핑하는 과정 자체를 해싱(hashing)이라고 한다. 

 

해시함수는 해쉬값의 개수보다 대개 많은 키값을 해쉬값으로 변환(many-to-one) 하기 때문에 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 해시충돌(collison)이 발생하게 된다. 

 

만약 A, B 두가지 key가 있다고 가정하자. A와 B를 hash function으로 해시값을 얻었는데 hash 값이 동일하게 3으로 나온경우 이런 현상을 해시충돌(hash collison)이라고 한다. 

 

해시함수로 해시를 만드는 과정에서 서로 다른 key가 같은 해시로 변경되면 같은 공간에 2개의

value가 저장되므로 key-value의 1:1 매핑이 성립되지 않게 된다. 해시 충돌은 필역적으로 나타날 수 밖에 없다. 중요한 것은 해시충돌이 해시값 전체에 걸쳐 균등하게 발생하게끔 하는 것이다. 

 

추후 해시 충돌에 대해서도 더 정리해보도록 하겠다. 

💡 해시테이블의 원리

해시함수를 사용하여 키를 해시값을 매핑하고, 이 해시값을 색인(index) 혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하는 자료구조를 해시테이블이라고 한다. 해쉬테이블의 기본적인 개념은

이렇다.

이름을 키로, 전화 번호를 저장하는 해쉬 테이블 구조를 만든다고 가정하자. 전체 데이터 양을 16명이라고 한다면 John Smith의 데이터를 저장할 때, hash_function("John Smith") % 16 을 통해서 index값을 구해내고, array[index] = "John Smith" 의 전화 번호 "521-8976"을 저장한다. 

 

출처: https://en.wikipedia.org/wiki/Hash_table

이런 형식으로 데이터를 저장하면, key에 대한 데이터를 찾을 때, hash_function을 한번만

수행하면 array 내에 저장된 index 위치를 찾아낼 수 있기 때문에 데이터의 저장과 삭제가 매우 빠르다. 

 

해시 테이블의 기본 연산은 삽입, 삭제 탐색이다. 이러한 해쉬 테이블은 충돌이 발생할 수 있는데 충돌이 발생하지 않는다고 가정했을 때,

 

탐색: 인덱스로 값을 탐색 O(1)

삽입: 해시 함수를 통해 인덱스가 정해짐 O(1)

삭제: 인덱스와 인덱스 안에 값만 지워주면 됨 O(1) (배열처럼 지워졌다고 순서를 다시 정리할 필요가 없다.)

 

따라서 풀스캔과 같은 선형탐색O(N) 보다 훨씬 빠르게 자료값을 찾는다고 볼 수 있다. 

 

📌 해시 테이블의 장점

1. 적은 리소스로 많은 데이터를 효율적으로 관리할 수 있다. 

2. 배열의 인덱스(index)를 사용해서 검색, 삽입, 삭제가 빠르다. (위에서 언급한 것처럼 평균 시간복잡도가 O(1) 이다.)

3. 키(key) 와 해시값(Hash)이 연관성이 없어 보안에도 많이 사용된다.

4. 중복을 제거하는데 유용하다.

 

📌 해시 테이블의 단점

1. 해시 충돌이 발생할 수 있다. 

• 해시 충돌이 발생하는 경우 평균 시간 복잡도가 최악의 경우 O(N) 이 된다.

2. 공간 복잡도가 커진다.

• 대신 시간복잡도가 줄어들었음

3. 순서가 있는 배열에는 어울리지 않는다. 

4. 해시 함수 의존도가 높아진다. 

 

📌 파이썬에서 hash table 의 활용 예 - Dictionary

파이썬의 딕셔너리가 해시테이블을 활용한 예이다. 파이썬 3.6 이후 버전부터는 딕셔너리도 순서

유지가 된다고 한다. 

딕셔너리는 키와 값 한 쌍이 하나의 대응 관계를 가지고 있는 자료형이다.

리스트 데이터 타입은 값들을 하나로 이어서 아루기 쉽게 하기 위해서 만들어졌다면, 딕셔너리는

데이터를 특정 key와 value 한쌍을 이루게 해서 순서와 상관없이 key를 이용해서 바로 value에 접근하게 하는 것

 

파이썬 딕셔너리 관련 함수들

1) in

• 딕셔너리에 해당 키가 있는 지

students = {'kim': 17, 'lee': 15, 'park': 18}
if 'kim' in students:
	print('kim is in students')
else:
	print('kim is not in students')

if 'son' in students:
	print('son is in students')
else:
	print('son is not in students')

>> 'kim' is in students
>> 'son' is not in students

 

2) keys

• 딕셔너리의 키 뽑기
  
  

students = {'kim': 17, 'lee': 15, 'park': 18}

# key 출력
print(students.keys())

# key 순서대로 출력
for student in students.keys():
	print(student)

>> dict_keys(['kim', 'lee', 'park'])

# 순서대로 출력
>> kim
>> lee
>> park

 

3) values

• 딕셔너리의 값 뽑기

students = {'kim': 17, 'lee': 15, 'park': 18}

# value 출력
print(students.values())

# value 순서대로 출력
for age in students.values():
	print(age)

dict_values([17, 15, 18])

# 순서대로 출력
>> 17
>> 15
>> 18

 

4) items

• 딕셔너리 키, 값 합쳐서 뽑기

students = {'kim': 17, 'lee': 15, 'park': 18}

print(students.items())

for student_info in students.items():
	print(student_info)

dict_items([('kim', 17), ('lee', 15), ('park', 18)])

# 순서대로 출력
>> ('kim', 17)
>> ('lee', 15)
>> ('park', 18)

 

5) get

• 딕셔너리 키로 값 얻기

students = {'kim': 17, 'lee': 15, 'park': 18}

# students 에 있는 키값
print(students.get('kim'))
>> 17

# students 에 없는 키값
print(students.get('son'))
>> None

 

6) del

• 딕셔너리에서 키, 값 한쌍 지우기

students = {'kim': 17, 'lee': 15, 'park': 18}

print(students)
>> {'kim': 17, 'lee': 15, 'park': 18}

del students['kim']
print(students)
>> {'lee': 15, 'park': 18}

del students['son']
>> error 발생

 

7) clear

• 딕셔너리 키, 값 모두 지우기

students = {'kim': 17, 'lee': 15, 'park': 18}

print(students)
>> {'kim': 17, 'lee': 15, 'park': 18}

students.clear()
print(students)
>> ""