4장: 해시 테이블과 집합
해시 사용 시 성능과 보안 상충 지점
외부 입력을 받는 서비스에서는 해시도 보안 관점으로 봐야 합니다.
평소에는 빠르던 코드가 특정 패턴 입력에서 갑자기 느려질 수 있기 때문입니다.
충돌이 몰리면 평균 O(1) 가정이 깨지고 성능이 급격히 떨어질 수 있습니다.
그래서 질문을 바꿔야 합니다. 가장 빠른 해시가 무엇인가보다 우리 입력 환경에 어느 정도 방어가 필요한가를 우선 정해야 합니다. 여기서는 방어 수준과 성능 예산을 함께 맞추는 기준을 정리합니다.
핵심 개념: 해시 성능과 방어 모델
해시를 보안 관점으로 다룰 때는 성능 수치보다 입력 신뢰 수준을 우선 정해야 합니다. 현재 시스템이 신뢰 입력인지 비신뢰 입력인지 우선 표시하고 아래 개념을 연결해 보세요.
위협 모델은 어떤 공격과 이상 입력을 대비할지 미리 정한 가정입니다. 정확히는 시스템이 받는 입력의 신뢰 수준과 공격 가능성을 명시한 보안 설계 전제입니다. 내부 배치 데이터만 받는지, 외부 사용자 요청을 직접 받는지에 따라 해시 방어 수준이 달라집니다.
솔트(salt)는 해시 입력에 섞는 비밀 값입니다.
같은 키라도 결과 해시를 달라지게 만들어 충돌 유도 예측을 어렵게 만듭니다.
"user42"라는 같은 키도 솔트가 다르면 버킷 위치가 달라져 공격자가 패턴을 맞추기 어려워집니다.
로드 팩터와 재해시는 충돌 밀도를 관리하는 운영 지표와 대응 절차입니다.
로드 팩터는 원소 수 / 버킷 수이고, 임계치를 넘으면 재해시로 버킷을 다시 분배합니다.
예를 들어 로드 팩터가 0.9를 넘을 때 테이블을 2배로 키우면 긴 체인 길이를 줄일 수 있습니다.
해시 보안 장애 사례와 연결하기
충돌 공격은 평균 O(1) 가정을 무너뜨릴 수 있습니다.
특정 키를 의도적으로 만들어 같은 버킷으로 몰면 체이닝 길이가 늘어나 선형 성능으로 악화될 수 있습니다.
또한 보안을 과하게 강화하면 정상 트래픽에서도 지연이 커질 수 있습니다.
그래서 방어 수준과 성능 예산을 함께 관리해야 합니다.
충돌 방어 테스트로 빠르게 검증하기
학습 효율을 높이려면 오답 -> 디버깅 -> 교정 -> 검증 순서로 로그를 남기면서 진행하는 것이 가장 빠릅니다.
충돌 집중 입력이 들어올 때를 간단히 시뮬레이션해 봅니다.
- 버킷 수:
8 - 공격성 입력: 동일 버킷으로 몰리도록 설계된 키 100개
- 충돌 완화 장치가 없으면 특정 버킷 길이가 급증합니다.
- 조회/삽입 시간이 평균보다 크게 늘고 tail latency가 상승합니다.
- 솔트 해시, 재해시 임계치, 입력 정규화를 함께 적용해야 완화됩니다.
단순 해시와 솔트 해시 분포 비교
문제 의도: 입력 분포에 따라 일반 해시와 솔트 해시의 버킷 편차를 비교합니다.
입력 예시: 공통 접두/접미 패턴이 많은 문자열 키 집합
출력 예시: 버킷별 키 개수 분포
normalize는 같은 의미 키를 하나로 모으기 위해 공백/대소문자를 먼저 통일하는 단계입니다.
#include <cctype>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
string normalize(const string& s) {
string out;
for (char c : s) {
if (!isspace(static_cast<unsigned char>(c))) {
out.push_back(static_cast<char>(tolower(static_cast<unsigned char>(c))));
}
}
return out;
}
int simpleHash(const string& key) {
int h = 0;
for (char c : key) {
h = (h * 31 + static_cast<unsigned char>(c)) % 1000003;
}
return h;
}
int bucketIndex(const string& key, int bucketCount, bool useSalt) {
string raw = useSalt ? ("salt-" + key) : key;
return simpleHash(raw) % bucketCount;
}
vector<int> countDistribution(const vector<string>& keys, int bucketCount, bool useSalt) {
vector<int> counts(bucketCount, 0);
for (const string& raw : keys) {
string key = normalize(raw);
if (key.empty()) continue;
counts[bucketIndex(key, bucketCount, useSalt)]++;
}
return counts;
}
int maxCount(const vector<int>& counts) {
int mx = 0;
for (int x : counts) mx = max(mx, x);
return mx;
}
int main() {
vector<string> keys = {
"ADMIN", "admin", "Admin", "user-1", "user_1",
"cache", "Cache", "cache ", "token", "token2"
};
vector<int> plain = countDistribution(keys, 8, false);
vector<int> salted = countDistribution(keys, 8, true);
cout << "plain: ";
for (int x : plain) cout << x << " ";
cout << "\n";
cout << "salted: ";
for (int x : salted) cout << x << " ";
cout << "\n";
cout << "max bucket size -> plain=" << maxCount(plain)
<< ", salted=" << maxCount(salted) << "\n";
return 0;
}import java.util.*;
public class Main {
static String normalize(String s) {
return s.replaceAll("\\s+", "").toLowerCase();
}
static int simpleHash(String key) {
int h = 0;
for (char c : key.toCharArray()) {
h = (h * 31 + c) % 1_000_003;
}
return h;
}
static int bucketIndex(String key, int bucketCount, boolean useSalt) {
String raw = useSalt ? "salt-" + key : key;
return Math.floorMod(simpleHash(raw), bucketCount);
}
static List<Integer> countDistribution(List<String> keys, int bucketCount, boolean useSalt) {
List<Integer> counts = new ArrayList<>(Collections.nCopies(bucketCount, 0));
for (String raw : keys) {
String key = normalize(raw);
if (key.isEmpty()) continue;
int idx = bucketIndex(key, bucketCount, useSalt);
counts.set(idx, counts.get(idx) + 1);
}
return counts;
}
static int maxCount(List<Integer> counts) {
int mx = 0;
for (int x : counts) mx = Math.max(mx, x);
return mx;
}
public static void main(String[] args) {
List<String> keys = List.of(
"ADMIN", "admin", "Admin", "user-1", "user_1",
"cache", "Cache", "cache ", "token", "token2"
);
List<Integer> plain = countDistribution(keys, 8, false);
List<Integer> salted = countDistribution(keys, 8, true);
System.out.println("plain: " + plain);
System.out.println("salted: " + salted);
System.out.println(
"max bucket size -> plain=" + maxCount(plain) +
", salted=" + maxCount(salted)
);
}
}def normalize(text):
return "".join(ch.lower() for ch in text if not ch.isspace())
def simple_hash(key):
h = 0
for ch in key:
h = (h * 31 + ord(ch)) % 1_000_003
return h
def bucket_index(key, bucket_count, use_salt):
raw = f"salt-{key}" if use_salt else key
return simple_hash(raw) % bucket_count
def count_distribution(keys, bucket_count, use_salt):
counts = [0] * bucket_count
for raw in keys:
key = normalize(raw)
if not key:
continue
idx = bucket_index(key, bucket_count, use_salt)
counts[idx] += 1
return counts
keys = [
"ADMIN", "admin", "Admin", "user-1", "user_1",
"cache", "Cache", "cache ", "token", "token2",
]
plain = count_distribution(keys, 8, False)
salted = count_distribution(keys, 8, True)
print("plain:", plain)
print("salted:", salted)
print("max bucket size -> plain=", max(plain), ", salted=", max(salted))fn normalize(text: &str) -> String {
let mut out = String::new();
for ch in text.chars() {
if !ch.is_whitespace() {
for low in ch.to_lowercase() {
out.push(low);
}
}
}
out
}
fn simple_hash(key: &str) -> usize {
let mut h: usize = 0;
for b in key.as_bytes() {
h = (h * 31 + (*b as usize)) % 1_000_003;
}
h
}
fn bucket_index(key: &str, bucket_count: usize, use_salt: bool) -> usize {
let raw = if use_salt {
format!("salt-{key}")
} else {
key.to_string()
};
simple_hash(&raw) % bucket_count
}
fn count_distribution(keys: &[&str], bucket_count: usize, use_salt: bool) -> Vec<i32> {
let mut counts = vec![0; bucket_count];
for raw in keys {
let key = normalize(raw);
if key.is_empty() {
continue;
}
let idx = bucket_index(&key, bucket_count, use_salt);
counts[idx] += 1;
}
counts
}
fn max_count(values: &[i32]) -> i32 {
let mut best = 0;
for &value in values {
if value > best {
best = value;
}
}
best
}
fn main() {
let keys = [
"ADMIN", "admin", "Admin", "user-1", "user_1",
"cache", "Cache", "cache ", "token", "token2",
];
let plain = count_distribution(&keys, 8, false);
let salted = count_distribution(&keys, 8, true);
println!("plain: {:?}", plain);
println!("salted: {:?}", salted);
println!(
"max bucket size -> plain={}, salted={}",
max_count(&plain),
max_count(&salted)
);
}해시 성능/보안 결과 해시 충돌 징후 확인
예제 목적은 어떤 해시가 절대 우월하다는 결론이 아닙니다.
입력 정규화와 시드 적용이 분포에 어떤 영향을 주는지 확인하는 데 있습니다.
보안 해시는 보통 상수 비용이 증가하지만 예측 가능성을 낮출 수 있습니다.
- 평균 시간복잡도: 버킷 계산
O(1) - 최악 시간복잡도: 충돌 집중 시 버킷 탐색
O(N) - 공간복잡도:
O(N)
로드 팩터 기반 재해시 정책
문제 의도: 로드 팩터 임계치 기반 재해시가 장기 성능 안정화에 미치는 효과를 확인합니다.
입력 예시: 연속 삽입으로 로드 팩터를 임계치 이상으로 증가
출력 예시: 재해시 전후 버킷 수와 삽입/조회 지연 변화
load factor = 항목 수 / 버킷 수가 커지면 충돌이 증가하므로 재해시로 버킷을 늘립니다.
#include <iostream>
#include <list>
#include <string>
#include <utility>
#include <vector>
using namespace std;
class SafeHashTable {
private:
vector<list<pair<string, int>>> buckets;
int count = 0;
int index(const string& key) const {
return static_cast<int>(hash<string>{}(key) % buckets.size());
}
double loadFactor() const {
return static_cast<double>(count) / buckets.size();
}
void rehash() {
auto old = buckets;
buckets.assign(old.size() * 2, {});
count = 0;
for (auto& bucket : old) {
for (auto& kv : bucket) {
put(kv.first, kv.second);
}
}
}
public:
explicit SafeHashTable(int size = 8) : buckets(size) {}
void put(const string& key, int value) {
if (loadFactor() > 0.75) rehash();
auto& bucket = buckets[index(key)];
for (auto& kv : bucket) {
if (kv.first == key) {
kv.second = value;
return;
}
}
bucket.push_back({key, value});
count++;
}
int bucketSize() const { return static_cast<int>(buckets.size()); }
int itemCount() const { return count; }
};
int main() {
SafeHashTable ht;
for (int i = 0; i < 100; ++i) ht.put("k" + to_string(i), i);
cout << ht.bucketSize() << " " << ht.itemCount() << "\n";
return 0;
}import java.util.ArrayList;
import java.util.List;
public class Main {
static class Entry {
String key;
int value;
Entry(String key, int value) { this.key = key; this.value = value; }
}
static class SafeHashTable {
List<List<Entry>> buckets;
int count = 0;
SafeHashTable(int size) {
buckets = new ArrayList<>();
for (int i = 0; i < size; i++) buckets.add(new ArrayList<>());
}
SafeHashTable() { this(8); }
int index(String key) {
return Math.floorMod(key.hashCode(), buckets.size());
}
double loadFactor() {
return (double) count / buckets.size();
}
void rehash() {
List<List<Entry>> old = buckets;
buckets = new ArrayList<>();
for (int i = 0; i < old.size() * 2; i++) buckets.add(new ArrayList<>());
count = 0;
for (List<Entry> bucket : old) {
for (Entry e : bucket) put(e.key, e.value);
}
}
void put(String key, int value) {
if (loadFactor() > 0.75) rehash();
List<Entry> bucket = buckets.get(index(key));
for (Entry e : bucket) {
if (e.key.equals(key)) {
e.value = value;
return;
}
}
bucket.add(new Entry(key, value));
count++;
}
}
public static void main(String[] args) {
SafeHashTable ht = new SafeHashTable();
for (int i = 0; i < 100; i++) ht.put("k" + i, i);
System.out.println(ht.buckets.size() + " " + ht.count);
}
}class SafeHashTable:
def __init__(self, size=8):
self.buckets = [[] for _ in range(size)]
self.count = 0
def _index(self, key):
return hash(key) % len(self.buckets)
def _load_factor(self):
return self.count / len(self.buckets)
def _rehash(self):
old = self.buckets
self.buckets = [[] for _ in range(len(old) * 2)]
self.count = 0
for bucket in old:
for k, v in bucket:
self.put(k, v)
def put(self, key, value):
if self._load_factor() > 0.75:
self._rehash()
bucket = self.buckets[self._index(key)]
i = 0
while i < len(bucket):
if bucket[i][0] == key:
bucket[i] = (key, value)
return
i += 1
bucket.append((key, value))
self.count += 1
ht = SafeHashTable()
for i in range(100):
ht.put(f"k{i}", i)
print(len(ht.buckets), ht.count) # 버킷 증가 확인#[derive(Clone)]
struct SafeHashTable {
buckets: Vec<Vec<(String, i32)>>,
count: usize,
}
impl SafeHashTable {
fn new(size: usize) -> Self {
Self {
buckets: vec![Vec::new(); size],
count: 0,
}
}
fn index(&self, key: &str) -> usize {
let mut h: usize = 0;
for b in key.as_bytes() {
h = h.wrapping_mul(131).wrapping_add(*b as usize);
}
h % self.buckets.len()
}
fn load_factor(&self) -> f64 {
self.count as f64 / self.buckets.len() as f64
}
fn rehash(&mut self) {
let old = self.buckets.clone();
self.buckets = vec![Vec::new(); old.len() * 2];
self.count = 0;
for bucket in old {
for (k, v) in bucket {
self.put(&k, v);
}
}
}
fn put(&mut self, key: &str, value: i32) {
if self.load_factor() > 0.75 {
self.rehash();
}
let idx = self.index(key);
for (k, v) in &mut self.buckets[idx] {
if k == key {
*v = value;
return;
}
}
self.buckets[idx].push((key.to_string(), value));
self.count += 1;
}
}
fn main() {
let mut ht = SafeHashTable::new(8);
for i in 0..100 {
ht.put(&format!("k{}", i), i);
}
println!("{} {}", ht.buckets.len(), ht.count);
}해시 성능/보안 결과 버킷 상태 추적
보안 관점과 별개로, 로드 팩터 관리만으로도 충돌 리스크를 줄일 수 있습니다.
재해시는 한 번에 비용이 크지만 장기적으로 평균 탐색 길이를 낮춰 성능을 안정화합니다.
운영에서는 재해시 타이밍과 피크 시간대 충돌을 함께 고려해야 합니다.
- 평균 시간복잡도: 삽입
O(1)(재해시 상쇄 가정) - 최악 시간복잡도: 재해시 시
O(N) - 공간복잡도:
O(N)
입력 정규화와 방어적 키 처리
문제 의도: 키 정규화와 입력 검증으로 충돌/중복 리스크를 줄이는 방법을 보여줍니다.
입력 예시: 대소문자/공백/특수문자가 섞인 사용자 키
출력 예시: 정규화된 키 목록과 처리 결과
정규화 함수는 입력이 들쭉날쭉해도 같은 사용자를 같은 키로 인식하게 만듭니다.
#include <algorithm>
#include <cctype>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
string normalizeKey(const string& raw) {
string key;
bool prevSpace = false;
for (char ch : raw) {
char c = static_cast<char>(tolower(static_cast<unsigned char>(ch)));
if (isspace(static_cast<unsigned char>(c))) {
if (!key.empty() && !prevSpace) key.push_back(' ');
prevSpace = true;
} else {
key.push_back(c);
prevSpace = false;
}
}
if (!key.empty() && key.back() == ' ') key.pop_back();
return key;
}
int main() {
vector<string> samples = {" User A ", "user a", "USER A", "user-b"};
for (const auto& s : samples) cout << "[" << normalizeKey(s) << "] ";
cout << "\n";
return 0;
}public class Main {
static String normalizeKey(String raw) {
return raw.trim().toLowerCase().replaceAll("\\s+", " ");
}
public static void main(String[] args) {
String[] samples = {" User A ", "user a", "USER A", "user-b"};
for (String s : samples) {
System.out.print("[" + normalizeKey(s) + "] ");
}
System.out.println();
}
}import re
def normalize_key(raw):
key = raw.strip().lower()
key = re.sub(r"\s+", " ", key)
return key
samples = [" User A ", "user a", "USER A", "user-b"]
print([normalize_key(x) for x in samples])
# ['user a', 'user a', 'user a', 'user-b']fn normalize_key(raw: &str) -> String {
let trimmed = raw.trim().to_lowercase();
let mut out = String::new();
let mut prev_space = false;
for ch in trimmed.chars() {
if ch.is_whitespace() {
if !prev_space {
out.push(' ');
}
prev_space = true;
} else {
out.push(ch);
prev_space = false;
}
}
out.trim().to_string()
}
fn main() {
let samples = vec![" User A ", "user a", "USER A", "user-b"];
let mut result: Vec<String> = Vec::new();
for s in samples {
result.push(normalize_key(s));
}
println!("{:?}", result);
}해시 성능/보안 결과 해시 접근 재확인
많은 성능 문제는 해시 함수보다 입력 품질에서 시작됩니다.
정규화를 통해 동일 의미 키를 통합하면 불필요한 충돌과 중복 저장을 줄일 수 있습니다.
보안 설계에서도 입력 정규화는 첫 번째 방어선입니다.
- 시간복잡도:
O(N * L)(N은 문자열 개수,L은 평균 길이) - 공간복잡도:
O(N * L)
해시 보안 강화 적용 기준
성능/보안 균형을 잡을 때 확인할 항목입니다.
- 외부 입력 비율이 높은가
- 최악 지연 허용치(SLO)가 엄격한가
- CPU 예산과 메모리 예산 중 무엇이 더 타이트한가
- 장애 시 재해시/재시작 비용을 감당할 수 있는가
서비스 성격에 따라 해시 강화 수준을 계층적으로 설정하는 것이 일반적입니다.
성능/보안 상충 지점
대표적인 균형점입니다.
- 빠른 해시: 처리량 유리, 충돌 공격 리스크
- 강한 해시: 예측 어려움, CPU 비용 증가
- 낮은 로드 팩터: 빠른 조회, 메모리 사용량 증가
- 높은 로드 팩터: 메모리 절약, 충돌 탐색 비용 증가
한 지표만 최적화하면 다른 지표에서 비용이 튀어 오릅니다.
해시 보안 오답 패턴과 교정 방법
운영에서 실제로 자주 발생하는 실수입니다.
- 공개 입력 키를 정규화 없이 그대로 저장
- 로드 팩터 임계치 없이 버킷 확장 미실시
- 재해시가 피크 시간에 동작해 지연 급증
- 충돌 집중 로그를 수집하지 않아 병목 원인 추적 실패
관측 지표(버킷 길이 분포, 재해시 횟수)를 운영 대시보드에 포함해야 합니다.
충돌률과 입력 분포 판단
같은 정답이라도 입력 분포에 따라 병목 지점이 달라지므로, 판단 축을 시간복잡도 표 하나로 끝내지 말고 분포 가정까지 명시해야 합니다.
| 항목 | 평균 시간 | 최악 시간 | 공간 |
|---|---|---|---|
| 해시 조회/삽입 | O(1) | O(N) | O(N) |
| 재해시 | 상쇄 시 평균 유지 | 단일 이벤트 O(N) | O(N) |
| 정규화 처리 | O(L) (L은 키 길이) | O(L) | O(1) 추가 |
평균 성능만이 아니라 최악 지연을 모니터링해야 안정 운영이 가능합니다.
키 정규화 구간 참고점
- 보안 강화를 적용할 때는 성능 회귀 테스트를 반드시 함께 수행합니다.
- 해시 구조는 입력 검증 계층과 결합해 설계해야 효과가 큽니다.
- 언어 런타임 기본 해시 정책을 맹신하지 말고 서비스 특성에 맞춰 검증합니다.
- 공격 시나리오와 정상 시나리오를 분리해 부하 테스트를 수행해야 합니다.
제출 전 해시 방어 체크리스트
- 충돌 집중 입력에 대한 방어 전략(솔트/재해시/정규화)을 정의했는가
- 평균 지표뿐 아니라 tail latency를 측정했는가
- 로드 팩터 임계치와 재해시 타이밍을 운영 조건에 맞췄는가
- 공격 시나리오와 정상 시나리오를 분리해 테스트했는가
해시 성능·보안 균형 정리
해시는 빠른 도구이면서 공격 표면이 될 수 있는 구조입니다.
성능과 보안을 동시에 설계하는 관점을 갖추면, 평균 속도와 최악 안정성을 함께 확보할 수 있습니다.