[자료 구조] 해시, 해시 함수, 해시 테이블 자료구조 총정리 (Feat.JAVA)

해시라는 단어는 암호화 관련 정보를 알아볼 때 주로 들었던 단어 같다.

오늘은 해시에 관련한 개념에 대해 총 정리를 해봐야겠다.

Java에서는 HashTable 과 HashMap 둘다 있는데, 이 포스팅에서는 둘을 구분 짓지는 않고, HashMap 기반으로 한 설명임을 알려드리는 바이다.

 

📌 해시 테이블 자료구조는 무엇인가?

해시(Hash) 단어 자체는 어떤 값을 일정 길이로 변환하는 기법이고, 해시 테이블은 그 해시 기법을 적용한 자료구조라고 할 수 있다.

간단하게 key-value 구조로 빠르게 검색을 할 수 있다는 것이 특징이다

대체 해시 테이블이 뭐길래 빠르게 검색을 할 수 있는 걸까?

자 우리가 친구의 전화번호를 검색할 수 있는 사이트를 만들었다고 치자.

검색창에 친구의 이름을 치면 전화번호가 나올 것이다.

이 때 이름 = Key, 전화번호 = Value 가 된다.

대체 이게 뭔데 빠르다는 거지? 

해시가 없다는 가정하에 전화번호를 다시 찾는다고 생각을 해보자.

// 일단 전화 번호 배열이 있을 것이다.
int phoneBook = new int[5]; 

// 찾고자 하는 이름
String name = "Kinzie";

/*
phonebook[name] 이런 식으로는 절대 찾을 수 없다.
*/

for (int i = 0; i < 5; i++) {
    if (phonebookName[i] = name){
    	phoneBook[i];
    }
}

전화번호 배열과 이름 배열이 필요할 것이고 전화번호부 길이 만큼 반복해서 일치하는 지 아닌지 확인 해가며 찾아야하는 수 밖에 없다.

-> 시간 복잡도는 O(N) 이라서 전화번호부에 1000명 10000명 이런 식으로 늘어가면 더 느려진다.

이런 장점 뿐만이 아니라 해시 테이블 구조는 Key와 Value에 모든 데이터 타입을 넣을 수 있기 때문에 굉장히 활용도가 높을 수 밖에 없다.

 

📌 해시 테이블은 어떻게 빠를 수 있지?

마치 int 배열에서 int[0] 이렇게 찾으면 0번째에 해당하는 value를 찾을 수 있는 것처럼,

해시 테이블도 phoneBook[name] 이렇게 찾으면 name에 해당하는 value를 찾을 수 있게 된다. 

이 글을 보는 모두가 알듯이 인덱스를 이용해서 int 배열에서 값을 찾는 것은 시간복잡도가 O(1)이다.

그럼 대체 해시 테이블 구조에서는 이런 일이 어떻게 가능하게 된 걸까?

 

해시 테이블의 Key 값을 해시값으로 변환 -> 해시값을 인덱스로 사용

이런 메커니즘이라서 1:1 매칭이 되고, 빠른 검색이 가능하게 된 것이다.

 

 

1️⃣ 왜 하필 이름이 해시 "테이블"일까?

지난 자료구조와 알고리즘 총정리 글에서 공부했듯이 자료구조는 데이터들의 집합이다.

근데 데이터 계에서 테이블의 생김새는 흡사 엑셀과 비슷하게 생겼다.

위키에서도 테이블(table)은 세로줄과 가로줄의 모델을 이용하여 정렬된 데이터 집합(값)의 모임이라고 정의하고 있다.

사실상 해시 테이블은 테이블의 형태가 맞기 때문이다.

1. Key 값이 해시 함수를 통해 해시 값으로 변환

2. 변환된 해시 값이 해시 테이블에서 인덱스로 쓰임

3. 이 인덱스의 한 row를 Bucket이라고 하고, 한 Bucket 안에는 여러 Slot이 있을 수 있다.

