자료구조 해시
목차
- 해시
- 해시 함수
- 해시 테이블
1. 해시
: 데이터를 효율적으로 관리하기 위해 임의의 길이 데이터를 고정된 길이의 데이터로 매핑
해시 함수에 의해 얻어지는 값을 해시코드, 해시라고 함
2. 해시 함수
: key를 고정된 길이의 hash로 변경해주는 역할을 하여 이 과정을 hashing라고 함
해시충돌 : 서로 다른 key가 hashing 후 같은 hash값이 나오는 경우(발생확률이 적을수록 좋음)
+ 균등하게 발생하도록 하는 것도 중요함(모든 키가 같은 해시값이 나오게 되면 데이터 저장시 비효율성도 커지고 보안이 취약해져서 좋지 않음)- 좋은 해시함수의 조건
- 특정 값에 치우치지 않고 해시값을 고르게 만들어내는 해시함수가 좋은 해시함수
- 충돌이 적어야함
- 해시함수 값이 해시테이블의 주소 영역 내에서 고르게 분포되어야 함
- 계산이 빨라야 함
3. 해시 테이블
: 해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인(인덱스) 또는 주소삼아 데이터를 key와 함께 저장하는 자료구조(= key-value로 이루어진 자료구조)
해시 테이블의 구성
- Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐
(특정 조건에 맞춰 배열을 모두 순회할 필요가 없다는 소리) - 파이썬 딕셔너리(Dictionary) 타입이 해쉬 테이블의 예: Key를 가지고 바로 데이터(Value)를 꺼낼 수 있음
- 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법)
- 해쉬 테이블의 길이(슬롯의 개수)를 늘리는 방법
- 단, 파이썬에서는 해쉬를 별도로 구현할 이유가 없음 (딕셔너리 타입 { ‘key’: ‘value’ } 을 제공하기 때문)
- JS 또한 별도로 구현할 필요가 없다 (객체 타입 { key: ‘value’ } 을 제공하기 때문)
- Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐
해시 테이블의 장단점
장점
- 데이터 저장/읽기 속도가 빠름 (검색 속도가 빠름)
- 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움
- 해쉬는 키를 바탕으로 한 데이터의 여부(유무)를 파악하기 쉬움
단점
- 일반적으로 저장공간이 좀 더 많이 필요
- 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요
- 해시 함수를 통해 나눠져 저장되는 해쉬 테이블의 주소가 같은데, 별도의 처리를 하지 않을 경우 : 키를 바탕으로 한 데이터가 덮어씌워질 가능성이 있음
- 중복이 일어나지 않도록 해쉬 테이블의 공간을 넓게 설계해야 함
주요 용도
- 검색이 많이 필요한 경우
- 저장, 삭제, 읽기가 빈번한 경우
- 캐쉬 구현시 (중복 확인이 쉽기 때문)
출처