[자료구조] Hash

참고 pangtrue.tistory.com/291

해시(Hash)

임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑하는 함수

 

해싱(Hashing)

매핑하는 과정

- 매핑 전 입력 데이터 값: Key

- 매핑 후 출력 데이터 값: HashCode

 

해시 특징

- 동일한 입력값에는 항상 동일한 출력 값 보장

- 출력 데이터 값으로 원본 입력 데이터 값을 알아낼 수 없음

- CPU, 메모리 자원 소비가 낮음

- 충돌: 입력 값의 범위보다 출력값의 범위가 좁음 -> 입력 데이터에 대해 동일한 출력값이 나올 수 있음

- 검색이 빠름: 해싱을 통해 만든 해시코드를 내부적으로 배열의 인덱스로 활용해시(Hash)

임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑하는 함수

 

해싱(Hashing)

매핑하는 과정

- 매핑 전 입력 데이터 값: Key

- 매핑 후 출력 데이터 값: HashCode

 

해시 특징

- 동일한 입력값에는 항상 동일한 출력 값 보장

- 출력 데이터 값으로 원본 입력 데이터 값을 알아낼 수 없음

- CPU, 메모리 자원 소비가 낮음

- 충돌: 입력 값의 범위보다 출력값의 범위가 좁음 -> 입력 데이터에 대해 동일한 출력값이 나올 수 있음

충돌 방지 및 회피

- 해시코드를 배열의 인덱스로 활용 할 때, 충돌로 인해 인덱스가 겹치는 현상 발생

- 해당 버킷에 데이터가 있다면, 다음 노드를 가리키는 연결리스트로 구현

- 검색이 빠름

  why?

  ▶ 해싱을 통해 만든 해시코드를 내부적으로 배열의 인덱스로 활용

  ▶ 별도의 정렬을 거치지 않고 데이터 인덱스를 해싱해 바로 추출

- 해시코드를 인덱스로 활용: 자료 분산, 기준 정렬 어려움

 

 

해시셋(HashSet)

데이터의 중복을 허용하지 않는 자료구조

이미 데이터가 추가되어 있는지를 검사할 때 주로 사용

저장된 데이터가 해싱되어 나온 해시코드를 인덱스로 활용하여 배열에 할당 ▶ 순서 파악 불가능

- Java 작동 과정

> 저장하는 요소의 GetHashCode() 메서드가 반환하는 해시코드와 배열(해시 버킷)의 크기를 나눈 나머지 값을 배열의 인덱스로 활용

> 저장하는 요소의 Equals() 메서드를 이용해 중복 여부 검사

> 해시버킷의 동적 확장(Resize)

  - 저장된 데이터 갯수 > 버킷의 길이 * 1.25

  - 기존의 모든 데이터에 대해 해싱을 새로해서 나온 위치값에 할당해야 함

    Why? 인덱스를 구하는 과정: 해시코드 % 버킷의 길이