[자료구조] hash 관련 용어정리와 hash table

• hash 관련 용어정리
• hash table
• hash table의 장단점
• hash collision (해시 충돌) 
• 해시 알고리즘
• hash collision 해결법
• Hashtable, HashMap 공통점과 차이점

 

---

 

자바 Object 클래스에 선언된 메서드들은 스레드와 객체를 처리하기 위한 메서드로 나눠져있다.

 

객체를 처리하기 위한 메서드에는

toString(), equals(), hashCode(), getClass(), clone(), finalize() 이 있다.

그 중, hashCode() 메서드는 객체에 대한 해시코드 값을 int 형태로 리턴한다는 설명을 봤고

hash code가 무엇을 의미하는지 자세히 알아보기로 했다. 

 

hash code를 검색하면, hash, hashing, hash function.. 등과 같이 비슷하고 헷갈릴만한 용어들이 많이 나온다.

정리가 잘 된 블로그를 참고해서 나만의 용어로 바꿔 정리해보려고 한다. 

 

---

hash code / hash /  hashing / hash function / hash 알고리즘 /  hash table ..

hash가 들어간 용어를 정리해보자.

일단 궁금했던 hash code가 무엇이며 어떤 용도로 쓰이는지 부터 알면 좋을 것 같다.

 

hash code란 객체를 식별하기 위한 고정된 길이의 고유한 정수값이다. 자바에서 Object 클래스의 hashCode() 메서드는 객체의 주소값을 변환해서 고유한 해시코드 값을 만든다. 이 hash code는 동일한 객체인지 확인할 때 equals와 함께 사용하고 해시코드를 해시(hash), 해시값(hash value)라고도 부른다. 

 

hashing을 정의하기 전에, hash function을 먼저 알아보자.

hash function는 임의의 길이인 key를 고정된 길이의 hash로 변경해주는 역할을 한다. 이 과정을 hashing이라고 한다. 해시함수에 Input으로 key를 넣어 Output으로 hash code(=hash)가 나오는 것이다.  결국 해시 함수는 key로 해시를 만들어내는 함수이자 hash 알고리즘이라고도 한다.

 

---

hash table

key, value가 1:1로 매핑된 형태로 이루어진 자료구조이다.

일반적으로 데이터 추가/삭제/검색이 O(1)의 시간복잡도를 가지는 좋은 perfomance를 기대하며 해시 테이블을 사용하고 순서를 보장하지 않는다.

 

1. key : hash function의 Input, 해싱을 통해 해시로 변환된다.

2. value : 버킷에 최종적으로 저장되는 값

3. hash(=hash code, hash value)

• key를 해싱해서 얻어진 고정된 크기의 정수값 (버킷 배열의 인덱스와 다름)

4. index 

• 버킷 배열의 인덱스
• hash를 capacity(버킷의 크기)로 나눈 나머지

5. buckets 또는 slot

• 배열 형태의 value 저장소
• HashMap default capacity : 16

 

 

hash table 자료구조의 장단점 

장점 

• 해시 충돌이 없다면, 1Step으로 매우 빠르게 데이터를 추가/삭제/조회할 수 있다. O(1)
• Key값의 중복확인이 쉽다. (캐시 구현에 사용)
  
  

단점

• hash table은 미리 buckets의 크기를 만들어 놓아야하므로 공간 효율성이 떨어진다. 
• 해시 충돌 해결을 위한 별도의 자료구조가 필요하다. (연결리스트)
• 해시 충돌이 발생했을 때, 최악의 경우 시간복잡도는 O(N)에 가까워진다.
• 해시함수가 복잡하면, hash를 만들어내는데 오랜 시간이 걸린다(hash function의 의존도가 높다).

 

---

hash collision (해시 충돌)

해시 충돌을 정의하기 전에, 아래 두 내용을 이해해야 한다.

1. key값이 다르더라도,  동일한 해시코드를 가질 수 있다.
2. 해시코드가 다르더라도, 동일한 버킷의 index를 가질 수 있다.

다른 key값이 동일한 해시코드를 가질 수 있는 이유는 무엇일까?

: 우리가 Object를 생성하는 데는 제한이 없고, Integer를 생성하는 데는 범위가 지정돼 있으므로 제한이 따른다.

즉, Input으로 주는 값(객체)는 무한하지만 Output으로 받는 값(정수)는 무한하지 않기 때문이다.

 

