[C++] Unordered_map

c#,java에서 hash_map이라고 불리는 자료구조가 c++에서는 unordered_map으로 사용되고 있다. (기존에 사용되는 hash_map 용어들과 충돌을 피하려고 이름을 이렇게 명명했다는 얘기가 있다.)

 

hash라는 자료구조 자체가 특정 키를 넣어주기만 하면 특정 값이 나오는 자료구조이고 key를 알고 있는 경우 시간 복잡도가 O(1)으로 아주 좋은 성능을 내고 있는 자료구조이다.

 

하지만, 설계에 따라 O(N)의 시간 복잡도를 가질 수도 있다. 따라서 제대로 구현을 하지 못하면 안쓰는 것만 못한 결과를 초래하게 된다. 그렇다. 구현을 해야한다. 이것을 말하려고 했는데, c++의 Unordered_map은 원시 자료형에 대해서는 key값을 사용하는데 문제가 없지만 사용자가 정의한 객체를 key 값으로 사용하게 될 경우 따로 작업을 해주어야 하는 부분이 있다.

 

세 가지 부분을 사용될 클래스에 정의 해줘야 한다.

먼저, (operator ==) 를 구현해줘야 하는데, 해쉬 충돌시 버켓의 원소들과 비교를 해야하기 때문이다.

bool operator==( const SocketAddress& inOther ) const
	{
		return ( mSockAddr.sa_family == AF_INET &&
				 GetAsSockAddrIn()->sin_port == inOther.GetAsSockAddrIn()->sin_port ) &&
				 ( GetIP4Ref() == inOther.GetIP4Ref() );
	}
// 멀티플레이어 게임 프로그래밍 코드 발췌

return 부분에서 비교되는 요소들은 GetHash()에 적용될 변수들의 계산으로 이루어져 있다. GetIP4Ref()가 접속하는 클라이언트의 ip를 나타내고 이 값들은 모든 클라이언트가 다른 값으로 정의가 되어있다. 

 

두 번째로, getHash()를 구현해 준다.

size_t GetHash() const
	{
		return ( GetIP4Ref() ) |
			( ( static_cast< uint32_t >( GetAsSockAddrIn()->sin_port ) ) << 13 ) |
			mSockAddr.sa_family;
	}

위에서도 언급했듯이 IP 값은 클라이언트마다 모두 다르기 때문에 전부 다른 값을 Return하게 될 것이다. 계산 값은 정해진게 아니라 가급적으로 해시 충돌을 피할 수 있는 연산이면 괜찮다.

 

마지막으로, 해시 함수를 계산하기 위한 함수 객체를 만들어 준다.

namespace std
{
	template<> struct hash< SocketAddress >
	{
		size_t operator()( const SocketAddress& inAddress ) const
		{
			return inAddress.GetHash();
		}
	};
}

 

템플릿 특수화를 통해 해당 객체가 unordered_map의 key로 들어갈 때 오류가 생기지 않고 제대로 들어갈 수 있게 됐다.

 

 

물론 .. 구현은 포폴에 해놨지만, 쓰진 않을 것 같다. 책에서는 address를 통해서 세션을 찾는 용으로 사용되었는데, 굳이 address를 사용하지 않아도 세션을 담고있는 deque에 인덱스를 통해서 세션을 충분히 찾아낼 수 있기 때문이다. 물론 유저의 데이터가 방대하다면 속도차이는 분명히 있을 것이다. 하지만 아직 시작 단계이기 때문에 필요하면 사용할 것 같다.

 

위에 ip를 사용한 방법으로 세션을 찾는것도 괜찮지만 내 생각에는 유저의 고유한 id나 번호를 지정해두고 key로 사용하는것도 나쁘지 않다고 생각한다. 내가 만드는 포폴의 경우에는 데이터베이스가 들어가기 때문에 굳이 ip를 통해 유저를 찾는 경우는 없을 것 같다. (그리고 애초에 메신저 프로그램이라 상대가 접속하지 않은 경우에도 데이터는 보내야 하고 단말기가 달라지는 경우도 생각을 해야하기 때문에 적절치 못하다고 생각한다.)

 

-수정-

위에서 클라이언트 ip 뿐만아니라 port 번호도 임의의 값으로 할당된다. 서버는 특정 포트를 명명하지만 클라이언트는 connect시 따로 포트를 명명하지 않아도 임의의 빈 포트로 할당되기 때문이다. 따라서 ip와 port의 조합은 절대 일치할 수 없는 수를 만들어 내기에 해시 값으로 사용하기 적당하다. 

 

궁금점

 

시프트 연산을 13비트 만큼 옮긴 이유를 모르겠다. 일단 시프팅을 통해 해시충돌을 막을 수 있다는 글들은 봤지만 왜 그런지에 대한 답은 보지 못했다. 예제 코드의 값이긴 한데 그냥 큰 수로 변환 시키기 위한 행위인지 .. 그렇다면 왜 애매한 13비트 시프팅을 했는지 이유를 알 길이 없다. ip port의 조합은 분명 겹칠 일이 없다. 근데 or 연산을 통해서 겹치지 않는다는 법이 있을까? 아주 미묘하게 맞아 떨어져서 그 값이 같다면? 그 때 operator ==의 리턴식이 맞아 떨어질까? 분명 다른 값들인데 그 or 조합이 같기 때문에 해시 충돌을 검사하지 못할 것 같다. 

 

일단 해당 문제는 throwbug와 네이버 카페에도 질문을 해놓은 상태인데.. 질문 자체가 껄끄러운게 누가 짜 놓은 코드를 왜 저렇게 짰을까 하고 물어보는거라 서로 답답한 면이 있다 ㅜ. 내 수준에서는 아직 이해가 되지않으니 기다릴수밖에