본문 바로가기
IT/Java

Hash 충돌의 해결

by 성준하이 2024. 8. 6.
반응형

아래 참고 포스팅에서 다양하게 자바에서 Hash 사용되는것들에 대해서 볼수 있다.

 

이 많은 해시들은 결국 Hash Function 에 의해서 가능한 서로 다른 키들에 대해 다른 해시 값을 생성하는데 

만약 이때 해시값이 충돌하여 동일한 값을 가지게 되면 어떻게 될까?

 

정답은

Hash Collision

이다.


해시 충돌은 서로 다른 데이터가 동일한 해시 값을 가지는 상황(key는 다른데, hash가 같을 때)이다.
해시 테이블의 크기는 제한되어 있기 때문에 현실적으로는 피할 수 없는 현상이다.

 

정리해서 다시 말하면 hash 충돌은 피할 수 없지만, 해시 함수의 결과 값이 골고루 분포되도록, 해시 충돌이 균등하게 발생하도록 해시 함수를 정하는 것이 좋다.

 

방법은 아래와 같다.

  • seperate chaining (체이닝)
    • 각 배열의 인덱스에 LinkedList를 사용하여 키들을 모아둔다.
      충돌이 발생하면 연결 리스트에 노드를 추가한다.
    • 과정
      • 해시 테이블 초기화 진행
        해시 테이블을 만들고, 각 인덱스에 빈 LinkedList를 할당한다.
      • 데이터 삽입
        해당 데이터의 해시 값을 계산하고 그 해시 값을 인덱스로 하는 LinkedList에 데이터를 추가한다.
        해당 인덱스에 다른 데이터가 이미 존재하는 경우에, 그냥 LinkedList의 다음 노드에 데이터를 추가한다.
      • 데이터 검색 또는 삭제
        동일한 해시 함수로 해당 인덱스을 찾고, LinkedList에서 데이터를 검색하거나 삭제한다.
    • 장점
      구현이 간단하고 유연하다.
      동적으로 크기를 조절하기 쉽다.
    • 단점
      메모리 사용이 비효율적일 수 있다. ⇒ 모든 인덱스에 LinkedList를 넣어놔야만 한다.
      연결 리스트의 길이가 길어지면 검색 시간이 길어질 수 있다. ⇒ LinkedList의 탐색 시간 복잡도는 O(n)
      (시간 복잡도 관련해서는 아래 참고 포스팅 참고)
      참고: LinkedList 대신 트리를 사용하여 충돌을 해결할 수 있으며, 이로써 탐색 시간을 효율적으로 유지할 수 있다.


  • open addressing (개방 주소법)
    • 충돌이 발생하면 다른 빈 버킷을 찾아 이동하거나 특정 규칙에 따라 다른 위치에 값을 저장한다.
      대표적인 개방 주소법에는 선형 탐사(Linear Probing), 이차 탐사(Quadratic Probing), 이중 해싱(Double Hashing) 등이 있다.
    • 과정
      • 해시 테이블 초기화 진행
        해시 테이블을 만들고, 인덱스가 아닌 버킷을 초기화 한다.
      • 데이터 삽입
        데이터를 삽입할 때, 해당 버킷이 비어있으면 데이터를 삽입한다.
        충돌이 발생하면 다른 방법을 사용하여 빈 버킷을 찾아 데이터를 삽입한다.
      • 데이터 검색 또는 삭제
        검색 또는 삭제 시에도 동일한 방법으로 데이터를 찾거나 삭제한다.
    • 장점
      캐시 및 메모리 사용이 효율적이다.
    • 단점
      복잡한 구현이 들어간다.
      클러스터링 성능 저하 우려가 있다.

 

또 다른 방법으로는 아예 해시 테이블 크기를 늘려주는방법도 있다.

해시 테이블 리사이징

테이블 리사이징은 기존 테이블 크기의 2배 크기의 테이블 선언하여, 기존 테이블의 데이터를 옮긴다. 자바의 경우, 테이블 공간의 3/4 이상을 차지하면 리사이징을 한다. 이는 사용하는 언어에 따라 리사이징 되는 수치는 다르다.
또한 테이블 리사이징을 하게 되면, 중첩되는 해시의 경우 다시 해시하여 다른 해시로 값을 이동하기도 한다.


참고 포스팅

https://thenicesj.tistory.com/1008

 

HashMap 정렬(Key/Value)

map에 대해서는 아래 참고 포스팅 참고 바란다. Map을 Key기준으로 정렬하기 위해서는 아래 코드와 같이 해결이 가능하다...이상 생략/ map 선언 되어있음List keySet = new ArrayList(map.keySet());// 키 값으

thenicesj.tistory.com

https://thenicesj.tistory.com/349

 

HashTable, HashMap, ConcurrentHashMap 비교

이전 포스팅에서 Map에 대해서 다룬적은 있다. 자세한 내용은 아래 참고 포스팅을 확인해보길 추천한다. 이번 포스팅에서는 Hash 관련해서 HashTable, HashMap, ConcurrentHashMap 세개를 얘기해볼 것이다.

thenicesj.tistory.com

https://thenicesj.tistory.com/772

 

Java 에서 Redis 사용하기 (@RedisHash , ValueOperations)

레디스에 대한 내용과 셋팅은 아래 참고 포스팅 참고 바란다. Java 에서 Redis 를 사용하기 위해서는 2가지 방법이 있다. (물론 이 밖에도 방법은 있다.) @RedisHash 사용 일반 ORM 프로젝트에서 Entity 를

thenicesj.tistory.com

https://thenicesj.tistory.com/599

 

JVM 내에 저장되어있는 데이터 위치 값 확인

자바를 사용한다면 JVM 이 뭔지 알것이라고 생각이 되지만 혹시 좀더 이해가 필요하면 아래 참고 포스팅을 참고 바란다. 자바에서 만약 String text = "A"; 이라고 선언을 하면 jvm 메모리 어딘가에 text

thenicesj.tistory.com

https://thenicesj.tistory.com/417

 

LinkedHashMap

이전에 포스팅에서 map과 set, list를 다룬적이 있는데 최근 linkedHashMap을 다루다가 해당 주제로 포스팅을 써본다. HashMap 은 hashcode 를 사용하기 때문에 순서가 일정하지 않다. LinkedHashMap 은 내부를 Do

thenicesj.tistory.com

https://thenicesj.tistory.com/284

 

시간복잡도 계산

시간복잡도 기본적인 연산을 수행하는데에 어떤 고정된 시간이 걸릴 때, 알고리즘에 의해서 수행되는 기본 연산의 개수를 세어 예측할 수 있다. 그러므로 걸리는 시간의 총량과 알고리즘에 의

thenicesj.tistory.com

 

반응형

댓글