해쉬 테이블(Hash Table)

2021. 1. 3. 23:52

Hash Table : 키(Key)에 값(Value)를 저장하는 데이터 구조.

" 키를 해쉬 함수에 넣어서 해시 주소를 얻고 그 주소에 저장되어 있는 값을 찾는다. "

만약 전화번호부가 있고, 'Song'에 대한 전화번호를 알고자 할 경우,

List에서는 for문을 이용하여 'Song'이 저장되어 있는 공간을 찾고, 그에 맞는 전화번호를 찾기 때문에 시간복잡도가 O(n)이다.

하지만 Dictionary에서는 'Song'이라는 key를 넣으면 그에 해당하는 주소값에 저장되어 있는 전화번호를 바로 찾기 때문에 시간복잡도가 O(1)이다. (Hash Funtion의 연산 시간 고려 x)

'해쉬 충돌'을 다루는 법은 밑 링크 참조

** 파이썬에서는 딕셔너리 타입을 사용하면 된다.

참조 링크

17. 해싱(hashing), 파이썬

해싱은 데이터를 아주 빠르게 '삽입'하거나 '가져올 때' 사용하는 기법입니다. 하지만, 최솟값이나 최댓값을 찾을 때(전체 자료를 검색해야할 때)는 효율이 떨어집니다. 김 빠지는 이야기를 하나

comdoc.tistory.com

파이썬과 컴퓨터 사이언스(자료구조): 대표적인 자료구조: 해쉬 테이블 - 잔재미코딩

연습4: 연습2의 Chaining 기법을 적용한 해쉬 테이블 코드에 키 생성 함수를 sha256 해쉬 알고리즘을 사용하도록 변경해보기 1. 해쉬 함수: key % 8 2. 해쉬 키 생성: hash(data)

www.fun-coding.org

Hash, Hashing, Hash Table(해시, 해싱 해시테이블) 자료구조의 이해

0_HJVxQPQ-eW0Exx7M.jpeg DATA들이 사용하기 쉽게 정리되어 있다. 자료구조는 도대체 무엇일까? 자료구조(Data-Structure)는 데이터들의 모임, 관계, 함수, 명령 등의 집합을 의미한다. 더 쉽게 표현하자면, 1)

velog.io