Bucket의 크기가 4, 슬롯의 크기가 3인 해시 테이블은 이런식으로 4*3 형태가 될 것이다.

이 때의 해시 테이블의 전체 저장 가능 공간은 12칸이 될 것이다.

 

 

2️⃣ 해시 충돌은 왜 생기는 걸까?

앞에서 키 값을 해시 함수를 통해 해시 값으로 변환해서 해시 테이블의 인덱스로서 쓰인다고 했다.

그림으로 한번 정리해보자.

여기 예제에서 주어진 키들은 서로 각각 다른 값이고, 서로 다른 해시 코드를 갖고 있다.

근데 해시 함수를 거쳐서 나온 해시 값 (= 해시 테이블의 인덱스 )은 같은 결과가 나왔다.

이것이 바로 해시 충돌 상황이다.

즉, 서로 다른 키 값이 해시 함수에 의해 같은 해시 값(해시 주소)을 갖게 되어서 생기는 문제이다.

해시 충돌은 해시 함수에 의해서도 발생될 수 있지만, 해시 테이블의 Bucket 사이즈가 유한해서 생길 수도 있다.

상황이야 어찌되었든, 저런 결과가 나오면 그것이 바로 해시 충돌이다.

해시 충돌이 발생하고, 버킷 안의 다른 슬롯에 저장되고, 그 슬롯마저 다 차버렸는데 또 데이터가 들어와야하는 경우는 오버플로우 상황이라고 한다.

 

그렇다면 해시 충돌이 안나게 해시 함수를 설정하면 될게 아니냐 할 수 있다.

서로 다른 객체 X와 Y가 있다고 했을때, X.hashCode() != Y.hashCode() 면 이때 사용하는 해시 함수를 완전한 해시 함수라고 한다.

근데 생각해보면, Integer, Long, Double 처럼 Number 객체야 그 고유의 값 자체를 해시 값으로 가질 수 있겠지만, String이나 POJO (Plain Old Java Object )등은 그게 불가능할 것이다. => 해시값이 겹칠 수 밖에 없음

 

어떤 완전한 해시 함수가 있다고 하더라도 HashMap에서 사용하기엔 힘들다.

HashMap 에서는 각 객체의 hashCode() 메서드가 반환하는 값을 사용하는데, 결과 자료형은 최대 int형의 정수이다.

public final int hashCode() {
    if (this.bits() >= 32) {
        return this.asInt();
    } else {
        byte[] bytes = this.getBytesInternal();
        int val = bytes[0] & 255;

        for(int i = 1; i < bytes.length; ++i) {
            val |= (bytes[i] & 255) << i * 8;
        }

        return val;
    }
}

32비트 자료형으로는 완전한 해시 함수를 만들 수 없다. 

실제로 생성 가능한 객체의 수는 2^32보단 많을 것이기 때문이다. 따라서 어차피 못 만들고 충돌 날거 실제 내부적으로는 메모리 절약을 위해 % 연산자를 활용해서 버킷의 수를 줄여버리는 등의 행위가 이루어진다.

그럼 이제 서로 다른 객체가 겹칠 확률이 더 올라가게 된다. 따라서 해시 충돌은 피할 수 없다.

 

💡 Tip

좋은 해시 함수는?

해시 함수는 Key를 해시 테이블의 버킷 주소(=index)로 변환(Hashing)하는 역할을 한다. 버킷의 사이즈는 유한하기 때문에 Key가 최대한 한 주소로 몰리지 않도록 해야한다. 즉, 버킷이 8개가 있다면 각 버킷이 Key에 대응될 확률이 모두 동일하게 1/8 씩 차지하는 것이 좋은 것이다. 이런 함수를 균등 해시 함수(uniform hash function)라고 한다.

대표적 해시 함수 기법에는 중간제곱법(mid-squre method), 나눗셈법(division method), 숫자분석법(digit analysis method), 접지법(folding method) 등이 있다.

 

 

