파이썬에는 dict( )라는 명령어가 있다. 맵 구조를 만들어준다.
a=dict()
a[3]=1
a[5]=3
a['abc']=5위에서 [ ]안에 들어가는 것이 key이고 =뒤에 있는 것이 value이다.
이는 다른 언어의 해시테이블, 해시맵과 유사한 느낌으로 사용 가능하다.
필자는 이 맵 구조를 대단히 좋아하는데,
배열에서는 어떠한 값들을 선형구조로 기록할 때, 인덱스로 접근하지만,
맵은 인덱스를 임의의 값으로 바꿔놓을 수 있기때문이다. 물론 인덱스 값만 바뀌고 배열의 성질을 그대로 갖는 것은 아니지만, 편의성이 좋아서 자주 사용한다.
a=[1,2,5,3]이라는 배열이 있다면, a[3]=3이고, a[2]=5다.
0~3이라는 인덱스를 통해 배열 안의 값에 접근할 수 있다. 그리고 이 인덱스는 항상 0부터 시작해서 배열 길이 - 1까지의 값을 갖는다. 즉 인덱스는 항상 0부터 시작하며 증가수열이다. 그리고 최대값이 정해져있다. 이미 그 자체로도 엄청난 활용도를 갖는다.
하지만 때로는 인덱스 숫자가 아닌 다른 값을 통해 접근하고 싶은 경우도 있다.
그럴 때, 제일 윗부분 코드블럭과 같이 임의의 key값을 고안하여 붙여주면 된다.
위의 그림은 똑같이, 3,7,6,-2라는 값을 담는 배열과 dict이다. (위의 그림에서 마지막 value는 -2인데, 오타입니다 ㅠㅠ)
배열에서는 인덱스 0~3을 통해 접근하며, dict에서는 임의의 key를 만들어주었고, 이를 통해 접근가능하다. key에는 항상 문자들만 써야되는 것도 아니고, 항상 숫자로만 이루어져야 하는것도 아니다. 음수도 가능하다. 배열에서는 a[1]이 두번째 원소를 가리켜서 7이 되지만, 아래에서는 a[1]이 6을 가리킴을 확인하자. 해시맵, 해시테이블에서 key는 일반적으로 중복이 불가하다. 즉 key는 식별자의 의미를 갖는다. 중복이 아니라면 어떠한 수나 문자도 key에 사용 가능하다.
또한, dict( )를 사용하여 아주 쉽게 링크드리스트를 구현할 수 있다.
위와 같이 일정 key안에 value로서 값이 아닌 dict()를 넣어주는 것이다. dict()안에 dict()가 들어가고 그 안에 계속 dict()를 넣는 식으로 구현가능하다. 문자열 처리에 있어 중요한 트라이(Trie)자료구조도 위와 같은 방식으로 구현할 수 있다. 트라이 자료구조와 관련 문제들도 추후에 포스팅하겠다.
맵 구조에서는 키(key)가 너무 많은 상황에 유의해야 한다. 일정한 범위를 만들어놓고 채우는 배열이나, 동적으로 크기가 변하는 벡터 등과 구조가 다르다. key가 하나 추가 될때 옆에 그냥 한개 쓰는 방식이 아니기에 load가 걸릴 수 있다. 위의 그림과 같이, key가 10만개를 넘어가는 식으로 많아지면, 성능이 떨어질 수 있다.
필자는 그래프 자료구조 구현에 dict를 사용했던 일이 많이 있었는데 정점이 너무 많아졌을 때 문제가 생긴다는 점을 통해 직접 경험하였다. 그래프 구현시에 인접리스트를 사용하면 되겠지만, dict사용시의 문제점을 아는 것도 중요하다.
그럴 때 위와 같은 방법으로 (가능하다면) 몇 개의 key를 묶어서 하나의 어떤 key안에 넣어주는 방식으로 구조를 만들어준다. 똑같이 10만개의 key를 담더라도 위와 같은 방법으로 담아주어 하나의 dict에 너무 많은 key가 몰리지 않도록 해준다면 성능이 엄청나게 좋아진다. 직접 코드 구현을 통해서 시간 차이를 확인하기 바란다.
마치 관계형 데이터베이스에서 join을 통해 액세스 하듯이, 하나의 dict를 다른 dict안에 넣어준 것이다. 그리고 key를 중첩시켜 목표값에 도달할 수 있다.
위를 통해, 간단한 구현, 활용법, 한계 등에 대해 조금씩 알아보았다. 이후, dict의 built-in 메서드(keys(), items()등등) 또는 그 외 추가사항을 덧붙이도록 하겠다.