해시테이블이란?

해시테이블은 키를 활용하여 값에 직접 접근 가능한 구조

• 해싱의 목적은 앞에서 배웠던 정렬알고리즘들과는 다르게 검색
  • 해싱의 장점 : 데이터 양에 영향을 덜 받으며 빠름(키를 통해 값을 검색)
• 파이썬 딕셔너리는 내부적으로 해시테이블 구조
  • 해시테이블은 검색 알고리즘 역할도 하고, 딕셔너리를 위한 자료구조 역할
• 주요 학습내용 : 해시 함수, 해시테이블, 해시 충돌, 해시를 활용했을 때의 성능
  • 해시(Hash)는 해시 함수를 통해 나온 값
  • 해시테이블은 키를 빠르게 저장 및 검색할 수 있는 테이블 형태의 자료구조
  • 해시 함수는 여러 키를 분할하기 위해 키를 해시값(정수값)으로 매칭
  • 해싱(Hashing)은 쉽게 말해서 다 흩뜨려놓고, 키와 매칭되는 값을 검색하는 과정

# case 1 - 딕셔너리로 활용되는 해시테이블을 확인

test_code = {2.5: 'A' ,'2.0': 'B', '1.0': 'C'}
print(test_code[2.5])
print(test_code['1.0'])
print(test_code['2.0'])

# case 2 - 리스트와 튜플을 활용해서 해시테이블을 확인
# 데이터는 튜플로 저장

test_code = [(2.5, 'A'), ('2.0', 'B'), ('1.0', 'C')]

def insert(item_list, key, value):
    item_list.append((key, value))

def search(item_list, key):
    for item in item_list:    # 데이터를 검색하려면 딕셔너리보다 오래 걸림(키,값 쌍이 없어서 개별 값으로 반복해서 검색하기 때문)
        if item[0] == key:
            return item[1]
    print('not matching')

print(search(test_code, '2.0'))
print(search(test_code, 2.5))
search(test_code, '2.5')

• 해시테이블에 대한 간단한 예시
  • 아래와 같이 키(aqua)와 값(#00FFFF)이 정렬되지 않은 형태로 있는 경우, 색상에 해당하는 코드를 찾는 상황
    • 이러한 경우, 반복문과 조건문을 활용한다면 선형시간 성능(O(n))을 나타냄
    • 색상이 알파벳 순서대로 이미 정렬되어있다면 이진검색을 할 수 있을 것이고, 로그시간 성능(O(log n))

# 수도코드

[("aqua", "#00FFFF"), ("beige", "#F5F5DC"), ("chartreuse", "#7FFF00")]

for i in range(0, len(dictionary)):
  1)알파벳순서대로 정렬되어있음
  2)알파벳찾기(예를 들어, "beige"를 찾아보겠다.)
  3)이진검색 알고리즘 활용
  4)로그시간 성능

• 파이썬의 딕셔너리는 자료구조의 해시테이블로 구현되어 있으므로, 딕셔너리를 활용하여 해시테이블 개념을 이해해보기

# 먼저 값이 없는 딕셔너리를 선언
dict = {}

# 값 추가
dict['a'] = 1
dict['b'] = 2
dict['c'] = 3
dict

• 위의 결과값은 {'키': 값} 쌍을 나타냄
• 해시테이블 dict의 값을 읽어오는데 사용되는 문자열이 "키"
• 해시테이블에 저장된 데이터(값)에 접근하려면 키를 알아야함

# 아래와 같이 키를 통해 값을 알 수 있다.
dict['c']

# 해시테이블에 반복문을 적용
for key in dict.keys():
  print(dict[key])

# (키,값) 쌍을 출력

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

해시함수