[F-Lab 모각코 페이백 9일차] 해시맵(HashMap), 해시(Hash)

학습 목표

• 해시맵(Hash Map)

TIL

• 해시맵(Hash Map)
  • 메서드
    • equals()
    • hashCode()
• 해시
  • 해싱
  • 해시 충돌
  • 해시 충돌 해결 기법
    • 오픈 어드레싱(Open Addressing)
    • 체이닝(Chaining)

해싱이 뭐야?

"해싱"은 데이터의 크기와 상관없이 고정된 크기의 고유한 값을 생성하는 과정을 말합니다. 해시 함수는 입력으로 데이터를 받아서 해시 값을 출력합니다. 이 고유한 해시 값은 원래의 데이터를 대표하며, 원래 데이터와 비교해 상당히 작은 고정된 크기를 가집니다.

해싱은 특히 데이터 저장 및 검색을 빠르게 수행하는데 유용합니다. 예를 들어, 해시맵 같은 데이터 구조는 키를 해시 함수에 통과시켜 결과 해시 값을 사용하여 값을 저장하고 검색합니다. 이렇게 해서 빠르게 특정 키와 연결된 값을 찾을 수 있습니다.

그러나 해싱은 항상 완벽하게 유일한 값을 보장하지는 않습니다. 다른 입력이 같은 해시 값을 생성할 수 있는데, 이를 "해시 충돌"이라고 합니다. 해시 함수의 선택과 해시 충돌의 처리 방법은 해시 기반 데이터 구조의 성능에 큰 영향을 미칩니다.

 

해시는 뭐야?

"해시"는 컴퓨터 과학에서 사용되는 용어로, 일정한 길이의 고유한 값이나 키를 의미합니다. 이 값은 원본 데이터를 해시 함수에 입력하여 생성됩니다.

해시 함수는 큰 데이터를 작은 크기의 고유한 값으로 변환하는 역할을 합니다. 예를 들어, 문자열이나 파일을 작은 크기의 숫자로 변환할 수 있습니다. 해시 함수의 특징은 같은 입력에 대해 항상 같은 출력을 반환하고, 크기와 상관없이 고정된 길이의 결과를 반환한다는 것입니다.

해시는 다양한 용도로 사용됩니다:

1. 해시 테이블: 해시는 빠른 데이터 검색을 가능하게 하는 해시 테이블이나 해시 맵과 같은 자료 구조에서 키로 사용됩니다.
2. 데이터 검증: 파일이나 메시지의 무결성을 검사하는데 해시를 사용할 수 있습니다. 원본 데이터의 해시를 계산하고, 이를 전송한 후에 다시 계산하여 비교하면 데이터가 온전하게 전달되었는지 확인할 수 있습니다.
3. 암호학: 해시는 비밀번호 저장이나 디지털 서명과 같은 암호학적 용도로도 사용됩니다. 비밀번호를 안전하게 저장하기 위해 해시를 사용하여 비밀번호를 '해싱'하고, 이 해시를 저장합니다.

해시 충돌은 두 개의 다른 입력이 같은 출력 해시를 생성하는 상황을 말합니다. 이는 피해야 하는 상황이지만, 모든 해시 함수는 이론적으로는 충돌을 발생시킬 수 있습니다. 이 문제를 해결하는 방법 중 하나는 충돌 발생 가능성이 매우 낮은 "강한" 해시 함수를 사용하는 것입니다.

 

해시테이블과 해시맵의 해시와 해싱을 이용해서 자료구조를 구현하는 방법과 원리 상세히 말해줘

1. 해시 함수: 해시 함수는 임의의 데이터(여기서는 키)를 입력으로 받아 고정된 길이의 숫자를 출력합니다. 이렇게 생성된 숫자는 원본 데이터를 식별하는 고유한 값으로 사용되며, 이를 해시 코드라고 부릅니다.
2. 버킷 배열: HashMap과 Hashtable은 내부에 버킷 배열을 유지합니다. 각 버킷은 해시 코드에 대응되는 키-값 쌍을 저장하는 공간입니다. 해시 함수는 키를 받아 해시 코드를 생성하고, 이 코드는 버킷 배열에서 적절한 버킷을 결정하는 인덱스로 사용됩니다.
3. 해시 충돌: 이론적으로, 두 개 이상의 키가 같은 해시 코드를 생성할 수 있습니다. 이런 상황을 해시 충돌이라고 합니다. HashMap과 Hashtable은 이런 충돌을 처리하기 위해 체이닝(chaining)이라는 방법을 사용합니다. 즉, 각 버킷은 실제로는 키-값 쌍의 연결 리스트를 저장합니다. 동일한 해시 코드를 가진 키-값 쌍들이 같은 버킷(즉, 같은 연결 리스트)에 저장됩니다.
4. 키-값 쌍의 저장 및 검색: 키-값 쌍을 저장하거나 검색할 때, 해시 테이블은 먼저 키의 해시 코드를 계산하고 이를 사용하여 적절한 버킷을 찾습니다. 그리고 이 버킷에 저장된 연결 리스트를 순회하여 해당 키를 가진 항목을 찾습니다.

