매핑 (Mapping)

매핑(mapping, 사상)은 한 집합(정의역)의 각 원소를 다른 집합(공역)의 원소 정확히 하나에 대응시키는 규칙으로, 수학에서 말하는 함수와 같은 뜻입니다. 정의역의 한 원소가 두 개 이상의 값에 대응한다면 그것은 매핑이 아니라 더 넓은 개념인 관계(relation)입니다.

자세히 알아보기

매핑 f: A → B는 A의 모든 원소 a에 대해 B 안의 값 f(a)를 하나씩 정해 줍니다. A를 정의역, B를 공역이라 하고, 실제로 나오는 값들의 모임 f(A)를 치역(상)이라고 합니다. 치역은 공역의 일부일 수도 있고 공역 전체일 수도 있습니다. 반대로 공역의 한 원소에 여러 정의역 원소가 몰리는 것은 허용됩니다.

매핑은 성질에 따라 세 가지로 나뉩니다.

• 단사(injective, 일대일): 서로 다른 입력은 항상 서로 다른 출력으로 갑니다. f(a₁) = f(a₂)이면 a₁ = a₂입니다.
• 전사(surjective, 위로의): 공역의 모든 원소가 어떤 입력의 값이 됩니다. 치역이 공역과 같습니다.
• 전단사(bijective, 일대일 대응): 단사이면서 전사입니다. 이때에만 역매핑 f⁻¹이 존재해 출력에서 입력을 거꾸로 되찾을 수 있습니다.

유한집합에서는 크기로 가능성이 정해집니다. 정의역이 공역보다 크면 단사가 될 수 없고(비둘기집 원리), 두 집합의 크기가 같으면 단사와 전사와 전단사가 모두 같은 말이 됩니다.

블록체인·암호화폐에서는

• S-box: 블록 암호의 치환 상자는 비트열을 비트열로 보내는 매핑입니다. AES의 S-box는 8비트 값 256개를 다시 256개로 보내는 전단사여서 복호화 때 역 S-box로 되돌릴 수 있습니다.
• 해시 함수: SHA-256은 길이가 거의 제한 없는 입력을 256비트 출력 하나로 보내는 매핑입니다. 입력 집합이 출력 집합보다 훨씬 크므로 단사일 수 없고 충돌은 반드시 존재합니다. 안전성은 충돌이 없다는 데가 아니라 충돌을 찾기가 계산상 어렵다는 데 있습니다.
• 스마트 계약의 mapping: 솔리디티(Solidity)의 mapping(address => uint256) 같은 자료형은 키마다 값 하나를 저장합니다. ERC-20 토큰의 잔액 표가 대표적이며, 한 번도 쓰지 않은 키를 읽으면 기본값 0이 나옵니다.

쉽게 말하면

학생마다 출석 번호를 하나씩 붙이는 것과 같습니다. 한 학생에게 번호가 두 개 붙으면 규칙이 성립하지 않습니다. 번호가 겹치지 않으면 단사이고, 준비한 번호가 하나도 남지 않으면 전사이며, 둘 다이면 번호만 보고 학생을 정확히 찾을 수 있는 전단사입니다.

예시

정수 집합에서 f(x) = 2x는 단사이지만 홀수가 값으로 나오지 않으므로 전사가 아닙니다. g(x) = x mod 10은 정수를 0부터 9까지의 10개 값으로 보내는 전사이지만, 3과 13이 같은 값 3으로 가므로 단사가 아닙니다.