해쉬
Key , Value 로 구성됨. 파이썬은 딕셔너리로 구성되어 있음.
하나의 Key에는 하나의 Value 할당
1) 원하는 크기의 배열을 생성한다.
2) 해시 함수를 이용해 저장할 key:value 데이터의 키를 배열 index 범위의 자연수로 변환
(파이썬 내부함수의 해시함수는 특정 범위가 아닌 아무런 정수로만 변경한다.)
3) 리턴한 배열의 index에 key:value 데이터 저장
해시 함수를 이용해 저장할 key:value 데이터의 키를 배열 index 범위의 자연수로 변환
# 1. 배열로 hashTable 생성.
hash_table = [0 for i in range(10)]
# 2. hashFunc(key) -> hashTableIndex
def hash_func(key):
hashValue=ord(key) # 여기서는 ord()가 hashFunc
hashAdress = hashValue%10 # 여기서는 나머지연산이 addressFunc
return hashAdress
# 3. 저장기능 , 읽기기능 구현
def save_data(key,value):
idx=hash_func(key)
hash_table[idx]=value
def read_data(key):
idx = hash_func(key)
return hash_table[idx]
Python
복사
•
장점
1) 데이터 저장/읽기 속도가 빠르다. (검색 속도가 빠르다.)
2) 키에 대한 데이터가 있는지(중복) 확인이 쉬움
•
단점
1) 일반적으로 저장공간이 좀 더 많이 필요하다.
2) 데이터 공간이 좁으면 여러 키에 해당하는 주소가 동일하여 충돌이 발생 할 수 있음. 이를 해결하기 위한 별도 자료구조가 필요함.
•
주요 용도
1) 검색이 많이 필요한 경우
2) 저장, 삭제, 읽기가 빈번한 경우
3) 캐쉬 구현시 (중복 확인이 쉽기 때문)
•
충돌 해결 방법
1) Open hashing(개방 해시)
충돌이 발생한 데이터에 대해서는 해시테이블 밖에 추가적인 데이터공간에 저장하는 방법이다.
ex) Channing 기법 : 충돌이 일어나면 linked list를 이용해서 뒤에 연결시켜 저장한다. 이 때 충돌 횟수를 모르기 때문에, 크기가 정해져 있는 array가 아니라 list를 이용한다.
2) Linear Probing(폐쇄 해시)
해시 테이블의 빈 공간에 저장하는 방법이다. hash address의 다음부터 맨 처음 나오는 빈공간에 저장 하기 때문에, 공간을 아낄 수 있다.
•
해당 문제
완주하지 못한 선수
SW Expert Academy Hash
프로그래머스 - 신고 결과 받기 (난이도 : 하)
프로그래머스 - 위장 (난이도 :중)
프로그래머스 - 베스트앨범 (난이도 :상)
