ProgrammingFor Interview

CS 자료구조

CS, Interview, 자료구조

자료구조

순서는 내맘대로기때문에 의미 없음.


해시(Hash)

LinkedList와 Array의 한계점을 극복하기 위해 제시된 방법.

기본 개념

  • 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 가짐(인덱스로 접근하므로)
  • 데이터 삽입 삭제시 shift 작업이 필요없도록 key 값을 hash function을 이용하여 데이터와 연관된 고유한 숫자(작은 범위의 값)로 만들어 낸 뒤 인덱스로 사용. 이를 hash code라고 함. (자바는 Object 클래스에 hashCode() 라는 메서드로 정의되어있다. 기본 클래스가 아닌 새로 정의한 클래스(ex. POJO)에서 HashMap을 제대로 사용하기 위해서는 이 메서드를 적절하게 오버라이드해야한다.)
  • 내부적으로 사용하는 배열을 Hash Table이라고 하며, 이 크기에 따라 성능 차이가 존재한다.

Hash code의 Collision

  • 어설픈 hash function은 동일한 hash code를 만들어낼 수 있고, 이로 인해 충돌이 발생할 수 있다.
  • collision이 많아질수록 탐색에 필요한 시간복잡도가 O(1) 에서 O(n)이 될 수 있다.

충돌 해결법 1. Open Address 방식 (개방 주소법)

  • 삽입하려는 버킷에 이미 데이터가 있는 경우, 다른 버킷을 찾아 삽입하는 방식.

  • worst case로 비어있는 버킷을 찾지 못하고 시작점으로 되돌아는 경우가 있다.

    • Linear Probing : 순차적으로 탐색하며 비어있는 버킷을 찾을 때까지 계속 진행된다.
    • Quadratic probing : 2차 함수를 이용해 탐색할 위치를 찾는다.
    • Double hashing probing : 하나의 해쉬 함수에서 충돌이 발생하면 2차 해쉬 함수를 이용해 새로운 주소를 할당한다. 위 두 가지 방법에 비해 많은 연산량을 요구하게 된다.

충돌 해결법 2. Separate Chaining 방식 (분리 연결법)

  • 같은 해시 값을 갖는 데이터를 연결 리스트에 의해 사슬 모양으로 연결하는 방식

  • Java HashMap에서 사용되는 방식

  • 보조 해시 함수를 잘 조정하면 충돌 빈도를 줄일 수 있음
    • 연결 리스트를 사용하는 방식(Linked List)
    • Tree 를 사용하는 방식 (Red-Black Tree)

Open Address VS Separate Chaining

일단 두 방식 모두 Worst Case 에서 O(M)

Open Adress 방식
  • 연속된 공간에 데이터를 저장하기 때문에 Separate Chaining에 비해 캐시 효율이 높다.
  • 데이터의 개수가 충분히 적다면 Separate Chaining 보다 더 성능이 좋다.
  • 배열의 크기가 커지면 캐시 효율에 대한 장점은 사라진다.
  • 버킷을 채운 밀도가 높아질수록 충돌 빈도 높아짐
Separate Chaining 방식
  • 충돌이 잘 발생하지 않도록 보조 해시 함수를 잘 조정하면 된다.

  • 개방주소법에 비해 삭제가 간단하다.

  • Open Address방식은 버킷을 계속해서 사용한다. 따라서 Separate Chaining 방식은 테이블의 확장을 보다 늦출 수 있다.

Java에서의 HashMap

map(또는 mapping) : 대응 관계를 지칭하는 용어. 함수 자체를 의미하기도 함

HashMap은 키 집합인 정의역과 값 집합인 공역의 대응에 해시 함수를 이용한다.

  • Java Collections Framework에 속한 구현체 클래스
  • 키에 대한 해시 값을 사용하여 값을 저장하고 조회하며, 키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 associate array

  • 기본적으로 각 객체의 hashCode() 메서드가 반환하는 값을 사용하는 데, 결과 자료형은 int

  • 데이터 개수가 많아지면 Separate Chaining 에서 연결리스트 대신 트리를 사용한다.

해시 버킷 동적 확장(Resize)

해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만 해시 충돌로 인해 성능 상 손실이 발생한다. 그래서 HashMap 은 key-value 쌍 데이터 개수가 일정 개수 이상이 되면 해시 버킷의 개수를 두 배로 늘린다. 이렇게 늘리면 해시 충돌로 인한 성능 손실 문제를 어느 정도 해결할 수 있다. 또 애매모호한 ‘일정 개수 이상’이라는 표현이 등장했다. 해시 버킷 크기를 두 배로 확장하는 임계점은 현재 데이터 개수가 해시 버킷의 개수의 75%가 될 때이다. 0.75라는 숫자는 load factor 라고 불린다.

참고 : Java HashMap은 어떻게 동작하는가?, 해쉬 기본 개념과 구조

아무리 줄이고 싶어도 길다. 어떤 부분이 중요한지 짚을 수가 없다.

위로

Share