[알고리즘] 해시 (Java)

01 . 개념

해시는 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료 구조이다. 해시는 키를 활용해 데이터 탐색을 빠르게 한다.

• 특징
  • 단방향 동작: 키 통해 값 찾기만 가능
  • 시간 복잡도 O(1): 해시함수 덕분에 탐색 과정 필요 X
    • 해시 함수를 활용해서 특정 값이 있는 위치를 바로 찾기 가능
      • 해시 테이블: 키와 대응한 값이 저장되어 있는 공간
      • 버킷: 해시 테이블의 각 데이터
  • 값을 인덱스로 활용하려면 변환과정 필요
• 활용 분야
  • 비밀번호 관리
  • 데이터베이스 인덱싱
  • 블록체인

 

 

 

02. 해시 함수

자바에서는 해시셋 혹은 해시맵이라는 표준 API를 제공

해시 함수 구현시 고려사항

1. 해시 함수가 변환한 값은 인덱스로 활용해야 하므로 해시 테이블의 크기를 넘으면 안 된다.
2. 해시 함수가 변환한 값의 충돌은 최대한 적게 발생해야 한다.

• 충돌: 두 키에 대해 해싱 함수를 적용한 결과가 동일한 것
• 충돌이 아예 발생하지 않는 해시 함수는 없다.

자주 사용하는 해시함수

1. 나눗셈법

• 키를 소수로 나눈 나머지를 활용
• 모듈러 연산: 나머지를 취하는 연산
  • 연산자 %
    

• x는 키, k는 소수
• 키를 소수로 나눈 나머지를 인덱스로 사용

2.곱셈법

• m은 최대 버킷의 개수, A는 황금비
• 황금비: 무한소수
  • 수학적으로 임의의 길이를 두 부분으로 나누었을 때, 전체와 긴 부분의 비율이 기 부분과 짧은 부분의 비율과 같은 비율
• 황금비를 사용하므로 나눗세법처럼 소수가 필요없다는 장점
  • 해시 테이블의 크기가 커져도 추가 작업 필요 X

3. 문자열 해싱

• 문자열의 문자를 숫자로 변환하고 이 숫자들을 다형식의 값으로 변환해서 해싱

 

 

 

03. 충돌 처리

• 체이닝으로 처리
  • 충돌이 발생하면 해당 버킷에 링크드리스트로 같은 해시값을 가지는 데이터를 연결
  • 단점
    • 해시 테이블 공간 활용성 저하
    • 검색 성능 저하
  • 자바에서 HashMap 클래스는 체이닝을 사용하여 해시 충돌 처리
    • 충돌 발생시 링크드리스트로 연결하는 데이터가 일정 개수가 넘어가면 자동으로 해당 링크드리스트를 이진 탐색 트리로 변환하여 데이터 접근에 O(logN)의 성능이 나오도록 개선
• 개방 주소법으로 처리
  • 빈 버킷을 찾아 충돌값을 삽입
  • 해시테이블을 최대한 활용하므로 체이닝보다 메모리 사용 효율적
  • 방식
    1. 선형 탐사 방식
       • 충돌이 발생하면 다른 빈 버킷을 찾을 때까지 일정한 간격으로 이동
       • 클러스터 형성: 충돌 발생시 1칸씩 이동하며 해시 테이블 빈 곳에 값으 넣으면 해시 충돌이 발생한 값끼리 모이는 영역 발생 ⇒ 해시값이 겹칠 확률 증가
    2. 이중 해싱 방식
       • 해시 함수를 2개 사용
       • 두 번째 해시 함수는 첫 번째 해시 함수로 충돌 발생시 해당 위치를 기준으로 어떻게 위치를 정할지 결정

 

 

 

04. 해시맵

해시 테이블을 구현한 컬렉션: HashTable 클래스, HashMap 크래스

ADT

• 연산
  • `ValueType put(KeyType key, ValueType value)`: 데이터 저장
  • `ValueType get(KeyType key)`: key 값에 대한 value 값을 반환
  • `ValueType remove(KeyType key)`: 해시맵에서 key에 해당하는 데이터를 삭제
  • `boolean containsKey(KeyType key)`: 해시맵 안에 해당 key가 있다면 true, 없다면 false를 반환
  • `void clear()`: 해시맵 안의 모든 데이터를 삭제
• 상태
  • `boolean isEmpty()`: 해시맵 안에 데이터가 없다면 true, 있다면 false 반환
  • `int size()`: 해시맵 안에 있는 데이터의 개수를 반환

HashMap<String, Integer> hashMap = new HashMap<>();

hashMap.put("ABC", 10);
hashMap.put("BBB", 20);
hashMap.put("AAA", 30);

System.out.println(hashMap.isEmpty()); // fale
System.out.println(hashMap.get("ABC"); // 15
System.out.println(hashmap.containsKey("ABC"); // true

hashMap.remove("ABC");
System.out.println(hashMap.size()); // 2

hashMap.clear(); 
System.out.println(hashMap.isEmpty());