Hash Table & Dictionary

Hash Table

• 효율적인 탐색(빠른 탐색)을 위한 자료구조
• key-value 쌍의 데이터를 입력 받음
• hash function에 key값을 입력으로 넣어 얻은 해시값을 위치로 지정하여 데이터 쌍(key-value)을 저장
• 저장, 삭제, 검색의 시간복잡도 O(1)
• Array List 또는 Array List+Linked List로 구현 가능 → 파이썬의 경우 Array List로 구현됨

Direct-address Table

• key 값이 index가 되는 테이블
• 낭비되는 메모리가 발생
• 문자열이 key로 들어오면 index로 사용 불가
• 이러한 문제를 해결하기 위해 Hash Table 사용

Collision

• 해시 테이블에서 인덱스 간 중복이 발생하는 것(충돌)
• Open Addressing, Seperate Chaining 기법이 있음

Open Addressing

• 충돌되면 바로 다음 인덱스에 저장

Dictionary

• key 값은 유일해야 함(중복x)
• (코테) 시간복잡도를 줄이기 위해 메모리를 사용 하는 것
• key in {} 사용이 핵심
  리스트의 경우 특정 값을 찾을 때, 하나씩 탐색하므로 O(n)이지만, 해시테이블은 O(1)으로 바로 탐색

 

 

참고자료

https://www.inflearn.com/course/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9E%85%EB%AC%B8-%ED%8C%8C%EC%9D%B4%EC%8D%AC