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

이전 글 : )

[알고리즘] 그리디 알고리즘 ( 탐욕 알고리즘, Greedy Algorithm)

---

 해시 hash 

 

해시란 임의 값을 고정 길이로 변환하는 것을 말합니다.

 

 해시 테이블 hash table 

해시 테이블은 키(Key)에 데이터( Value)를 저장하는 데이터 구조입니다.

 

파이썬에서는 해시를 따로 구현할 필요가 없이 딕셔너리 타입 (Dictionary Type)을 사용하면 됩니다.

데이터 저장에는 순서가 없으며 Value값은 중복이 가능하지만 Key값은 중복될 수 없습니다.

이러한 해싱 자료구조는 key를 통해 바로 value를 받아올 수 있으므로, 속도가 획기적으로 빨라집니다.

대부분의 탐색은 O(1)의 시간 복잡도를 가지며 하나의 key에 값이 몰린 경우 O(n)을 최악의 경우로 가집니다.

 

https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%95%A8%EC%88%98

문자열(keys) 데이터는 해시 함수(hash function)를 거쳐 숫자로 변경됩니다. 변경된 값(해시화 된 값)을 배열(buchets)의 키로 삼아 value를 저장합니다. 따라서 데이터를 서칭 하는 과정에서 배열을 순차적으로 탐색할 필요 없이 해시 함수를 거쳐 생성된 해시 값으로 데이터를 빠르게 찾을 수 있습니다.

 

 

 예제 

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

# hash table 예제 (dictionaly)

def solution(participant, completion):
    answer = ''

    hashSum = 0
    nameDict = {}
    
    for name in participant:
        nameDict[hash(name)] = name
        hashSum += int(hash(name))
        
    for name in completion:
        hashSum -= int(hash(name))
        
    answer = nameDict[hashSum]
    return answer

python의 dictionaly를 이용해 해결한 문제입니다.

 

---

 

 

[알고리즘] 스택 (Stack)