다른 해시코드가 동일한 index를 가질 수 있는 이유는 무엇일까?

: 버킷의 인덱스는 해시값을 버킷의 크기만큼 나눈 나머지가 된다고 위에서 언급했다.

예를 들어, A와 B객체의 해시코드는 각각 15, 45이고 버킷의 크기는 10이라고 가정해보자.

두 해시코드는 다르지만 같은 5라는 인덱스를 가진다. 즉, 버킷의 5번째 방에 A와 B의 value 값이 같이 저장돼야 한다는 의미

 

 

그래서 결국,

해시 충돌이란?

해시코드가 같다면 반드시 버킷인덱스가 같고, 해시코드가 달라도 버킷인덱스가 같을 수 있기 때문에, 

같은 버킷에 복수의 데이터를 넣어야하는 경우를 '해시 충돌(hash collition)'이라고 정의하는게 맞다고 생각한다!

 

 

---

당연히 충돌이 적게 발생할수록 좋고, 불가피할 경우 해시값을 고르게 만들어내 충돌이 균등하게 발생하도록 하는 것이 중요하다.

해싱을 통해 해시를 얻는 해시 알고리즘(해시 함수)에는 여러가지 방식이 존재한다.

해시 테이블에 사용되는 대표 해시 함수에는  4가지가 있다. 

1. Division Method : 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산한다.
2. Digit Folding : Key의 각 문자를 ASCII 코드로 바꾸고 값을 합한 데이터를 인덱스로 사용하는 방법이다.
3. Multiplication Method : 숫자로 된 Key값 K와 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같은 계산을 해준다. (h(k)=(kAmod1) × m)
4. Univeral Hashing : 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법이다.

 

---

대표적인 두 가지 충돌 해결법

 

개방 해싱(Open Hashing) : 해시 테이블 공간 외에서 충돌 해결

폐쇄 해싱(Close Hashing) : 해시 테이블 공간 안에서 충돌 해결

 

1. Separate Chaining

해시 테이블 저장공간 외에 공간을 별도로 만드는 개방 해싱(Open Hashing) 기법 중 하나이다.

링크드 리스트라는 자료구조를 사용해서 데이터를 연결시켜 저장한다. 

 

ex)

위 그림을 보면 John과 Sandra의 버켓의 인덱스가 152로 동일해 충돌하게 된 경우인데,
이 때, John 뒤에 Sandra를 연결함으로써 충돌을 처리한다.

 

 

2. Open Addressing

해시 테이블 내에서 충돌을 해결하는 폐쇄 해싱 기법 중 하나로,

비어있는 버켓을 찾아 이동해 데이터를 저장하는 방식이다. 

 

ex)

John과 Sandra의 버켓의 인덱스가 152로 동일해 충돌하게 된 경우인데,
Sandra는 비어있는 153 인덱스에 value를 저장함으로써 충돌을 처리한다.

 

 

---

Hashtable, HashMap 공통점

• Map 인터페이스의 구현체로 Key, Value가 1:1로 매핑된 형태를 띄는 자료구조이다.
• 키에 대한 해시 값을 사용하여 value를 저장/조회/삭제, <key, value> 개수에 따라 동적으로 크기가 증가하는 연관배열

 

연관배열(associative array)이란?

: 키 하나와 값 하나가 연관되어 있으며 키를 통해 연관되는 값을 얻는 자료구조 (대표적으로 Map, Dictionary)

 

 

Hashtable, HashMap 차이점

1. Thread-safe 여부

HashMap 

• Thread safe하지 않다 (싱글 스레드 환경에서 사용)

: 동기화 처리를 하지 않기 때문에, 데이터 탐색 속도가 HashTable과 ConcurrentHashMap보다 빠르지만, 안정성이 떨어진다.

 

 

HashTable

• Thread safe (멀티 스레드 환경에서 사용)

: 데이터를 다루는 메소드인 get(), put(), remove() 등에 synchronized 키워드가 선언돼있다. 이는 메소드를 호출하기 전에 스레드간 동기화 락을 걸어, 멀티 스레드 환경에서도 데이터의 무결성을 보장한다. 

 

 

2. key, value에 null 허용여부

HashMap

• key, value에 null을 허용

 

HashTable

• key, value에 null을 허용하지 않는다.

 

 

 

 

 

참고자료 

https://mangkyu.tistory.com/102

https://go-coding.tistory.com/30

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