해시는 데이터를 고정된 크기의 값으로 변환하는 함수를 말합니다.

해시 함수는 입력으로 받은 데이터를 해시 값으로 변환하는 역할을 수행하며, 해시 값은 고유한 값으로 매핑된다.

해시 함수의 주요 특징은 다음과 같다.

1. 일관성 : 동일한 입력에 대해서는 항상 동일한 해시 값을 출력한다. 즉, 입력이 조금만 변경되어도 해시 값은 완전히 다르게 나타난다.
2. 고유성: 서로 다른 입력은 항상 다른 해시 값을 가지도록 보장한다. 하지만 입력 공간이 유한하기 때문에, 해시 함수는 충돌이 발생할 수 있다. 충돌이란 두 개 이상의 입력이 동일한 해시 값을 가지는 상황을 말한다.
3. 역전파 불가능성: 해시 값을 통해 입력 값을 역추적하는 것은 매우 어렵거나 거의 불가능하다. 해시 함수는 일방향성을 가지며, 입력 값을 해시 값으로 변환하는 것은 가능하지만, 해시 값을 역으로 입력 값으로 변환하는것은 매우 어렵다.

해시는 다양한 용도로 활용된다.

1. 데이터 검색: 해시 함수를 사용하여 데이터를 해시 값에 매핑하여 검색 속도를 빠르게 할 수 있다. 해시를 사용하면 데이터를 효율적으로 저장하고 검색하는 데 사용할 수 있는 해시 테이블을 구현 가능
2. 암호화: 해시 함수는 보안 분야에서도 중요한 역할을 한다. 비밀번호 저장, 디지털 서명, 메시지 무결성 확인 등 다양한 보안 작업에 활용된다. 예를 들어, 비밀번호를 해시 함수에 적용하여 해시 값으로 저장하고, 로그인 시 입력된 비밀번호를 해시 함수에 적용하여 저장된 해시 값과 비교하는 방식을 사용할 수 있다.
3. 데이터 무결성 확인 : 데이터의 무결성을 확인하기 위해 해시 함수를 사용할 수 있다. 예를 들어, 파일의 해시 값을 계산하고, 파일이 변경되지 않았는지 확인하기 위해 이전 해시 값과 비교할 수 있다.

시간 복잡도

해시 함수의 시간 복잡도는 보통 O(1)인데

충돌이발생하는 경우 선형 탐사법, 체이닝, 이중 해싱 등과 같은 충돌 해결 방법을 사용해야하므로, 최악의 경우에는 O(n)의 시간 복잡도를 가질 수 있다.

해시 함수와 충돌 해결 방법의 선택은 해시 테이블의 성능에 영향을 미치는 중요한 요소

효율적인 해시 함수와 충돌 해결 방법을 선택하여 해시 테이블을 구현하면 보다 효율적인 데이터 저장 및 검색이 가능

HashMap과 Map의 차이점

둘 다 키-값 쌍을 저장하는 자료구조

HashMap: HashMap은 가변(mutable)한 자료구조, 요소를 추가, 수정, 삭제할 수 있습니다.

Map: Map은 불변(immutable)한 자료구조입니다. 한 번 생성된 Map은 요소를 추가, 수정, 삭제할 수 없습니다. 하지만 Map을 기반으로 새로운 Map을 만들거나, 불변 컬렉션 함수를 사용하여 변형된 Map을 얻을 수 있습니다.

HashMap 사용법

val hashMap = HashMap<String,Int>()

//요소 추가
hashMap["apple"] = 5
hashMap["banana"] = 2
hashMap["orange"] = 8

// 요소 접근
val count = hashMap["apple"]

// 요소 수정
hashMap["apple"] = 10

// 요소 삭제
hashMap.remove("banana")

for((key, value) in hashMap) {
	println("$key: $value")
}

해시 vs 배열

해시의 장점

1. 요소의 삽입 및 삭제

   해시는 요소의 삽입 및 삭제를 평균적으로 상수 시간 O(1)에 수행할 수 있다. 즉, 해시 테이블을 이용하면 요소의 삽입과 삭제가 매우 빠르게 이루어질 수 있다. 배열은 요소를 삽입하거나 삭제할 때 이동작업이 필요하므로 시간이 더 소요될 수 있다.

2. 탐색 속도

   해시를 사용하면 요소를 키-값 쌍으로 저장하므로 특정 요소를 빠르게 검색할 수 있다.

   키를 해시 함수에 적용하여 해시 값을 계산한 후, 해당 해시 값을 가진 인덱스로 바로 접근하여 요소를 찾을 수 있다. 이는 평균적으로 상수 시간 O(1) 에 탐색이 가능 배열의 경우 요소를 탐색하기 위해서는 선형 검색을 수행해야 하므로 최악의 경우 시간 복잡도가 O(n)이 될 수 있다

1. 중복 요소 확인

   해시를 사용하면 중복된 요소를 효율적으로 확인 가능 요소를 해시 테이블에 저장하고, 이미 저장된 요소인지 여부를 빠르게 확인 가능

   이는 중복요소를 확인하기 위해 배열을 순회하는 것보다 효율적

2. 그룹화 및 카운팅

   해시를 사용하여 데이터를 그룹화하거나 특정 요소의 등장 횟수를 카운팅하는 경우에도 효율적이다. 해시를 사용하면 각 요소를 키로 하고, 해당 요소의 정보를 값으로 저장하여 효율적으로 그룹화하거나 카운팅 가능

3. 효율적인 메모리 사용

   해시는 동적으로 크기가 조정되는 자료구조. 요소의 삽입 및 삭제에 따라 해시 테이블의 크기가 자동으로 조정되므로, 필요한 메모리 공간을 효율적으로 사용 가능

   배열은 초기에 크기를 정해야 하며, 크기를 동적으로 변경하기 위해서는 추가적인 작업이 필요