Hash Tables

Hash Tables 란?

Hash Tables는 Key, Value System을 이용하여 자료를 정리 하는 기법
Ex) 사전, Object(JavaScript), Dictionary(Python), Map(Go)

시간 복잡도 비교

• Array
  • O(N)
    • 아이템이 많을 수록 찾는 시간이 오래걸린다.
• Hash Table
  • O(1)
    • 찾는 Key 가 바로 Hash Table에서 사용되는 배열의 Index이므로 바로 데이터를 가져 올수있다.

원리

Hash Table 에는 Array 를 사용한다. 하지만 기존의 Array와 다르게 Hash Function을 사용하여 데이터를 관리 하게 된다.

Hash function을 사용하여 Key를 숫자로 변환 하고 이 숫자를 Index로 사용한다.

그래서 기존의 Array와 다르게 검색 속도가 엄청 빠르다

(Key -> Index변환(Hash Function 사용) -> Index로 데이터 가져옴)

따라서 Hash Table에서는 중복이 허용 되지 않는다.

---

참고 자료

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