즐겨보던 인스타 코딩선생님네 유튜브 강의 공부 겸 번역해보았다.
https://youtu.be/IOt4dS1IWWU?si=elvM_s1eQm6pc__a
Hash Table에 5칸이 있다고 생각해보자.
나는 'greg'라는 String을 이 Hash Table에 넣고 싶다.
0, 1, 2, 3, 4칸 중 어디에 넣어야 할 지 결정해야 한다.
Hash Function은 'greg'라는 String을 Index로 변환시켜 줄 것이다.
알파벳의 순서에 번호를 붙였다고 생각해보자.
g: 7
e: 5
r: 18
이 될 것이다.
'greg'=7 5 18 7이 될 것이다.
이 수를 모두 더 하여 7+5+18+7=32를 주어진 칸의 수 5로 나눈 나머지를 보자.
32 % 5 = 2
따라서 'greg'는 index 2 칸에 들어갈 것이다.
이런식으로 했을 때, 'gre'는 7+5+18=30으로 나머지 0, index 0에 들어가게 될 것이다.
그런데 만약, 'grg'를 이 테이블에 넣고 싶다면?
계산해보면 'grg'의 나머지는 2로 이미 'greg'가 들어가 있는 인덱스와 똑같다.
이 때 우리가 쓰는 것이 Seperate Chaining이다.
Seperate Chaining은 이어진 리스트를 이어지게 넣어주는 것이다.
이런 형식으로 말이다.
Hash Sets 또는 Hash Maps를 쓰는 이유가 뭘까?
바로 시간 복잡도 때문이다.
Hash Set를 사용하는 예시를 보자.
만약 지금처럼 String이 3개가 아니라 1,000,000개 있었더라면 우리는 아주 오랫동안 반복문을 돌려야 했을 것이다.
하지만 Hashing을 하게 되면, 'gre'를 단순하게 O(1)의 시간복잡도, constant time 내로 위치를 구할 수 있다.
좋은 Hash Function이라면 한 칸에 모든 data가 모여있지 않을 것이기 때문에 대부분 O(1)의 시간복잡도를 지닌다. 물론 가장 최악의 시나리오 일 때, 모든 data가 단 한 칸에 모여있다면 O(N)의 시간복잡도를 가지게 될 것이므로 "*O(1)"이라고 표현하는 것이 맞을 것이다.
lookup, add, delete 전부 O(1)를 쓰게 될 것이다.
Hash Map은 key:value 관계이다.
greg:7 이런식으로 저장되는데 key는 hashable 해야한다. value는 어떤 type이던 key와 연관성이 있으면 된다.
lookup, add, remove(del) 셋 다 O(1)의 대강 시간복잡도를 가질 것이다.
지금까지 Seperate Chaining을 통해 Collision을 막았다면, 이번엔 다른 방법으로 막아보자.
바로 Linear Probing이다.
겹치는 String이 있을 때 chain을 만들지 않고, 1 차이나는 공간에 넣어보자.
lookup을 해본다고 가정하자. grg를 찾으러 2에 갔는데 없네? 주변에 있나? 찾았다, 하면 true를 돌려주는 방식인 것이다.
여기서 주변에 있는 지 probing하는 것이 Linear probing이다.
이 방법도 마찬가지로 최악의 상황일 때 O(N)의 시간복잡도를 얻게 될 것이다.
만약 del를 하게 되면, del한 data에 rely하고 있는 어떤 값들은 찾지 못하는 상태가 될 수 있으므로, 지우게 되면 -1처럼 어떤 표시를 남겨두어 hashing이 진행되도록 해야 한다.
이 방법은 이제까지 했던 Hash Sets, Hash Maps Operation과 같다. 다만 Hash Table이 이들을 implement 할 뿐이다.
여전히 이 두 방법 모두 lookup할 때는 항상 constant time이 된다.
무엇이 Hashable 할까?
- Strings
- Integers
- Tuples (1,2 3)=frozen array
NOT HASHABLE?
- Arrays
- Dictionaries
Hashable할 때는 Immutable, Not Hashable할 땐 Mutable하다는 특징이 있다.
코드를 통해 알아보자.
: NEXT EPISODE LINK 공개 예정
