Skip to content

Latest commit

 

History

History
73 lines (56 loc) · 4.09 KB

1. HashTable.md

File metadata and controls

73 lines (56 loc) · 4.09 KB

HashMap과 HashTable

  • HashMap과 HashTable은 자바 API 이름입니다.

  • HashTable 또한 Map 인터페이스를 구현하고 있기 때문에 HashMap과 HashTable이 제공하는 기능은 같습니다.

  • 다만, HashMap은 보조 해시 함수(Additional Hash Functional)를 사용하기 때문에
    보조 해시 함수를 사용하지 않는 HashTable에 비해
    해시 충돌(hash collision)이 덜 발생할 수 있어 상대적으로 성능상 이점이 있습니다.

  • HahsMap과 HashTable을 정의한다면, 키에 대한 해시 값을 사용하여 값을 저장하고 조회하며,
    키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 'associate array'라고 할 수 있습니다.

  • 이 associate array를 지칭하는 다른 용어로는 Map, Dictionary, Symbol Table 등이 있습니다.

해시 분포와 해시 충돌

  • 동일하지 않은 객체 X와 Y가 있을 때, 즉 X.equals(Y)가 false일 때, X.hashCode() != Y.hashCode()라면
    이때 사용하는 해시 함수는 완전한 해시 함수(Perfect Hash Functions)라고 합니다.

  • Boolean 같이 서로 구별되는 객체의 종류가 적거나,
    Integer, Long, Double 같은 Number 객체는 객체가 나타내려는 값 자체를 해시 값으로 사용할 수 있기 때문에
    완전한 해시 함수 대상으로 삼을 수 있습니다.

  • 하지만 String이나 POJO(Plain Old Java Object)에 대해서 완전한 해시 함수를 제작하는 것은 사실상 불가능합니다.

  • 적은 연산만으로 빠르게 동작할 수 있는 완전한 해시 함수가 있다고 해도, 그것을 HashMap에서 사용할 수 있는 것은 아닙니다.

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

  • 32비트 정수 자료형으로는 완전한 자료 해시 함수를 만들 수 없습니다.
    논리적으로 생성 가능한 객체의 수가 2^32보다 많을 수 있기 때문입니다.

  • 또한, 모든 HashMap 객체에서 O(1)을 보장하기 위해 랜덤 접근이 가능하게 하려면,
    원소가 2^32인 배열을 모든 HashMap이 가지고 있어야 하기 때문입니다.

충돌 해결 : 저장할 위치 계산 방법

Division Method

  • 저장할 값을 배열의 크기로 나눈 나머지가 바로 그 값을 저장할 위치입니다.
  • 충돌이 발생하는 것을 최소화하고,
    배열의 값을 골고루 위치하게 하려면 배열의 크기가 소수(prime number)인 것이 좋습니다.
  • 계산이 간단하고 배열의 크기가 소수일 때 저장할 위치가 골고루 분포하게 됩니다.

Multiplication Method

  • 이 방법은 0 < A < 1 인 상수 A가 필요합니다.
  • 예를 들어 상수 A의 값을 0.3758이라고 하겠습니다.
  • 배열의 크기가 32, 저장할 값이 14라면 다음과 같은 절차로 저장할 위치를 계산합니다.
    1. 저장할 값을 A와 곱합니다. (14 x 0.3758 = 73.6568)
    2. 위의 결과에서 소수점 아래 자리만 꺼냅니다. (0.6568)
    3. 위의 결과에 배열의 크기를 곱합니다. (0.6568 x 32 = 21.0176)
    4. 위의 결과에서 소수점 아래 자리를 버립니다. (21)
    5. 결과적으로, 저장할 위치는 인덱스 21입니다.
static final double A = 0.3758;

private int getStartIndex(int value) {
    double fractionalPart = (value * A) % 10;       // 1, 2번 과정
    return (int)(fractionalPart * 배열의 크기);     // 3, 4번 과정
}
  • Division Method보다 계산이 복잡합니다. (실수 계산이기 때문입니다.)
  • 배열의 크기는 마음대로 정할 수 있습니다. (보통 2의 배수로 합니다.)

충돌을 해결하는 방법

  • 서로 다른 값을 저장할 위치가 동일할 경우 충돌이 발생합니다.
  • 충돌을 해결하는 방법은 다음과 같습니다.
    1. Chaining : 저장할 데이터를 LinkedList에 등록
    2. Open Addressing : 그 다음 칸에 저장을 시도
      • 그 다음 칸 계산 방법
        1. Linear probing
        2. Quadratic probing
        3. Double hashing