해시 충돌 해결 방안 1. Separate Chaining ( 개별 체이닝 )

위에서 살짝 맛봤던 slot의 개념으로 LinkedList를 활용해서 해결하는 것이다. 

1. 해시 충돌이 발생하면  LinkedList로 노드를 추가하여 연결하기 때문에 크기 제한에 있어서 자유롭다.
2. 데이터를 검색할 때는 Key에 대한 index를 구하고, index가 가리키고 있는 LinkedList를 선형 검색해서, 해당 Key에 대한 데이터가 있는지 확인 후에 리턴하게 된다.
3. 삭제 또한 비슷하다. 선형 검색해서 해당 노드를 삭제 처리하면 된다.
4. 동일한 해시 값을 가진 항목들은 하나의 리스트로 관리되기 때문에, 다른 슬롯에 영향을 주지 않는다. 이로 인해 클러스터링(인접한 슬롯들이 가득 차게 되는 현상)이 발생하지 않는다.
5. 해시 함수에 대해 독립성이 있다. 해시 함수가 동일한 해시 값을 반환하는 경우에만 충돌이 발생하며, 이 충돌은 단순히 해당 슬롯의 리스트에 추가하는 방식으로 처리된다. 따라서, 해시 함수의 분포가 좋지 않더라도(즉, 해시 값이 고르게 분포되지 않더라도) 클러스터링 문제를 일으키지 않는다.

 

💡 Tip

Java 8 부터는 하나의 해시 버킷에 8개의 키-쌍이 모이면 LinkedList를 Tree로 변경한다. 해시 충돌이 많이 일어나서 모든 키가 같은 해시값을 갖게되면 O(n)의 시간 복잡도를 가지게 되기 때문이다. 만약에 해당 버킷에 있는 데이터를 삭제하여 개수가 6개가 되면 다시 링크드 리스트로 변경한다. 2개의 차이를 두어 1개의 어떤 키-값 쌍이 반복적으로 삽입/삭제가 일어났을 때 트리-링크드리스트 변환으로 인한 성능저하를 예방했다.

따라서 내부 코드에서도 TreeNode를 사용하기 위해 Java 7에서 처럼 Entry 클래스가 아니라 Node클래스를 사용한다.

이 때 사용되는 트리는 Red-Black Tree인데, TreeMap과 구현이 거의 같다. 최악의 경우에도 탐색, 삽입, 삭제가 O(log n) 시간에 수행된다는 특징이 있다. 

 

 

해시 충돌 해결 방안 2. Open Addressing ( 개방 주소법 )

개방 주소법에서는 모든 키-값 쌍을 동일한 배열에 저장한다. 충돌이 발생했을 때 추가적인 데이터 구조를 사용하지 않고, 동일한 배열 내에서 빈 슬롯을 찾아 데이터를 저장한다. -> 슬롯의 크기가 1이라는 소리다.

충돌이 발생했을 때 다른 슬롯을 탐사(Probing)하여 빈 슬롯을 찾는 방식으로 충돌을 해결한다. 

데이터를 삭제하면 삭제된 공간은 Dummy Space로 활용된다.

Dummy Node는 실제 값을 가지지는 않지만, 검색할 때 다음 위치(인덱스)까지 연결해주는 역할을 한다.

하지만 삭제가 빈번히 일어나서 Dummy Node 수가 많아진 상태에서 검색할 경우에 많은 버킷(Bucket)을 연속적으로 검색해야한다.

따라서, 이 Dummy Node의 개수가 일정 수 이상이 되었을 경우에 주기적으로 새로운 배열을 만들어고 재해시(Rehash)를 해줘야 성능을 유지할 수 있다.

탐색 방법에 따라 다양한 개방 주소법이 존재한다. 대표적인 3가지를 알아보도록 하겠다.

 

 

