Hash Map

• Reference
• Reference2
• Reference3
• Insert/Find 기능이 O(1)의 Tiem Complexity를 가진다.
• Data Constructor가 Key-Value 관계를 가진다.
• Hash Map의 핵심은 hash function 이며 해당 Output을 조작하여 Bucket으로 설정해서 Linked List 구조로 둔다.
  • Insert/Find가 사실상 O(1)은 아니라 O(n)이라는 뜻이다.
• Bucket Size가 초과되면 Rehasing을 진행한다.

Example

• Two Sum 문제에서 아래와 같은 값들을 줬다고 해보자.

[13, 7, 5, 1, 3, 2]

• 더해서 10이되는 두 수들을 찾는 문제에서 Hash Map을 활용할 수 있다.
• 기존 Array 방식의 알고리즘에서 O(nlogn)의 TimeComplexity를 가졌지만, HashMap에서는 O(n)으로 끝낼 수 있다.
• Key를 10에서 해당 element를 뺀 값으로 하고, Value를 해당 Index로 두면 된다.

Key	Value
-3	0
3	1
5	2
9	3
7	4
8	5

• 이렇게 Hash Table을 두고 있으면 13인 경우 -3이 필요하고 계속해서 Key값을 채워나갈 것이다. 채워나갈 때, 3이라는 값의 필요한 수 7을 Key로 넣기전에 Hash Key에 3이 존재하므로 쌍이 존재한다는 의미이므로 빠르게 합이 10인 쌍을 찾아 낼 수 있는 것이다.
  • 다만, Space Complexity는 O(n)으로 늘어난다.

Example2

• Isomorphic의 경우를 생각해보자. 이러한 문제에서는 대응되는 Alphabet 쌍이 핵심이다. 하나의 문자열에대한 문자와 다른 문자열에 대한 문자를 Key-Value 관계로두고 판단하면된다.

aaaffh, xyzhhh
|Key|Value|
|--|--|
|a|x|
|a|y?|

• a는 이미 x와 매칭되어 있으므로 False ! Invalid !

Example3

• Anagram

nocodeprogram, promodernacog

Key	Value
n	1
...	...

• 각 단어의 개수를 세어주고 다른 문자열에서 다시 하나씩 빼주는 것이다.
• 모든 Value의 값이 0이면 Anagram인 것이다.
• O(n)의 Time Complexity로 해결이 가능한 것이다.