해시함수 정리 (Hash 충돌 발생 원인과 해결방법 / Hash Table과 Hash Map 차이점)

 

1.해시 함수란?

2.해시 충돌이란?

3.해시 함수를 사용하는 자료구조

 

승원이가 어제 퇴근시간 직전 내줬던 숙제를

하루종일 고민하고 공부하며 열심히 정리해봤다.

 

참고한 출처는 키워드, 문장에 삽입해놨으니 

부족한 내용이 있거든 이동해 확인하시길 바란다. 

 

 

 

---

 

1. 해시 함수란 무엇인가? 

• 임의의 길이를 가진 데이터를 입력받아 고정된 길이의 값, 즉 해시값을 출력하는 함수
• 입력값의 길이가 달라도 출력값은 언제나 고정된 길이로 반환
• 동일한 값이 입력되면 언제나 동일한 출력값을 보장 (항상 동일한 해시값을 가짐)
• 암호 알고리즘에서는 키가 사용되는 반면, 키를 사용하지 않기 때문에 같은 입력에 대해
  같은 출력이 나오게 되기 때문에 메세지의 오류나 변조를 탐지할 수 있는 무결성을 제공하기 위해 사용
• 블록체인에서 해시 함수를 사용하는 이유는 고유한 해시값으로 변환하여 저장함으로써
  식별성, 무결성, 데이터 보안 등의 장점이 있기 때문이다.

 

특징

• 단방향성
     : 입력된 데이터에서 해시값으로 변환은 쉽지만, 원래 데이터로 역변환은 거의 불가능
       (데이터의 무결성을 보장하고, 보안 용도로 활용되는데 중요한 특징이라고 할 수 있음)
• 해시 충돌 (Hash Collision)
     : 서로 다른 입력에 대해 동일한 해시값을 출력할 수 있기 때문에 충돌이 발생한다.
       보안 측면에서도 낮은 충돌 확률을 보장해야 좋은 해시 함수라고 할 수 있다.
• 일정한 결과값 길이
     : 입력 데이터의 크기가 다르더라도 항상 동일한 길이의 해시값을 반환한다.
       (블록체인과 같은 분산 시스템에서 데이터의 일관성과 효율적인 처리를 보장하는데 유용)

 

---

 

2. 해시 충돌은 어떨 때 발생할까?

위에서 설명했지만, 해시 함수가 서로 다른 두 개의 입력 값에 대해

동일한 출력 값을 내는 상황에서 충돌이 발생한다.

 

 

 

해결 방법

• 체이닝(Chaining) : 충돌 시 연결 리스트를 만들어 값을 할당하고 이어서 연결하는 방식
  • 연결 리스트로 노드를 계속 추가해 나가는 방식으로 제한은 없지만, 메모리 문제가 발생한다.
• Open Addressing : 충돌 시 해시 테이블에서 비어있는 인덱스에 할당하는 방식
  • 선형 탐사 : 만들어놓은 버킷의 자리를 우선적으로 사용하는 방식 (정해진 고정 폭으로 옮겨 해시값 중복을 피함)
                      테이블이 모두 차면 Resizing을 통해 크기를 늘려줘야 한다.
    
  • 제곱 탐사 : 정해진 고정 폭을 제곱수로 옮겨 해시값의 중복을 피함
  • 이중 해싱 : 충돌이 발생한 경우 기존과 다른 해싱 함수를 사용해 인덱싱하여 해시값 중복을 피함

 

정리
Chaining	연결 리스트를 만들어 값을 할당하기 때문에 리스트를 계속 만들면 공간 메모리 측면에서 비효율적이다.
Open Addressing	비어있는 인덱스에 값을 할당하기 때문에 한정된 공간의 해시 테이블을 사용하는 경우 적합하지 않다. 해시 충돌에 대비해 Hash Table 크기를 잡아 한다.

 

---

 

3. Java에서 해시를 사용하는 자료구조

• key-value 쌍을 이루는 자료구조로써 검색, 삽입, 삭제, 연산을 빠르게 할 수 있다.
• Hash 자료구조에 key-value 삽입 방법
     ① key에 해당하는 데이터를 Hash 함수를 통해 Hash 코드로 변환
     ② % 연산으로 데이터를 저장할 Index 크기 구하기
     ③ Value를 해당 Index에 저장

 

3-1 Hash Table과 Hash Map 차이점

1. HashTable은 key와 value 값에는 null을 넣을 수 없다.  반면, Map은 동기화되지 않지만 null을 허용한다. 
   
   
2. 둘 다 Map 인터페이스를 구현하고 있기 때문에 제공하는 기능은 같다고 할 수 있으나
   Hash Table(JDK 1.0)보다 HashMap(Java 2)이 나중에 나왔으며, 지속적으로 개선되고 있는 편이다. 
   
   
3. 또한 HashMap은 보조 해시를 사용하기 때문에 비교적으로 해시 충돌이 덜 발생해 성능상 이점이 있다.
   
   
4. 그렇다면 (JDK 1.0) 틀딱 Hash Table은 내세울 것이 아무것도 없는가? 아니다.
   HashTable은 동기화를 보장해 Thread-Safe 이점이 있기 때문에 동시 접근에 안전하려면 HashTable
   
   
   
5. Thread-Safe 이점이 있는 만큼 한 Thread에서 작업 중인 경우
   다른 곳의 작업에 block을 걸기 때문에 당연히 속도에 이슈가 생기게 될 것이다.
   단일 Thread에서 빠른 처리가 목적이라면 HashMap을 사용하면 된다.
   
6. 요약하자면, 단일 Thread - HashMap   /   멀티 Thread - ConcurrentHashMap

 

3-2 HashTable 장단점

장점

• 빠른 검색 및 삽입
     : HashTable은 해시 함수를 사용해 데이터를 저장하기 때문에 데이터에 접근하는데 상수시간(O(1))이 소요
• 유연한 크기 조정
     : HashTable은 데이터의 갯수에 따라 자동으로 크기 조절이 가능해 메모리 공간의 효율성을 유지하면서도 
       높은 성능을 유지 가능하다.
• 다양한 용도로 활용 가능
     : HashTable은 캐싱, 데이터베이스 인덱싱, 중복 검사 등에 사용 가능

 

단점

• 해시 충돌
     : 새로 다른 키가 동일한 해시값에 매핑될 수 있는데, 충돌이 자주 발생할 경우 검색 및 삽입 연산의 성능 저하 우려
• 메모리 사용량
     : 해시 버킷과 해시 함수를 사용하기 때문에 일정한 메모리 공간이 필요 (데이터 수 많을수록 메모리 사용량 증가)
• 순서의 무작위성
     : key의 해시값을 기반으로 데이터를 저장해 순서가 무작위 (순차적 접근이 필요 시 다른 자료구조 고려)