Hash 의 정의와 Java 의 Hash

이현우·2024년 5월 12일
Javahash자료구조
1

자료구조

목록 보기
1/1
post-thumbnail

다음 정의를 hash 라고 한다.

  1. Hash Function (또는 hash Algorithm)
    • 임의의 가변 길이 데이터를 받아 “전자 지문”을 만드는 함수
      (전자 지문이란 개체를 식별할 때 쓰는 unique한 특성을 가진 매개체)
    • 통상적으로 고정 길이 데이터를 리턴하나, 극소수 가변 길이 데이터를 리턴하는 함수도 존재함.
  2. Hash Value
    • 해시 함수의 리턴 값. unique 한 특성을 지니기 때문에, 전자지문의 역할을 한다.
  3. Hash Table
    • 자료구조의 일종. key-value 의 형태이며 key값으로 hashValue를 넣는다.

- wikipedia

자료구조의 시간복잡도

배열의 시간복잡도: O(n)

이진 트리 구조의 시간복잡도: 평균 O(log n), 최악 O(n)

B-tree 구조의 시간복잡도: O(log n)

Hash Table

해시테이블의 시간복잡도: O(1)

  • 시간복잡도에서 강점을 보임

  • Key 값을 해시 함수를 통해 해시값으로 변환한다.
  • 이 해시값을 주소값으로 사용하여 값을 저장한다.
  • 값을 탐색할 때, Key 의 해시값을 계산하여 바로 해당 주소로 접근한다.

Hash Function

특징

  • 가변 길이 데이터를 고정 길이의 데이터로 변환하는 함수
  • 같은 입력값에 대해 같은 출력값을 보장함.
  • 서로 다른 입력값에서 동일한 출력값이 나올 확률이 희박함.
  • 일방향성을 가짐: 출력값으로 입력값 또는 해시 함수를 알아내는 것은 불가능

예제

h(x) = x mod 13; (x / 13 의 나머지)

Hash Conclusion (해시 충돌)

해시 함수가 서로 다른 2개 이상의 입력값에 대해 같은 출력값을 내는 상황

ex) 해시 함수가 h(x) = x mod 13 (x를 13으로 나눈 나머지) 일 때,

h(x) = x mod 13
h(7) = 7;
h(20) = 7;

해시 충돌 해결: 체이닝(Chaining)

  • 해시테이블의 값에 해당하는 부분에 연결리스트의 주소값을 넣어 모든 값을 관리한다.
  • 원소를 검색할 때, 해당 연결리스트를 차례로 지나가며 탐색한다.

단점

  • 해시테이블의 장점인 시간복잡도가 빠르다는 점이 약화됨.
    최악의 경우 O(n) 까지 느려질 수 있다.

해시 충돌 해결: 개방 주소 방법 (open addressing)

  • 해시 충돌이 발생하면 테이블 중 비어있는 새로운 주소를 탐사한 후, 탐사한 주소에 충돌된 데이터를 입력함

개방 주소법 알고리즘: 선형 탐사법(Linear Probing)

  • 정해진 칸만큼 옆으로 이동해 탐사하는 방법

    단점 - 특정 해시 값의 주변이 모두 채워져 있는 일차 군집화(Primary Clustering) 문제에 취약함

개방 주소법 알고리즘: 제곱 탐사법(Quadratic Probing)

  • 선형 탐사법과 비교해 탐사하는 폭이 고정이 아닌 제곱으로 늘어나는 탐사법
    • 첫 번째 충돌시, 충돌 지점으로부터 1의 제곱 만큼
    • 두 분째 충돌시, 충돌 지점으로부터 2의 제곱 만큼
    • n^2

단점 - 선형 탐사법과 비교해 데이터는 고르게 분산되어 충돌 확률을 줄이지만, 같은 주소에 접근할 시 계속 충돌이 나는 문제는 여전히 존재함. 이 현상을 이차 군집화(Secondary Clustering) 라고 함.

개방 주소법 알고리즘: 이중 해싱(Double Hashing)

  • 해시 함수를 이중으로 사용하는 방법
  • 위의 선형 탐사법과 제곱 탐사법에 비해 충돌 확률이 적음

보편적인 해시 알고리즘 - Secure Hash Algorithm (SHA)

  • NSA(미국 국가안보국)에 의해 1993년 처음 개발된 해시 알고리즘
  • 종류:
  • 256의 뜻: 해싱을 하면 2^256개의 해시값을 출력함. → 동일 출력 값 나올 확률 희박.

Java 의 HashTable, HashMap

  • Java 의 HashTable 과 HashMap 을 알아보고 둘의 차이점에 대해서 알아본다.

Java - HashTable

  • Java Collection Framework의 가장 오래된 멤버 중 하나
  • 수학적인 해시 테이블 구조의 구현체

Java - HashTable 과 HashMap의 차이점

  • HashTable 과 HashMap은 구조적으로 거의 동일하나, 동기화 지원 여부에서 차이가 있다.
  • HashTable은 초기 컬렉션의 특징으로 동기화를 지원한다.
    • 거의 모든 메서드가 synchronized 키워드를 갖고 있다.
    • 해당 요소로 인해 해시 테이블은 성능 문제를 동반하기도 함
  • HashMap은 동기화를 지원하지 않는다.
    • 멀티 스레드 사용시, 자원이 동기화 되지 않을 수 있다.

다음 정리할 내용

  • 자바에서 해시맵의 종류 정리

출처

위키피디아

mdn web docs

codegym

profile
이현우
Back-End 개발자

0개의 댓글