Hash란?
Hash(해시)는 데이터를 고정된 크기의 고유한 값으로 변환시키는 함수야. 해시는 보안, 검색, 데이터베이스 등 다양한 분야에서 사용되며, 주로 데이터의 무결성 검증이나 데이터의 일치 여부를 확인하기 위해 사용돼.
해시 함수의 특징
입력값이 조금만 변해도 출력값이 완전히 달라짐.
출력값을 통해 입력값을 유추하기 어려움.
동일한 입력값에 대해서는 항상 동일한 출력값을 반환.
이러한 특징들로 인해 해시는 보안 문제에서 많이 사용되고, 비밀번호의 암호화나 인증 과정에서도 사용돼. 그러나 해시 함수는 입력값이 같은 경우 항상 같은 출력값을 반환하기 때문에, 해시값을 미리 계산해놓은 해시테이블에서는 충돌이 발생할 수 있어. 이를 방지하기 위해 충돌을 최소화할 수 있는 해시함수를 사용해야 해.
HashMap
HashMap은 Java에서 제공하는 해시 자료구조로, Key-Value 쌍으로 이루어져 있으며, Key를 인덱스로 사용하여 값을 저장해.
HashMap의 특징
Key는 중복될 수 없으며, Value는 중복될 수 있음.
null 값을 허용함 (Key와 Value 둘 다 허용).
순서를 보장하지 않음.
HashMap은 많은 양의 데이터를 빠르게 검색할 수 있으며, 삽입과 삭제도 빠르게 가능해. 하지만 해시 충돌이 발생할 경우 검색 성능이 저하될 수 있으므로, 충돌을 최소화할 수 있는 해시함수를 사용해야 해.
HashSet
HashSet은 Java에서 제공하는 해시 자료구조 중 하나로, 중복되지 않는 요소들을 저장하는 집합(set)을 구현하며, 내부적으로 HashMap을 사용해.
HashSet의 특징
요소들은 순서를 보장하지 않음.
null 값을 허용함.
중복된 값은 허용하지 않음.
HashSet은 데이터베이스나 파일 시스템 등에서 중복된 값을 제거하거나, 대용량 데이터 중에서 특정 값을 찾을 때 유용하게 사용될 수 있어. 또한, HashSet은 Set 인터페이스를 구현하기 때문에, Set이 제공하는 다양한 메서드를 사용할 수 있어.
HashSet의 주요 메서드
add(E e): 지정된 요소를 HashSet에 추가.
clear(): HashSet에서 모든 요소를 제거.
contains(Object o): 지정된 요소가 HashSet에 포함되어 있는지 확인.
isEmpty(): HashSet이 비어있는지 확인.
iterator(): HashSet의 요소를 반복하는 Iterator를 반환.
remove(Object o): 지정된 요소를 HashSet에서 제거.
size(): HashSet에 저장된 요소의 개수를 반환.
Hash Table
해시 테이블(Hash Table)은 해시 함수를 사용하여 키(Key)와 값을 연결하는 자료구조야. 해시 함수를 사용하여 키와 값이 저장될 위치를 계산하기 때문에, 검색, 삽입, 삭제 모두 O(1)의 상수 시간 내에 이루어져.
하지만 해시 충돌이 발생할 경우 검색 성능이 저하될 수 있으므로, 충돌을 최소화할 수 있는 해시함수를 사용해야 해. 해시 테이블은 키(Key)와 값(Value)을 1:1 대응시키는 구조이기 때문에, 키와 값 모두 유일해야 해.
Java에서는 해시 테이블을 구현하기 위해 Hashtable, HashMap, LinkedHashMap, ConcurrentHashMap 등 다양한 클래스를 제공해. 이 클래스들은 각각의 특징과 용도에 따라 적합한 클래스를 선택하여 사용할 수 있어.
Java의 해시 테이블 클래스들
Hashtable: Java에서 가장 오래된 해시 테이블 클래스이며, 동기화를 보장하기 때문에 멀티스레드 환경에서 안전하게 사용할 수 있지만 동기화로 인한 성능 저하가 발생할 수 있어.
HashMap: Hashtable보다 빠른 검색 속도와 삽입/삭제 속도를 가지고 있지만 동기화를 보장하지 않기 때문에 멀티스레드 환경에서 안전하게 사용하기 위해서는 ConcurrentHashMap을 사용해야 해.
ConcurrentHashMap: 멀티스레드 환경에서 안전하게 사용할 수 있는 해시 테이블 클래스. 동시성을 보장하기 위해 분할 잠금을 사용하므로, 여러 스레드가 동시에 접근해도 성능이 저하되지 않아.
LinkedHashMap: 삽입 순서를 보장하기 때문에, 순서에 따라 데이터를 처리해야 하는 경우에 유용해.
해시 테이블에서 충돌 해결 방법
Open Addressing
충돌이 발생하면 미리 정한 규칙에 따라 해시 테이블의 비어있는 슬롯을 찾아. 추가적인 메모리를 사용하지 않으므로 linked list 또는 tree 자료구조를 통해 추가로 메모리를 할당하는 separate chaining 방식에 비해 메모리를 적게 사용해.
Linear Probing(선형 조사법): 충돌 발생 시 해시값으로부터 일정한 값만큼 뛰어, 비어있는 슬롯에 저장해.
Quadratic Probing(이차 조사법): 제곱수로 건너뛰어 비어 있는 슬롯에 저장해.
Double Hashing(이중 해시, 중복 해시): 클러스터링 문제가 발생하지 않도록 2개의 해시 함수를 사용해. 하나는 최초의 해시값을 얻을 때 사용하고 또 다른 하나는 해시 충돌이 발생할 때 탐사 이동폭을 얻기 위해 사용해.
Separate Chaining
linked list(또는 tree)를 이용하여 충돌을 해결해. 충돌이 발생하면 linked list에 노드를 추가하여 데이터를 저장해.
삽입: 서로 다른 두 key가 같은 해시값을 갖게 되면 linked list에 node를 추가하여 (key, value) 데이터 쌍을 저장해. 시간 복잡도 O(1).
검색: 기본적으로 O(1)의 시간 복잡도지만 최악의 경우 O(n)의 시간 복잡도.
삭제: 삭제하기 위해 검색을 먼저 하므로 검색과 동일하지만 최악의 경우 O(n)의 시간 복잡도.
최악의 경우 n개의 모든 key가 동일한 해시값을 갖게 되면 길이 n의 linked list가 생성되는데 이때 시간 복잡도는 O(n)이 돼.
추가로 알아두면 좋은 내용
해시 함수 선택
Cryptographic Hash Functions: MD5, SHA-1, SHA-256 같은 해시 함수들은 보안이 중요한 경우에 사용돼.
Non-Cryptographic Hash Functions: CityHash, MurmurHash 같은 해시 함수들은 성능이 중요한 경우에 사용돼.
해시 함수의 응용
비밀번호 저장: 비밀번호는 해시 값을 저장하여 원본 비밀번호를 직접 저장하지 않음으로써 보안을 강화해.
데이터 무결성 검증: 파일이나 데이터 전송 시 해시 값을 이용해 데이터의 무결성을 검증할 수 있어.
빠른 데이터 검색: 해시 테이블을 이용해 대용량 데이터에서 빠르게 데이터를 검색할 수 있어.
