[자료구조/Java] 해시

✔ 목차

1. 해시란?
2. 해시테이블
3. 해시충돌
4. 시간복잡도
5. java에서 해시
   
   

---

🔎 해시란?

• key와 value가 쌍을 이루는 자료구조

• 해시 함수를 통해 고정길이 key 생성

• 대표적인 해시 함수 종류
  1) bit extraction: 적절한 위치의 비트를 추출
  2) mid-square: 원소 제곱 후 적절한 위치의 비트를 추출
  3) division: h(x) = x mod m
  4) multiplication: h(x) = (xα mod 1) ⨯ m
  ⁕ m은 보통 테이블 사이즈, A는 0<α<1인 상수
  
  

---

🔎 해시테이블

• 해싱을 통한 원소들의 저장공간

• 해싱: 해시 함수를 통해 원소의 위치 계산

• 순차적으로 데이터 저장하지 않음

• 크기가 m인 해시테이블을 T[0 ... m-1]이라고 할 때 원소 x 에 대한 모든 값 h(x)은 {0, ... m-1} 중 하나

• 해시 테이블의 각 엔트리를 버킷이라 하고, 버킷에는 1개 이상의 슬롯으로 구성

• 원소는 하나의 슬롯에 저장

---

🔎 해시충돌

• 서로 다른 두 원소 x, y의 해시 값이 h(x) = h(y) 이면 충돌

• 해결방법
  1) chaining: 충돌이 일어나면 원소들을 연결리스트로 연결
  2) linear open addressing: 충돌이 일어나면 다음 빈 주소로 가서 저장
  3) rehashing: 여러 해시 함수 사용
  
  

---

⏰ 시간복잡도

해시는 key와 value가 1:1 매핑되어 있어 평균 시간복잡도는 O(1)이다.

연산
삽입	O(1)
삭제	O(1)
탐색	O(1)

---

💻 java에서 해시

자바에서 해시는 HashMap, HashSet 통해 자주 사용한다. 둘의 차이를 알아보자

1. HashMap

• Map 인터페이스 구현체
• key-value 형태로 저장
• 중복 key 값 허용하지 않음, 중복 value 값 허용

  java에서 HashMap 사용하기

2. HashSet

• Set 인터페이스 구현체
• 객체 그 자체 저장(객체가 key 값이 되고 value는 더미객체를 사용한다.)
• 중복 허용하지 않음
  • hashCode(), equal() 매서드를 이용하여 중복체크