• 매우매우매우매우매우 중요한 자료구조임
• 너의 코드르 더 빠르게 만들어줄꺼야

1. Hash Tables

정의

• Hash Tables는 Key Value System을 이용하여, 자료를 정리한다.
• 현실에서 자주 사용하는 예로는 사전이 있다. 단어(key)를 찾고 단어의 뜻(value)을 이해한다.
• Javascript => Object , Python => Dictionary, Go => map ...

Hash Tables과 Array의 차이

• Array
  아래와 같은 배열에서 데이터를 찾거나, 수정할 때의 시간복잡도는 O(n)이다.
  원하는 데이터를 찾을 때까지 선형검색으로 배열을 찾아야하고 이는 비효율적이다.

const Array = [
  {name: a },
  {height: 100},
  {age: 20},
  ...
]

• Hash Table
  Array와 다르게 Hash Table에서 원하는 데이터를 찾을 때는 바로 key값에 접근하면 된다. 어떠한 데이터를 검색해도 단 한번의 스텝을 거쳐서 찾을 수 있다. 이는 시간복잡도에서 상수(O(1))로 표현된다. 수정하나, 검색하나 단 한번의 스텝이 필요하다.

// age가 찾고싶다? 
// hash[age] => 22

const hash = {
  name: b,
  height: 190,
  age: 22,
  ...
}

2. 더 자세히

작동 원리

• Hash Tables에는 array 구조가 있다.
• 모든 Hash Tables 값들은 그 array에 있다.
• array의 값에 접근하기 위해서는 인덱스 값을 알아야한다.
• 그럼 배열하고 똑같자나? 아님 Hash Function이 있음
• Hash function은 우리가 찾고자 하는 키를 숫자로 바꾼다.
• 바로 그 숫자가 인덱스가 된다. 그 인덱스 주소를 가진 array에 value가 저장된다.

자자 정신이 아득하니 다시 정리하자

• hash table을 만들면 key, 해쉬함수, value가 있다.
• key를 해쉬함수에 넣어서 숫자를 발급받는다.
• 그리고 그 숫자를 인덱스로 value가 모여있는 배열에 저장한다.
• 해쉬함수는 어떤 기준으로 숫자를 발급하는가? key string의 길이를 기준으로 발급한다. ex) 'pizza' = 5 , 'age' = 3

자자 그럼 key값의 길이가 같은 경우가 있는 경우는?

이러한 경우를 해시 충돌(Collision)이라고 한다. 해결방법은 간단하다.

• 동일한 배열에 또다른 배열을 넣는것
  ex) 4번째 인덱스에 해시 충돌이 발생한다면 'key:value'가 함께 있는 배열을 그 안에 또 만든다. => 이 경우 시간복잡도가 달라진다. 선형검색이 필요