[자료구조] 해시, 해시맵
2022. 8. 6. 13:39ㆍ학습/CS
반응형
0. 해시가 나온 상황
배열의 경우 내부 인덱스를 통해서 자료의 검색을 한번에 함
- 장점: 빠른 검색
- 단점: 데이터의 삽입, 삭제 시 많은 데이터가 이동하게됨 (시간 소요!)
연결리스트는 해당 노드를 검색하기위해 순회 검색을 함
- 장점: 데이터의 삽입, 삭제 시 인근노드들의 참조 값만 수정하면 됨
- 단점: 느린 검색
이 과정에서 해쉬라는 데이터를 다루는 방법이 나오게 됨
1. 해시 원리
해시함수F(key) => HashCode => 배열의 index => index와 value가 한쌍으로 존재하게 됨
- key가 해시함수를 거쳐서 HashCode로 바뀌게되고
- HashCode가 배열의 크기에 맞는 Index 로 변환이 됨
- 해당 Index에 value를 할당하여 (key, value) 형태의 테이블을 형성하게 됨
- key 값이 크든 말든 동일한 HashCode를 만들어줌
- 데이터를 해시코드로 바꾸는 해시함수(해시알고리즘)는 개발자에 따라 다름
- HashCode는 무수한 수로 나올 수 있지만 배열의 크기는 한계가 있음
- 해시코드를 배열의 크기로 나누고 나머지를 Index로 사용함
- 그렇다면 같은 인덱스가 나올수 있겠지?
- 이를 해시충돌이라고함
해시충돌
- 이 충돌을 해결하는 방법은 두가지
- open addressing - 겹치면 비어있는 인근 인덱스로 넘기는 방법
- Separate Chaining - 해당 인덱스에서 링크드리스트로 엮음
- 데이터가 적은경우 open addressing 가 효율이 좋을것이라는게 예상될 것이고 실제로도 그렇다
2. 특징
빠른탐색
- 유일한 값을 통해서 원소에 접근하는데 유용하게 쓰임
- 대부분의 시간복잡도가 O(1)
- 알고리즘 풀이 시 원소를 넣거나 삭제, 찾는 일이 많을 때에는 해시를 사용하는 것이 좋음
추가적으로 키에 대한 데이터의 유무와 중복 확인이 쉬움
3. 활용 - 파이썬
파이썬에서는 Dictionary 라는 자료구조를 통해 해시를 제공합니다.
용도
- 검색이 많이 필요한 경우
- 저장, 삭제, 읽기가 빈번한 경우
- 캐쉬 구현 시 (중복확인이 쉽기 때문)
4. Etc
해시맵과 해시테이블의 차이?
두개 다 key, value를 가진 map 자료구조이다.
- 중복키에 대한 처리
- 해시 테이블은 키가 값은 같은 값을 두번 넣으면 초기값을 유지함
- 해시맵은 키가 값은 같은 값을 두번 넣으면 두번째 값으로 덮어버림
- Null값
- 해시맵은 키에 Null값을 허용한다.
맵
- key 와 Value를 갖는 자료구조이다.
- 효율적인 검색을 위해서 사용된다.
참조
- 해시 전반적인 내용
- 해시맵과 해시 테이블의 차이, 해시 충돌
반응형