[해시] 해시의 개념과 예상 면접 질문

‡Computer Science ‡/º 자료구조

[해시] 해시의 개념과 예상 면접 질문

Trudy | 송연 2024. 6. 20. 19:55

해시(Hash)/해시 함수(Hash Function)/해싱(Hashing)

해시 (Hash)

데이터를 다루는 기법 중 하나

해시 함수 (Hash Function)

데이터를 효율적으로 관리하기 위해서 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수

ex) 나눗셉 법, 곱셈 법, SHA

해싱 (Hashing)

키 -> 해시값(Hash value)로 매핑되는 과정 자체

Hash Table

장점

배열의 인덱스를 사용해서 검색/삽입/삭제가 매우 빠름
O(1) - 충돌이 없다면
key와 해시값(hash)가 연관성이 없어 보안에 좋음
키에 대한 데이터가 있는지 (중복) 확인이 쉬움

단점

저장공간이 많이 필요한 편
여러 키에 대해 주소가 동일한 경우(충돌) 별도의 자료구조가 필요하다
충돌이 발생하면 Chaining에 연결된 리스트까지 모두 검색해야해서 O(N)까지 증가 가능

주요 용도

검색이 많이 필요할 때
저장/삭제/조회가 빈번한 경우
캐시 구현 (중복 확인이 쉽기 떄문에 자주 사용)

시간 복잡도

	평균	최악
탐색	O(1)	O(N)
삽입
삭제

✔️ Hash Table vs Hash Map

동기화 지원여부와 null 값 허용 여부의 차이
Hash Map: 자원의 동기화 x, 병렬처리 x, null값 허용
Hash Table: 자원의 동기화 o, 병렬 처리 o, null값 허용 x

예상 면접 질문

Hash Table은 단골 면접 질문

🌟 🌟 🌟 해시 테이블과 시간 복잡도에 대해 설명해주세요.
- 효율적인 탐색을 위한 자료구조
- key, value로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있다는 장점을 가진 자료구조
- 내부적으로 배열(버킷)을 사용해서 데이터 저장해서 빠름
- key 값은 해시함수에 의해 고유한 index를 가져서 바로 접근 가능
- O(1)
- index가 충돌하는 경우 Chaining에 연결된 리스트까지 검색해야해서 O(n)까지 증가할 수 있음
Hash Map과 Hash Table의 차이점은 무엇인가요
- 동기화 지원여부와 null 값 허용 여부의 차이
- Hash Map: 자원의 동기화 x, 병렬처리 x, null값 허용
- Hash Table: 자원의 동기화 o, 병렬 처리 o, null값 허용 x
해시 테이블의 시간복잡도과 공간 효율
- 저장/삭제/검색은 모두 기본적으로 O(1)의 시간 복잡도를 가져서 매우 빠른 편이지만, 충돌로 인한 최악의 경우 O(n)이 될 수 있다.
- 데이터가 저장되기 전에 미리 저장공간(slot, bucket)을 확보해야하므로 공간 효율성은 좋지 않다.
해시 함수란?
- 임의의 길이의 데이터 -> 고정 길이의 데이터 로 매핑하는 함수
- 골고루 분포 될 수 있게 해시 함수를 선택해야 함
좋은 해시 함수는?
- 연산 속도가 빠르고, 해시값이 최대한 고르게 분포되게 하는 함수
해시 테이블의 단점은?
- 배열에 저장하므로 공간 효율성이 좋지 않음
- 순서가 없음
해시 테이블 자료구조에서 발생할 수 있는 문제는?
- 서로 다른 데이터가 같은 해시값을 갖게 되는 충돌 문제
- 충돌 문제가 발생하면 O(1) -> O(n)으로 늘어나 해시 테이블 성능이 안좋아짐
🌟 🌟 🌟 🌟 해시 테이블에서 충돌이 발생하면 해결방법은 뭐가 있나요?
- 1. Open addressing
  - 미리 정한 규칙에 따라 비어있는 해시 테이블에 데이터를 저장
  - 장점) Chaining 방식보다 메모리를 적게 사용
  - 단점) 충돌 횟수가 많아지면 특정 영역에 데이터가 몰리는 클러스터링이 발생 가능
- 2. Seperate Chaining
  - Linked List를 활용해서 노드로 추가해서 저장
  - 장점) 구현이 간단, 테이블 확장을 늦출 수 있음
  - 단점) 조회 성능이 O(n)까지 나빠질 수 있음
Hash 충돌이 잦다면?
- 다른 자료구조 탐색
- 테이블이 75% 찼으면 테이블 확장
어떨 때 해시를 쓰고 어떨 때 트리를 쓸까?
- 빠른 삽입/삭제/검색이 필요하면 해시
- 자료가 정렬되어 있어야하거나, 범위 탐색이 필요하면 트리