[노씨데브 킬링캠프] 5주차 - 이론강의: 해시테이블

자바에서는 Hashmap
파이썬에서는 Dictionary 라고 표현

HashTable 의 특성

키 값으로 Int 형 뿐만아닌 String 타입도 줄 수 있다.

Direct-address Table

키값 자체가 바로 인덱스 값을 지칭하는 테이블
[ 문제점 ]

학번을 키값으로 하여 바로 인덱스를 저장한다고 하면, 메모리의 낭비가 발생 (0번,1번,2번...)

문자로 된 값은 인덱스로 지칭할 수 없음

HashTable의 등장

Hash Function 을 매개체로 활용하여 키값을 1대1 대응되는 index 값에 저장, 1대1 대응이 되지 않으면 해시충돌(Hash Collision)이 발생

문자열도 처리가능

코딩테스트에서의 Hashtable

1. 시간복잡도를 줄일 수 있음
2. 문자열을 키값으로 활용할 수 있음