solidity 의 hash table

Solidity에서 자주 쓰는 mapping 타입은 내부적으로 해시 테이블처럼 동작하지만, 우리가 일반적으로 아는 HashMap 자료구조와는 구조도, 처리 방식도 매우 다릅니다.

이번에는 Solidity의 mapping이:
• 어떻게 데이터를 저장하고
• 어떤 해시 함수를 사용하며
• 충돌 시 어떻게 대응하는지
를 EVM 관점에서 최대한 자세하게 설명드릴게요.

⸻

🧠 Solidity의 mapping은 어떻게 작동할까?

mapping(address => uint256) public balances;

이 코드는 balances[addr] 값을 EVM의 스토리지 슬롯에 해시 계산을 통해 저장하는 구조입니다.

⸻

✅ 기본 작동 원리

Solidity에서 mapping(KeyType => ValueType)은 실제로는 다음과 같이 동작합니다:

storage slot = keccak256(encode(key) . encode(mappingSlot))

•    key: 검색할 주소 등
•    mappingSlot: 해당 mapping 자체가 선언된 스토리지 위치(index)
•    . : 붙여쓴다는 의미 (ABI encodePacked 방식)

⸻

🔎 예시

contract Example {
    mapping(address => uint256) public balances; // 슬롯 0
}

balances[0xAbc...123] 은
👉 keccak256(abi.encodePacked(address, uint256(0))) 에 저장됨

⸻

🔐 해시 함수: keccak256

Solidity는 모든 mapping 키 계산에 keccak256을 사용합니다.

keccak256(abi.encodePacked(key, mappingSlot))

•    강력한 충돌 방지 특성을 가진 SHA3 기반 해시 함수
•    Solidity / EVM에서 기본 제공

⸻

❓ 충돌(collision)은 어떻게 처리하나요?

✅ 답: 애초에 충돌이 “거의 발생하지 않도록” 설계되어 있음
• Solidity의 keccak256는 256비트의 해시 공간을 사용
• mapping은 해시 테이블처럼 보이지만 실제 테이블을 만들지 않음
• 각 키-슬롯 조합은 고유한 위치에 바로 접근하는 방식이라,
충돌 해결 로직이 필요 없음 (open addressing, chaining 없음)

📌 다시 말해:

충돌이 발생해도 별도로 관리하거나 저장된 값이 엉키는 일은 없습니다.
단지 다른 슬롯 주소에 저장될 뿐이죠.

⸻

📦 EVM 저장 구조 (스토리지 관점)

예시:

contract Example {
    uint public normalValue; // slot 0
    mapping(address => uint256) public balances; // slot 1
}

이 경우 balances[msg.sender]는 다음과 같이 계산됩니다:

slot = keccak256(abi.encodePacked(key, slotOfBalances)) = keccak256(msg.sender ++ 1)

해당 슬롯에 바로 접근하여 값을 읽거나 씁니다.

⸻

🔧 복합 Key 구조는?

Solidity는 아래처럼 중첩 mapping도 허용합니다:

mapping(address => mapping(uint256 => uint256)) public userVotes;

이 경우:

userVotes[A][B] → slot = keccak256(B ++ keccak256(A ++ mappingSlot))

즉, 깊이에 따라 keccak256가 중첩됩니다.

⸻

📊 장점 vs 단점

항목	장점	단점
✅ 가변성	동적으로 키 추가 가능	키 목록을 알 수 없음
✅ 읽기 속도	O(1) 해시 기반 접근	반복 불가 (no length, no iterator)
✅ 충돌	keccak 기반으로 거의 없음	충돌 해결 전략 없음 (필요도 없음)
❌ 데이터 순회	불가 (off-chain에서 indexing 필요)	---

⸻

📚 보너스: 왜 mapping은 iterable 하지 않나요?

Solidity에서 mapping은 키 목록을 저장하지 않기 때문에:

// ❌ 불가능
for (uint i = 0; i < balances.length; i++) { ... }

✔️ 이걸 해결하려면, 보통은 별도로 address[] public keys; 등을 두어 수동으로 트래킹해야 해요.

⸻

✅ 요약

항목	설명
해시 함수	keccak256 (SHA3)
저장 위치	keccak256(key ++ mappingSlot)
충돌 처리	없음 (슬롯 자체가 다르므로 발생하지 않음)
반복 가능 여부	❌ 직접 순회 불가
읽기 속도	O(1) 접근
쓰기 방식	storage 슬롯 직접 접근