HashMap과 Hashtable의 주요 차이점 중 하나는 동기화입니다. Hashtable은 스레드 안전(thread-safe)이지만 HashMap은 그렇지 않습니다. 여러 스레드가 동시에 해시 테이블을 수정하면 동시성 문제가 발생할 수 있습니다. 이러한 문제를 방지하기 위해 Hashtable은 각 메서드를 동기화하지만, 이로 인해 성능 저하가 발생할 수 있습니다. 반면에 HashMap은 비동기화되어 있어 단일 스레드 환경에서 더 빠른 성능을 제공합니다.

 

Hashtable은 null 키나 값이 허용되지 않는 반면에, HashMap은 하나의 null 키와 여러 null 값들을 허용합니다.

아직도 Hashtable이 필요한 경우는 매우 드뭅니다. 대부분의 경우에는 ConcurrentHashMap, Collections.synchronizedMap(), ReadWriteLock 등 다른 동시성 해결책을 사용하는 것이 좋습니다.

결론적으로, HashMap과 Hashtable 모두 키-값 쌍을 저장하는 데 해시 테이블을 사용합니다. 해시 테이블은 해시 함수를 사용하여 키를 고유한 해시 코드로 변환하고, 이 코드를 사용하여 내부의 버킷 배열에서 적절한 위치에 키-값 쌍을 저장하고 검색합니다. 이는 키에 대한 빠른 접근을 가능하게 합니다. 그러나 이 두 자료구조는 동기화, null 처리 등에서 차이를 보입니다.

 

나는 해시 맵 구현체에 hashCode()메서드와 equals() 메서드가 존재한다고 해서

어? 왜 그러면 오버라이딩을 해야하지?? 이미 존재하고 동작은 한다고 하였는데.

알고보니 해시 맵 구현체에 있는 두개의 메서드는 해시 맵 클래스, 즉 클래스 단위에 대한 해싱과 동등성을 확인하는 메서드라

우리가 월래 원하였던 해시맵에 들어있는 값에 대한 해싱을 하고 동등성을 확인 하려면

우리가 오버라이딩을 하여 해싱을 하고 동등성 확인 할 수 있도록 각각 코드를 짜야하는 것이였다.

 

나는 해싱을 사용하는 컬랙션은 hashCode()와 equals()를 둘다 꼭 재정의(Overriding) 해야한다고 해서

그 이유로 eqauls 메서드 내부 로직이나 동작에 hashCode를 사용 해서 그런 것인 줄 알았는데

알고보니 get()메서드를 사용하면 hashCode()를 사용하고 그 다음에 eqauls()를 호출하는 것이라고 한다.

 

과정설명:

hashCode()는 먼저 호출되어 가능한 한 정확한 버킷을 찾는 데 사용되며, 이렇게 함으로써 검색 효율성이 크게 향상됩니다. equals()는 이후에 호출되어 실제 원하는 키를 찾는 데 사용됩니다. 이는 hashCode() 메서드가 같은 값을 반환하는 서로 다른 키(즉, 해시 충돌이 발생하는 키)가 있을 수 있기 때문입니다. 따라서 equals()는 해시 충돌이 발생한 경우에 실제 원하는 키를 찾는 데 사용됩니다.

 

이것을 내가 풀이해보면 equals만 쓰면 애초에 정확했겠지만 효율성이 떨어서 hashCode로 1차적으로

같은 값을 찾는 것으로 효율성을 찾고 하나면 그것이 원하는 값일 테고 해시 충돌이 일어난다면

중복된 해시가 있다는 뜻이니까 그러면 그 떄는 찾은 값들 중(중복된 해시들 중) 다시 equals로 찾아보는 방식으로 진행된다.

 

Hash Map 주요 동작 원리

1. 삽입: HashMap에 값을 저장하려면, 키(key)와 값(value)을 함께 제공해야 합니다. HashMap은 먼저 키의 hashCode() 메서드를 호출하여 해시 코드를 얻습니다. 이 해시 코드는 배열의 인덱스로 사용되며, 이 위치에 키-값 쌍이 저장됩니다. 만약 같은 해시 코드를 가진 다른 키-값 쌍이 이미 그 위치에 있다면(이를 해시 충돌이라고 합니다), HashMap은 연결 리스트 또는 트리(Java 8 이후)를 사용하여 그 위치에 여러 키-값 쌍을 저장합니다.
2. 검색: 키를 사용하여 HashMap에서 값을 검색하려면, HashMap은 먼저 키의 hashCode() 메서드를 호출하여 해시 코드를 얻습니다. 이 해시 코드는 배열의 인덱스로 사용되며, 이 위치에서 키-값 쌍을 찾습니다. 만약 그 위치에 여러 키-값 쌍이 있다면(즉, 해시 충돌이 발생했다면), HashMap은 equals() 메서드를 사용하여 실제 키를 찾습니다.
3. 삭제: 키를 사용하여 HashMap에서 값을 삭제하려면, HashMap은 먼저 키의 hashCode() 메서드를 호출하여 해시 코드를 얻습니다. 이 해시 코드는 배열의 인덱스로 사용되며, 이 위치에서 키-값 쌍을 찾습니다. 만약 그 위치에 여러 키-값 쌍이 있다면(즉, 해시 충돌이 발생했다면), HashMap은 equals() 메서드를 사용하여 실제 키를 찾아 삭제합니다.