1️⃣  선형 탐사 (Linear Probing)

가장 간단한 방식이다.

충돌이 일어난 그 위치에서 일정한 간격(ex 고정폭 1)으로 다음 슬롯을 순차적으로 탐색하여 빈 영역에 키를 저장하는 방식이다.

일반적으로 h(k,i)=(h(k)+i)mod m의 형태로 탐색하며, 여기서 h(k)는 키 k에 대한 해시 값, i는 탐사 단계, m은 해시 테이블의 크기이다.

Primary Clustering(1차 클러스터링: 특정 영역에 원소가 몰리는 현상) 에 취약하다.

• 선형 탐사는 충돌이 발생한 위치로부터 연속된 빈 슬롯을 찾기 때문에, 해시 테이블에 빈 공간이 연속적으로 존재할 때까지 이동한다.
• 이로 인해 여러 개의 충돌이 같은 범위 내에서 발생하면, 연속된 슬롯들이 채워지게 되어 클러스터(연속된 사용 슬롯)가 형성된다.
• 새로운 키가 삽입될 때 기존 클러스터와 충돌하면, 해당 키는 클러스터의 끝에 삽입된다. 
• 결과적으로 클러스터가 점점 더 길어진다. => 충돌 가능성도 높아진다. 최악의 경우 해시 테이블(Hash Table) 전체를 검색해야 하는 상황이 발생할 수 있다.

 

 

2️⃣ 이차 탐사 (Quadratic Probing)

선형 검색법(Linear Probing)에서 발생하는 1차 클러스터링(Primary Clustering) 문제를 제거하는 방법이다.

충돌이 발생하면 제곱만큼 건너뛴 버켓에 데이터를 삽입하는 방식이다. 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2², 3² 칸씩 옮기는 방식이다.

Secondary Clustering(2차 클러스터링: 여러 개의 원소가 동일한 초기 해시 함수값을 갖는 현상 )에 취약하다

• 일정한 탐사 거리가 제곱수로 증가하다보니, 특정한 충돌 패턴이 발생할 수 있다.
• 예를 들어, 특정 인덱스에서 충돌이 발생하면 그 다음 탐사 위치도 비슷한 거리에 위치할 가능성이 높아진다.
• 이는 연속된 슬롯에 여러 키가 모이게 되어 클러스터를 형성한다.

 

3️⃣ 이중 해싱 (Double Hashing)

하나의 해시 함수(Hash Function)에서 충돌이 발생하면 2차 해시 함수를 이용해 검색 이동 거리를 얻는 방법이다.

두 개의 서로 다른 해시 함수를 사용하여 충돌을 해결한다.

클러스터링 문제를 최소화 할 수 있다.

가장 많은 연산량을 요구한다.

 

Java에서는 해시테이블 자료구조에 대해 개별 체이닝 방식을 채택하고 있지만 오픈 어드레싱 방식을 취하는 언어도 있다.

 

 

📌 로드 팩터와 보조 해시 함수

로드 팩터와 성능, 리사이징 정리 하기 남음

로드 팩터와 리사이징

로드 팩터(Load Factor)가 뭘까?

항공 용어에서 기인한 것으로, 원래는 중량대비 비행체가 견딜 수 있는 최대 하중을 말한다.

이처럼 컴퓨터 공학에서도 용량 대비 데이터가 어느 정도 찼을 때 사이즈를 늘려주는 임계점을 뜻한다.

따라서 해시 테이블에도 당연히 로드 팩터가 존재 하는데, 

 

 

📌 Ref

https://en.wikipedia.org/wiki/Hash_table

https://velog.io/@fore0919/TIL-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%95%B4%EC%89%AC%ED%85%8C%EC%9D%B4%EB%B8%94Hash-Table

https://d2.naver.com/helloworld/831311

https://dev-kani.tistory.com/1

https://nlp.jbnu.ac.kr/AL/ch06.pdf