[F-Lab 모각코 챌린지 17일차] HashMap을 위한 HashTable

TIL

1. HashMap과 HashTable
2. HashTable
   • HashTable 특징
   • 해시충돌
   • 해시충돌 핸들링 하는 방법
     • Open Addressing
     • Separate Chaining
   • HashTable 아주 간단하게 구현하기
   • 해시버킷 동적 확장

 

---

 

HashMap과 HashTable

HashMap과 HashTable을 정의한다면

 

1. key에 대한 hash 값을 사용하여 value를 저장하고 조회한다.
2. key-value pair의 개수에 따라 동적으로 크기가 증가하는 associate array라고 할 수 있다.

 

HashMap과 HashTable이 제공하는 기능은 같다. 다만 HashMap은 보조해시함수(Additional Hash Function)를 사용하기 때문에 HashTable에 비하여 해시충돌(hash collision)이 덜 발생할 수 있어 성능상 이점이 있다.
현재 HashTable 구현에는 변화가 거의 없는 반면에 HashMap은 지속적으로 개선되고 있다.

 

 

 

HashTable

1. 검색하고자 하는 key 값을 입력 받아서 해시함수에 돌린다.
   • 숫자, 문자열, 파일 데이터를 key 값으로 입력 받을 수 있다.
   • 해시함수는 특정한 규칙을 이용해서 입력 받은 key 값으로 고정된 길이의 해시코드를 만들어준다.
2. 해시함수로부터 리턴 받은 해시코드를 배열의 index로 환산한다.
3. index를 통해 value 값에 접근한다.

 

 

 

HashTable 특징

HashTable의 가장 큰 장점은 검색 속도가 매우 빠르다는 것이다. 해시함수를 이용해서 만든 해시코드는 정수이다. 배열 공간을 고정된 크기만큼 미리 만들어놓고 해시코드를 배열의 개수로 나머지 연산을 하여 배열 방에 나눠 담는다. 즉, 해시코드 자체가 배열 방의 index로 사용되기 때문에 검색 작업 자체를 할 필요가 없다는 뜻이다. 해시코드를 이용하여 데이터의 위치에 direct로 접근할 수 있기 때문에 검색 속도가 이렇게 빠른 것이다.

 

그러나 해시테이블도 아주 완벽한 것은 아니다. 어떻게 하다 특정 배열 방에만 데이터가 몰리게 되면 다른 배열의 방들은 텅텅 비게 되는데 이렇게 되면 공간 효율이 떨어진다. 그렇기 때문에 해시코드를 배열 방에 분배할 때, 규칙을 만드는 것이 매우 중요하다. 이게 바로 해시함수의 알고리즘이다.

 

알고리즘의 효율이 나쁠 때, 특정 배열 방에만 데이터가 몰리는 것을 충돌이 일어난다고 표현한다. 해시테이블의 장점은 데이터 검색 시간이 O(1)만큼 걸린다는 것인데 충돌이 많은 경우에는 최대 검색 시간이 O(N)까지 걸릴 수도 있다. 특정 배열 방에만 데이터가 몰리면 그 안에 있는 모든 데이터를 뒤져봐야 하기 때문이다.

 

따라서 해시함수의 알고리즘은 입력 받은 key 값을 통해 만든 해시코드가 배열 방들에 얼마나 골고루 분배되는지에 따라 좋은 알고리즘인 지, 아닌 지가 결정 된다.

 

 

 

해시충돌

1. 해시함수는 서로 다른 key 값으로 동일한 해시코드를 만들어내기도 한다. 그 이유는 key 값은 문자열이고 그 가지 수가 무한한데 해시코드는 정수 범위만큼만 제공 가능하기 때문이다. (해시코드를 반환하는 hashCode() 메소드의 리턴 타입이 int형이다) 즉, 해시코드는 정수 범위(2^32)만큼만 제공한다. 논리적으로 생성 가능한 객체의 수가 2^32보다 많기 때문에 알고리즘이 아무리 좋아도 서로 다른 어떤 key들은 중복되는 해시코드를 가질 수 밖에 없다.
   
   
   HashMap을 비롯한 많은 해시함수를 사용하는 associate array 구현체에서는 메모리 절약을 위해서 해시함수가 표현할 수 있는 정수 범위 |N|보다 작은 M개 size를 가지고 있는 배열만을 사용한다. 따라서 객체(X)에 대한 해시코드를 배열의 크기로 나눈 나머지 값을 배열의 index로 사용한다.
   

int index = X.hashCode() % M;

 

 

 

2. 해시함수가 서로 다른 key 값으로 서로 다른 해시코드를 만들어 냈는데 같은 방(same index)에 배정 받는 경우도 있다. 배열 방의 개수가 한정 되어있기 때문이다.

 

 

이렇게 하나의 배열 방에 겹쳐서 배정 되는 모든 경우를 모두 충돌이라고 부른다. 이 충돌을 최소화 하기 위해서 좋은 해시 알고리즘을 만드는 것은 해시테이블에서 매우 중요한 포인트이다.

 

 

 