2번에 관해서 좀 더 질문을 했다.

찾을 저장하고 찾는 과정을 간단히 설명하면 get(키)메서드를 실행하면 만약 버킷이 11칸이라면 인덱스는 0~10까지만 존재할테고 해싱을 진행하면 해시를 11등분 하여서 그 나온 값에 맞는 인덱스에 있는 값을 가져오는가???

 

맞습니다, HashMap의 기본적인 동작 원리는 키의 해시 코드를 사용하여 버킷(인덱스)를 결정하고, 그 버킷에서 값을 찾는 것입니다. 그러나 이 과정에는 몇 가지 주의할 점이 있습니다.

1. 해시 코드 결정: 키의 hashCode() 메서드를 호출하여 해시 코드를 얻습니다. 이 해시 코드는 일반적으로 키의 상태(값)를 기반으로 생성되며, 두 키가 equals()를 통해 동일하다고 판단되면 반드시 같은 해시 코드를 반환해야 합니다.
2. 버킷 결정: 해시 코드를 HashMap의 버킷 수로 나눈 나머지를 사용하여 버킷(인덱스)를 결정합니다. 예를 들어, 버킷 수가 11이라면 해시 코드를 11로 나눈 나머지가 버킷이 됩니다. 이는 HashMap의 모든 버킷을 고르게 사용하도록 돕습니다.
3. 값 검색: 결정된 버킷에서 equals() 메서드를 사용하여 실제 키를 찾습니다. 만약 그 버킷에 여러 키-값 쌍이 있다면(즉, 해시 충돌이 발생했다면), equals() 메서드를 사용하여 정확한 키를 찾아 해당 값을 반환합니다.

따라서 get(키) 메서드를 실행하면, 키의 해시 코드를 사용하여 버킷을 결정하고, 그 버킷에서 equals()를 사용하여 실제 값을 찾습니다. 이렇게 하면 HashMap은 매우 큰 데이터 집합에서도 빠르게 값을 검색할 수 있습니다.

 

예전에 해시맵에 쓰이는 해시 함수와 해시 충돌에 알아 본적이 있었는데

해시 함수도 여러 종류고 그에 따라 드는 리소스와 해시 충돌간의 상관, 연관 관계가 있다고 보았었다.

소규모, 대규모 등 규모에 따라 다르고 다른 여러 요소에 따라 최적이 되는 해시 함수나 해시 충돌이 일어났을 떄 대처방법등이 다르다고 해서 좀 더 나중에 알아봐야겠다.

 

해시 충돌 해결하는 기법

1. Chaining(체이닝): Chaining 방식에서는 해시 테이블의 각 버킷이 키-값 쌍의 리스트를 가리키도록 합니다. 충돌이 발생하면, 동일한 버킷에서 여러 키-값 쌍이 리스트로 관리됩니다. 리스트는 연결 리스트 또는 트리 등의 자료 구조를 사용할 수 있습니다. HashMap은 이 방법을 사용하며, 특히 충돌된 키-값 쌍이 많아질 경우 연결 리스트를 밸런스가 잡힌 트리로 바꾸는 트리화(treeification)라는 최적화를 수행합니다.
2. Open Addressing(오픈 어드레싱): Open Addressing 방식에서는 해시 테이블의 모든 버킷이 단 하나의 키-값 쌍만을 저장합니다. 충돌이 발생하면, 다른 버킷에 키-값 쌍을 저장하는 방식으로 충돌을 해결합니다. 이때 새로운 버킷을 찾는 방법에 따라 선형 탐사(Linear Probing), 이차 탐사(Quadratic Probing), 더블 해싱(Double Hashing) 등의 방법이 사용될 수 있습니다.

이 두 가지 방법은 각각 장단점이 있습니다. 예를 들어, Chaining은 구현이 간단하고 메모리를 동적으로 할당하여 공간 효율이 좋지만, 많은 충돌이 발생하면 검색 성능이 저하될 수 있습니다. 반면 Open Addressing은 모든 키-값 쌍이 해시 테이블 안에 직접 저장되므로 메모리 접근 횟수가 줄어들지만, 충돌 해결이 복잡하고 테이블의 로드 팩터가 증가하면 성능이 크게 저하될 수 있습니다.