반응형
Hash table은 무엇인가요?
해시테이블은 효율적인 탐색(빠른 탐색)을 위한 자료구조로 키-값 쌍의 데이터를 입력받습니다.
hash function h에 key값을 입력으로 넣어 h(k)를 위치로 지정하여 키-값 쌍을 저장합니다.
저장, 삭제, 검색의 시간복잡도는 모두 O(1)입니다.
좀 더 자세히 알아볼까요~
Direct-address Table을 먼저 알아봅시다.
직접 주소화 테이블이란? 키를 인덱스로 설정하여 저장하는 방식입니다.
직접 주소화 테이블의 단점은 키에 따라 빈공간이 생기고 공간을 낭비하게 됩니다.
또한 인덱스에 다양한 자료형의 키를 저장할 수 없습니다.
이러한 단점들을 보완하기 위해 해시 테이블을 사용합니다.
해시 테이블
해시 테이블은 hash function h를 이용, (키, 값)을 인덱스:h(k)에 저장합니다.
이 때, “키 k값을 갖는 원소가 위치 h(k)에 hash된다.”, “h(k)는 키 k의 해시값이다” 라고 표현합니다.
여기서 전제 조건은 '키는 무조건 존재'해야하며, '중복되는 키가 없어야' 합니다.
이러한 (키, 값)데이터를 저장하는 공간을, slot(row와 유사) 또는 bucket이라고 합니다.
낭비되는 공간을 최소화할 수 있고, 다양한 자료형의 키를 사용할 수 있습니다.(hash function의 알고리즘을 통해)
Collision(충돌)
collision이란 서로 다른 키의 해시값이 똑같을 때, 서로 동일한 인덱스를 부여받게 되어 충돌이 발생합니다.
이러한 충돌을 방지하기 위해서는 'seperate chaining' 또는 'open addressing' 방법을 사용해야합니다.
반응형
'나는 이렇게 학습한다 > Algorithm & SQL' 카테고리의 다른 글
Data Reverse (0) | 2022.03.21 |
---|---|
Persistent Bugger (0) | 2022.03.20 |
자료구조 _ Queue 그리고 Stack (0) | 2022.03.20 |
Multiplication table (0) | 2022.03.19 |
Primorial Of a Number (0) | 2022.03.18 |