4. 해시 (Hash)

1.  해시란?

만약, 우리가 배열이나 리스트에서 특정 데이터("A")를 찾는다고 가정해보자.

• List: 0번부터 끝까지 하나씩 탐색해야 한다.
  • 데이터가 100만개라면 100만번 확인이 필요하다. (O(N))
  • 코딩테스트에서는 N이 크면 무조건 시간 초과다.
• Hash: "A"라는 이름만 주면, 단 한 번의 계산으로 데이터가 있는 곳을 바로 찾는다.
  • 데이터가 10억개여도 단 1번 확인이다. (O(1))

 

2. 해시의 작동원리

1. Key : "Apple"라는 데이터를 저장하고싶다면
2. Hash Fucntion (해시 함수) : "Apple"를 넣으면 알 수 없는 숫자(해시 코드)로 변경한다.
   • 예시 : "Apple" → hash_func() → 352
   • 이 352를 배열의 크기로 나눈 나머지를 인덱스로 사용한다. (만약 배열의 크기가 100이라면 352 % 100 = 52)
3. Bucket (저장) : 배열의 52번 인덱스에 데이터를 저장한다.

이제 찾을 때 동일하게 "Apple"이라는 값을 해시 함수로 태우면 인덱스 52가 바로 나오기때문에 순회가 필요 없이 직접적으로 찾을 수 있다.

 

만약 인덱스의 충돌이 일어난다면?

"Banana"를 넣었는데 우연히 계산 결과가 "Apple"과 동일하게 52로 나온다면?

→ Java는 52번 방에 연결 리스트(LinkedList)를 달아서 줄줄이 연결시켜 놓는다.

 

 

3. 해시맵(HashMap)

• 특징 : Key는 중복될 수 없지만 Value는 중복이 가능하다. (해시맵은 순서개념이 없다.)
• 용도 : ID로 회원 정보 찾기, 투표 수 집계 등

 

3.1. 메서드

메서드	설명	시간 복잡도	비고
put(K, V)	데이터를 저장한다.	O(1)	Key 값이 같다면 덮어씌워진다.
get(K)	데이터는 키 값으로 꺼낸다.	O(1)	없다면 null
containsKey(K)	키 존재의 여부를 확인한다.	O(1)	List의 contains보다 100만 배 빠르다.
remove(K)	삭제	O(1)
getOrDefault(K, def)	키가 없으면 기본값을 반환한다.	O(1)	빈도수를 셀 때 필수 메서드

 

---

 

4. 해시셋(HashSet)

• 특징 : HashMap에서 Value를 버리고 Key만 남긴 형태라고 보면 된다. 중복 제거가 핵심이다.
• 용도 : 로또 번호 생성(중복 방지), 방문했던 좌표 체크, 서로 다른 종류의 개수 세기 등

 

4.1. 메서드

메서드	설명	시간 복잡도	비고
add(E)	데이터를 추가한다.	O(1)	중복이면 false를 반환한다.
contains(E)	값 존재 여부를 확인한다.	O(1)	검색 속도 최강자
remove(E)	데이터를 삭제한다.	O(1)
size()	데이터의 개수를 조회한다.	O(1)	중복 제외된 개수