해시는 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조이다. 키와 데이터가 일대일 대응하므로 키를 통해 데이터에 바로 접근할 수 있다.

특정 데이터를 탐색하는 횟수가 많을 경우 해시를 고려하면 좋다!

ex. 연락처: 전화번호는 값(value)이고, 값을 검색하기 위해서 활용하는 정보는 키(key)이다. 그리고 그 사이에 키를 이용해 해시값 또는 인덱스로 변환하는 해시 함수가 있다.

특징

1. 단방향으로 동작
   키를 통해 값을 찾기 O
   값을 통해 키를 찾기 X
   (외부에 정보를 안전하게 제공할 수 있어서 네트워크 보안에서 많이 활용됨)
2. 찾고자 하는 값을 O(1)에서 바로 찾을 수 있다.
   키 자체가 해시 함수에 의해 값이 있는 인덱스가 되므로 값을 찾기 위한 탐색 과정이 필요 없다.
3. 값을 인덱스로 활용하려면 적절한 변환 과정을 거쳐야 한다.

해시 테이블은 키와 대응한 값이 저장되어 있는 공간.
해시 테이블의 각 데이터를 버킷(bucket)이라고 함.

해시 함수

JAVA에서는 해시셋 혹은 해시맵이라는 표준 API를 제공하는데 이 클래스는 해시와 거의 동일하게 동작하므로 해시를 쉽게 사용할 수 있다.

해시 함수를 구현할 때 고려할 내용

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

자주 사용하는 해시 함수

1. 나눗셈법(division method)
   키를 소수로 나눈 나머지를 활용. — 소수를 사용하면 다른 수를 사용할 때보다 충돌이 적다.
   (나머지를 취하는 연산을 모듈러 연산이라고 함)
2. 곱셈법(multiplication method)
   모듈러 연산을 활용하지만 소수는 활용하지 않는다. 황금비를 사용.
   황금비: 수학적으로 임의의 길이를 두 부분으로 나누었을 때, 전체와 긴 부분의 비율이 긴 부분과 짧은 부분의 비율과 같은 비율을 뜻한다. 대략 1.6180339887…
3. 문자열 해싱
   문자열의 문자를 숫자로 변환하고 이 숫자들을 다항식의 값으로 변환해서 해싱한다. 해시 함수를 적용한 값이 해시 테이블 크기에 비해 너무 커 오버플로우가 발생될 여지가 있다. 그래서 중간 중간 모듈러 연산을 해 더한 값을 모듈러 연산하면 오버플로우를 최대한 방지할 수 있다.

충돌 처리

서로 다른 키에 대해서 해시 함수의 결과값이 같으면 충돌(collision)이라고 한다.

1. 체이닝으로 처리하기 —java에서 HashMap 클래스가 사용하는 법
   체이닝은 충돌이 발생하면 해당 버킷에 Linked List로 같은 해시값을 가지는 데이터를 연결하여 해결한다.

   • 단점
     충돌이 많아지면 그만큼 LinkedList의 길이가 길어지고, 다른 해시 테이블의 공간은 덜 사용하므로 공간 활용성이 떨어진다.
     충돌이 많아지면 LinkedList 자체의 한계 때문에 검색 성능이 떨어진다.
     — java에서는 LinkedList로 연결하는 데이터가 일정 개수 넘어가면 자동으로 이진 탐색 트리로 변환한다.

2. 개방 주소법으로 처리하기(open addressing)
   빈 버킷을 찾아 충돌값을 삽입한다. 메모리를 더 효율적으로 사용하는 방법이다.

   • 단점
     충돌 발생시 1칸씩 이동하며 빈 버킷에 값을 넣으면, 해시 충돌이 발생한 값끼리 모이는 영역이 생긴다. 이를 클러스터(cluster)를 형성한다고 하는데, 이러한 군집이 생기면 해시값은 겹칠 확률이 높아진다.

해시맵

해시맵을 위한 HashTable 클래스와 HashMap 클래스가 있다. 유사하지만 전자는 자바의 초기 버전과 호환성을 위한 것일 뿐 최근에는 잘 사용하지 않는다.

HashMap<KeyType, ValueType>

구분	정의	설명
연산	put(KeyType key, ValueType value)	해시맵에 데이터를 저장합니다. 첫 번째 매개변수는 해당 데이터의 key 값, 두 번째 매개변수는 해당 key에 해당하는 value 값입니다. 반환하는 값은 해시맵 내에 동일한 key에 해당하는 값이 있었다면 그 key에 대한 value 값을 반환합니다.
	get(KeyType key)	key 값에 대한 value 값을 반환합니다.
	remove(KeyType key)	해시맵에서 key에 해당하는 데이터를 삭제합니다.
	containsKey(KeyType key)	해시맵 안에 해당 key가 있다면 true, 없다면 false를 반환합니다.
	getOrDefault(Object key, V defaultValue)	해시맵 안에 해당 key가 있다면 해당 값을, 없다면 null 대신 기본 값을 반환하도록 할 수 있는 방법.
상태	void clear()	해시맵 안의 모든 데이터를 삭제합니다.
	int isEmpty()	해시맵 안에 데이터가 없다면 true, 있다면 false를 반환합니다.
	int size()	해시맵 안에 있는 데이터의 개수를 반환합니다.

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        // HashMap<KeyType, ValueType> 입니다.
        HashMap<String, Integer> hashMap = new HashMap<>();

        // hashMap에 데이터 추가
        hashMap.put("ABC", 10);
        hashMap.put("BBB", 20);
        hashMap.put("AAA", 30);
        hashMap.put("ABC", 15); // 기존 "ABC" 키의 값이 15로 업데이트됨

        System.out.println(hashMap.isEmpty()); // false
        System.out.println(hashMap.get("ABC")); // 15
        System.out.println(hashMap.containsKey("ABC")); // true
        
        System.out.println(hashMap.getOrDefault("ABC", "디폴트값")); // 15
        System.out.println(hashMap.getOrDefault("red", "디폴트값")); // 디폴트값

        // hashMap에서 키 "ABC"인 데이터 제거
        hashMap.remove("ABC"); 
        System.out.println(hashMap.size()); // 2

        // 해시맵의 모든 데이터 삭제
        hashMap.clear();
        System.out.println(hashMap.isEmpty()); // true
    }
}

	HashMap	HashSet
저장 방식	키-값 (Key-Value) 쌍 저장	유일한 값 (Unique Value) 저장
중복 허용 여부	키(Key)는 중복 불가, 값(Value)은 중복 가능	값(Value)이 중복 불가
내부 구현	HashTable 기반 (HashMap<K, V>)	내부적으로 HashMap<K, Object> 사용
null 허용 여부	키에 null 허용 (한 개만), 값에는 여러 개 가능	null 값 한 개 허용
사용 목적	키-값 매핑이 필요할 때	유일한 요소 집합이 필요할 때

참고 자료: 코딩테스트 합격자 되기 : 자바편