해시충돌 핸들링 하는 방법

해시충돌이 발생하더라도 키-값 쌍 데이터를 잘 저장하고 조회할 수 있게 하는 방식에는 대표적으로 두 가지가 있다.

 

 

1. Open Addressing
2. Separate Chaining

 

 

Open Addressing

• 데이터를 삽입하려는 배열 방이 이미 사용 중인 경우, 다른 배열 방에 해당 데이터를 삽입하는 방식이다.
• HashMap에서 remove() 메소드는 매우 빈번하게 호출 될 수 있는데 이 방식은 데이터를 삭제할 때, 비효율적이다.
• HashMap에 저장된 키-값 쌍 개수가 일정 개수 이상으로 많아지면, 일반적으로 Open Addressing은 Separate Chaining보다 느리다. 해시버킷을 채운 밀도가 높아질수록 Worst Case O(M) 발생 빈도가 더 높아지기 때문이다.

 

 

 

Separate Chaining

• 각 배열의 요소는 인덱스가 같은 해시버킷을 연결한 LinkedList의 첫 부분(head)이다.
• Java HashMap에서 사용하는 방식이다.
• 데이터의 개수가 일정 개수 이상일 때에는 LinkedList 대신 Tree를 사용하는 것이 성능상 좋다.
• LinkedList를 사용할 것인가, 트리를 사용할 것인가에 대한 기준은 하나의 해시버킷에 할당된 키-값 쌍의 개수이다. Java8 HashMap에서는 상수 형태로 기준을 정하고 있다. 즉, 하나의 해시버킷에 8개의 키-값 쌍이 모이면 LinkedList를 Tree로 변경한다.
  
  만약 해당 버킷에 있는 데이터를 삭제하여 데이터 개수가 6개가 되면 다시 LinkedList로 변경한다. 왜냐하면 Tree는 LinkedList보다 메모리 사용량이 많고 데이터의 개수가 적을 때, Tree와 LinkedList의 Worst Case 수행 시간 차이를 비교하는 것은 별 의미가 없기 때문이다.
• Java8 HashMap에서는 Entry 클래스 대신 Node 클래스를 사용한다.

 

 

 

HashTable 아주 간단하게 구현하기

 

1. key 값으로 입력 받은 문자열의 각 아스키 값을 더해서 해시코드를 만든다. (getHashCode(key))

 

 

 

2. 해시코드를 배열의 index로 환산한다. (converToIndex(hashCode))

• 고정 된 크기의 배열을 우선 선언한다.

 

 

3. 환산 된 index 방에 value 값을 할당한다.

• 위 예제는 데이터들이 배열 방에 그리 골고루 분배 되지 않아 좋은 해시 알고리즘은 아니다.
• 위 예제와 같은 충돌이 생기는 경우를 대비하여 배열 방 안에 LinkedList를 선언한다. 데이터가 배열 방에 할당될 때마다 LinkedList 안에 데이터를 추가한다.

 

ℹ 만약 검색 요청이 들어왔을 때, 검색할 key 값을 해시코드로 만들고 배열의 index로 환산해서 해당 index의 배열 방에 LinkedList를 순회하며 데이터를 찾는다.

 

 

 

해시버킷 동적 확장

배열의 사이즈가 적다면 메모리 사용을 아낄 수 있지만 해시충돌로 인해 성능상 손실이 발생한다. 그래서 HashMap은 키-값 쌍 데이터 개수가 일정 개수 이상이 되면, 배열 사이즈를 2배로 늘린다. 이렇게 배열 사이즈를 늘리면 해시 충돌로 인한 성능 손실을 어느 정도 해결할 수 있다.

 

해시버킷 개수의 기본값은 16이고, 데이터의 개수가 임계점에 다다를 때마다 해시버킷 크기를 2배씩 증가시킨다. 버킷의 최대 개수는 230개다. 그런데 이렇게 버킷 개수가 2배로 증가할 때마다, 모든 키-값 데이터를 읽어 새로운 Separate Chaining을 구성해야 하는 문제가 있다.

 

HashMap 생성자의 파라미터로 '초기 해시버킷 개수'를 지정할 수 있다. 해당 HashMap 객체에 저장될 데이터의 개수가 어느 정도인지 예측 가능한 경우에는 이를 생성자의 인자로 지정하면 불필요하게 Separate Chaining을 재구성하지 않아도 된다.

 

해시버킷 크기를 2배로 확장하는 임계점은 현재 데이터 개수가 load factor * 현재 해시버킷 개수에 다다를 때이다. 이 load factor는 0.75 즉, 3/4이다. 이 load factor 또한 HashMap의 생성자를 통해 지정할 수 있다.

 

 

 

📚 참고
해쉬테이블(Hash Table)에 대해 알아보고 구현하기
Java HashMap은 어떻게 동작하는가?