HashTable 자료구조를 알아보자

근데 이제 Big O와 Hash collision을 곁들인

Java 컬렉션 프레임워크 중에는 HashMap이 있다. 자바스크립트의 Map이나 오브젝트를 생각하면 좀 쉽다. 간략히 말하자면 Key와 Value의 쌍으로 구성된 집합이다. 이 HashMap 공부를 하다가 HashTable자료구조와 Big O까지 공부를 하게 되었다. 줄줄이 포테이토로 연결되어 있거등. 모두 간단히(?) 정리하고 넘어가보자.

1. Java의 컬렉션 프레임워크 중 HashMap

HashMap은 Map 인터페이스의 구현체이다. key와 value의 쌍으로 저장을 한다. 데이터를 선언할 때는 아래와 같이 선언할 수 있다.

HashMap<String, String> Infos= new HashMap<>(); // 1번
names.put("name", "Hong")

HashMap<String, Integer> counts = new HashMap<>(); // 2번
counts.put("summer", 10)

1번 HashMap은 key가 String, value가 String인 Map이고, 

2번 HashMap은 key가 String, value가 Integer인 Map으로 이루어진 것이다. 

2. 자료구조 중 하나인 HashTable

HashMap은 큰 의미의 컴퓨터 자료구조로 봤을 때 HashTable 구조를 사용한라고 볼 수 있다. HashTable 자료구조는 뭘까? 간단히 이야기하면 "key"와 "value"로 짝을 지어주는 데이터 구조를 말한다. 그래서 이게 뭐냐구? 이렇게 하면 뭐가 좋을까? 왜 이런 자료구조를 사람들은 생각하게 되었을까? 결국은 성능때문이다.

다른 자료구조와 비교하기 위해 '배열' 자료구조를 생각해보자.

아래와 같은 배열이 있다고 생각해보자. 

내가 원하는 디저트 = [ "초콜릿", "커피", "케익", "아이스크림", "아이스아메리카노"]

배열 안에 "아이스크림"이 있는지 찾아보기 위해서는 첫번째부터 하나씩 대조를 해봐야된다. 

"초콜릿? 불일치 패스, 커피? 불일치 패스, 케익? 불일치 패스, 아이스크림? 오 일치!"

이런식으로 말이다. 벌써 물음표가 여러번 들어갔다. 몇번을 물어봐야 답에 접근할 수 있었다.

하지만 아래와 같이 자료구조를 바꾸면 어떨까?

내가 원하는 디저트 = {
   "초콜릿": true,
    "커피": true,
    "케익": true,
    "아이스크림": true,
    "아이스아메리카노": true
}

내가 원하는 디저트["아이스크림"] = true
내가 원하는 디저트["치킨"] = undefined

이런 자료구조에서는 원하는 값을 대입하기만 하면 바로 알 수 있다. 딱 1번만의 검색으로 내가 원하는 결과값을 얻을 수 있는 것이다. 이것이 바로 HashTable의 자료구조의 장점이다!

3. Big O (시간복잡도)

시간복잡도라고도 불리는 Big O 표기법은 크게 아래와 같은 종류가 있다.

O(N)
O(1)
O(log N)

갑자기 이 개념이 왜 튀어나왔느냐면, 위에서 얘기한것과 이어지기 때문이다.

O(N) 

내가 원하는 디저트 = [ "초콜릿", "커피", "케익", "아이스크림", "아이스아메리카노"]

=> "아이스크림"이 존재하는가? => 처음부터 차례로 대조해본다
=> "초콜릿"? 불일치 패스, 커피? 불일치 패스, 케익? 불일치 패스, 아이스크림? 오 일치! 

이렇게 처음부터 차례대로 검색하는 것을 선형검색이라고 한다. 선형검색을 할 때는 아이템의 개수에 따라서 소요시간이 늘어난다. 리스트 안에 "아이스크림"이 있는지 확인하려면, 최악의 경우 아이템의 개수가 N개면 N개만큼 시간이 걸릴것이다. 이때의 시간 복잡도는 O(N)이라고 한다. 포함된 아이템의 N개의 시간만큼 수행 시간을 요구하는 성능이라는 뜻으로 쓰인다.

O(1)

반면 HashTable의 자료구조에서는 어떨까?

내가 원하는 디저트["아이스크림"] = true

딱 1번만 조회하면 결과를 알 수 있다. 안에 데이터가 아무리 많아도 10개여도 100개여도 1000개여도 1번만에 알 수 있다. 이때의 시간 복잡도는 O(1)라고 한다. 이것은 일정한 상수 시간에 종료된다는 것을 의미한다. 

4. Hash Function

Key와 Value의 구조가 좋은건 알겠는데, 컴퓨터가 이것을 어떻게 처리해주는걸까? "name": "hong"이라는 데이터를 key와 value로 보낼때, 컴퓨터 메모리에는 엄밀히 말하면 "name"이라는 방은 없다. 그래서 무조건 숫자로 변환해서 저장해야 한다. 이때 일련의 규칙을 가지고 키값을 숫자로 변환시켜주는 함수를 Hash Function이라고 한다. 

근데 숫자의 결과값(해시값)이 같을 수도 있을거다. 예를 들어 "글자 수"로 해쉬값을 변환하기로 했다면 같은 글자수의 글자는 같은 키값을 가지게 되는거다. 이때 발생하는 것이 Hash Collision(해시 충돌)이다. (하지만 실제 해시 함수는 더 복잡하고 균일한 분포를 만들어내도록 설계된다.)

이때의 해결방법 중 하나는 체이닝이 있다. 체이닝이란, 그냥 같은 값에 할당된 값들을 연결시켜 놓는거다. 그러면 만약 4글자 key를 검색하려고 하면 4에 가서 찾게 되고 거기에 연결된 값이 여러개이면 그 안에서 찾는거다. 최악의 경우 O(N)의 시간이 걸릴 수도 있겠지만(모든 키가 같은 해시 값을 가질 경우), 그럴 일은 거의 없을 것이다. 많더라도 평균 O(1)의 그래프를 유지하게 될 것이다.

** 이 글은 아래 영상으로 공부한 후 작성한 글입니다. 영상으로 보면 훨씬 더 이해가 쏙쏙 잘된다. 둘다 너무 좋은 영상이라 꼭 시청하시길!

https://www.youtube.com/watch?v=BEVnxbxBqi8

https://www.youtube.com/watch?v=S7vni1hdsZE