해시테이블
연관 배열이란?
연관 배열은 키를 사용해서 키-값의 쌍을 저장하는 데이터 타입이다.
해시 테이블이란?
연관 배열을 구현한 자료구조이다. 고유한 키를 사용해 키-값을 저장하는 선형자료구조이다. 해시테이블은 배열이나 인덱스처럼 순차적으로 접근하는 것이 아니라 키를 통해 값을 얻는 방식이다. 따라서 키는 고유해야한다.
해시함수를 통해 해시값을 반환받고, 해시값을 값을 저장하는 배열 인덱스로 사용한다.
해시테이블의 값은 어떤 타입이든 가능하지만, 키는 정수나 문자열처럼 해시함수가 인덱스로 변환할 수 있어야한다.
해시함수과 해시값
해시 함수는 데이터를 입력 받아, 해시값을 출력한다.
해시 값은 입력 데이터로부터 계산된다. 따라서 해시함수는 동일한 입력에 대해 항상 동일한 해시값을 반환한다.
해시값은 컴퓨터가 값을 저장하는 배열 인덱스로 사용된다.
입력데이터는 어떤 데이터 타입이든 저장할 수 없지만 키는 변하지 않는 문자열이나 정수만 가능하다.
🤔 해시값이 충돌된다면..?
입력데이터를 통해 해시 값을 생성한다. 그리고 이 해시 값을 인덱스로 활용한다.
그런데 서로 다른 입력에 대해서 동일한 해시값을 반환하면 어떻게 해야할까...?
해시 함수의 특징
단방향성
입력데이터에서 해시값의 반환은 쉽지만, 해시값으로 데이터를 유추하기는 불가능에 가깝다.
➡️ 데이터의 무결성보장 & 보안을 위해서
- 평가 지표 :
역상저항성- 어떤 해시 함수가 특정한 값을 출력하는 입력값을 찾기 어려움을 의미
해시 충돌
해시함수는 서로 다른 입력에 대해 동일한 해시값을 출력할 수 있고 이를 해시 충돌이하고 한다. 좋은 해시 함수는 충돌을 최소화해야한다.
- 평가 지표 :
충돌저항성- 해시 함수가 충돌하는 서로 다른 두 입력값을 찾기 어려움을 의미한다.
💡 제 2상 역상저항성 : 충돌 저항성과 역상 저항성이 복합적으로 작용한 경우로, a라는 입력의 해시값과 동일한 해시값을 갖는 입력 b를 찾기 어려워야 함을 나타냅니다.
고정된 결과값의 길이
해시 함수는 항상 일정한 길이의 결과값을 출력한다.
➡️ 데이터의 일관성과 효율적인 처리,무결성을 보장한다.
해시테이블의 성능
| 접근 | 탐색 | 삽입 | 삭제 | |
|---|---|---|---|---|
| 해시테이블 | N/A | O(1) | O(1) | O(1) |
각각의 키값이 해시함수에 의해 고유한 인덱스를 가지기 때문에 효율적으로 처리가 가능하다. 탐색, 삽입, 삭제에 평균적으로 O(1)의 성능을 따른다.
그러나 충돌이 발생하면 O(n)의 시간 복잡도를 가질 수 있다.
해시테이블은 n번째 요소에 접근하는 방법이 존재하지 않는다. 따라서 순서대로 조작하거나 접근해야하는 경우에는 배열이나 리스트가 더 적절할 수 있다.
자바의 해시테이블 보러가기
해시테이블이 적합한 상황
대량의 데이터가 있고 개별 데이터에 빠르게 접근해야할 때 해시테이블이 가장 효율적이다.
전화번호부나 영어사전을 만들 때 해시테이블을 고려할 수 있다.
파이썬의 딕셔너리
dic = { 1:"1", 2:"2", 3:"3"}
print(dic) #{1: '1', 2: '2', 3: '3'}
#값 추가
dic[4] = "4"
print(dic) #{1: '1', 2: '2', 3: '3', 4: '4'}
#값 삭제하기
del dic[4]
print(dic) #{1: '1', 2: '2', 3: '3'}
#값 접근하기
a = dic[3] #'3'
print(a)
#b = dic[4] 없는 키에 접근하면 KeyError: 4
print(dic.get(4)) #None
print(dic.get(4,"없어요!")) #없어요!
#해당 키가 딕셔너리 안에 있는지 조사하기
print(4 in dic) #False
print(3 in dic) #True
dic[3] = "삼"
print(dic) #{1: '1', 2: '2', 3: '삼'}
#dict_keys 객체 반환
print(dic.keys()) #dict_keys([1, 2, 3])
#dict_values
print(dic.values()) #dict_values(['1', '2', '삼'])
#dict_items
print(dic.items()) #dict_items([(1, '1'), (2, '2'), (3, '삼')])
#지우기
print(dic.clear()) #None해시테이블 활용문제
문자열 속의 문자
문자열에 들어 있는 문자의 수를 모두 세어보는 문제
def character_counting(a_string):
dic = {}
for i in a_string:
if i in dic:
dic[i] += 1
else:
dic[i] = 1
return dic
a_str = "Be Happy~!"
print(character_counting(a_str))
#{'B': 1, 'e': 1, ' ': 1, 'H': 1, 'a': 1, 'p': 2, 'y': 1, '~': 1, '!': 1}
두 수의 합
def two_sum_brute(a_list,target):
dic = {}
count = 0
for i, n in enumerate(a_list):
x = target - n
if x in dic :
count += 1
dic[n] = i
else:
dic[n] = i
return count
a_list = [1,2,3,4,5,6]
print(two_sum_brute(a_list,7)) #3
print(two_sum_brute(a_list,6)) #2
print(two_sum_brute(a_list,4)) #1
print(two_sum_brute(a_list,1)) #0