개발자 취준 기록 34 - Hash(Table·Map·Set)

HashTable

HashTable은 Hash를 이용하여 연관 배열을 구현한 자료구조이다.

해시 함수를 통해 key를 해시값으로 매핑하고, 이 해시값을 인덱스로 하여 value값을 key와 함께 저장하여 검색을 빠르게 하기 위한 자료구조이다.

 

아래 그림과 같이 key는 이름, value는 전화번호를 저장한다고 가정해 보자

그림1. HashTable

위 그림을 보면 John Smith의 데이터를 저장할 때 index = hash_function("John Smith") % 16을 통해서 index값을 구해내고, array[index] = "521-1234"를 저장한다.

 

hash_function를 통해 key에 대한 index값을 구하고 해당 index값을 주소로 buckets에 값(value)을 저장한다.

이런 형식으로 데이터를 저장하게 되면, key에 대한 value를 찾을 때 hash_function을 한 번만 실행하면 array 내 저장된 index 값을 찾아낼 수 있기 때문에 데이터의 저장과 삭제가 빠르다.

해시 충돌 처리 방식

위와 같은 hash_function을 사용할 경우 index의 값이 중복되는 경우가 발생할 수 있다.

그 경우에 해결하는 방법이 두 가지가 있는데,

1. Open Addressing
2. Separate Chaining

이다. 

1. Open Addressing

그림2. Open Addressing

index가 중복되었을 때 이전이나 다음 index 중에서 비어있는 곳에 value를 삽입하는 방식이다.

2. Separate Chaining

그림3. Separate Chaining

중복된 index값이 가리키고 있는 LinkedList에 Node를 추가해서 값을 추가한다.

비교

Open Addressing 방식은 Linear 구조상 데이터를 삭제할 때 효율적이지 않기 때문에 Java의 HashMap에서는 Separate Chaining 방식을 채택하여 사용하고 있다. (Linear 구조이기 때문에 해당 index가 삭제되면 다음 index와 연결해 주기 위해 dummy 데이터를 삽입해 주어서 비효율적이다.)

---

HashMap

Map 인터페이스를 구현한 컬렉션이다.

key, value의 형태로 데이터가 저장되며, key 기반으로 데이터를 검색하기 때문에 key는 고윳값을 가진다. 그렇기 때문에 같은 key에 다른 value로 저장을 하게 되면 기존의 value는 삭제된다.

 

HashTable과 유사한 형태로 데이터를 저장하는 자료구조이다.

HashTable과의 차이점

• 동기화를 보장하지 못한다. (저장 순서와 출력 순서를 보장하지 않음)
• 비동기 방식이기에 속도가 훨씬 빠르다.
• key, value에 null값을 허용한다.
• 보조 해시 함수를 사용하고 있어 해시 충돌이 덜 발생한다.

보조 해시 함수
key의 해시 값을 변형하여 해시 충돌 가능성을 줄이는 것

static final int hash(Object key) { 
    int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 
}​

상위 16비트 값을 XOR 연산하는 매우 단순한 형태의 보조 해시 함수를 사용

---

HashSet

Set 인터페이스를 구현한 컬렉션이다.

HashSet은 내부적으로 HashMap으로 구현되어 있기 때문에 마찬가지로 HashTable과 유사한 형태의 자료구조이다.

key에 삽입되는 객체 그 자체를 값으로 저장하고, value에는 dummy 데이터를 저장하는 방식을 사용한다.

HashMap과의 차이점

• HashMap은 중복 value는 허용하지만, HashSet은 객체 데이터 자체를 저장하기 때문에 중복 value를 허용하지 않는다.
• 단 하나의 null값을 가질 수 있다.(중복이 허용되지 않기 때문에)
• HashMap은  put()으로 삽입하고 key-value 쌍의 객체가 생성되지만, HashSet은 add()로 삽입되고 key 객체와 value(dummy 데이터) 객체가 생성되어 HashMap보다 속도가 느리다.

---

참고

https://barbera.tistory.com/51

https://bcho.tistory.com/1072

https://siahn95.tistory.com/96