1. 해시
1-1. 해시의 개념
배열에서 특정 값을 찾으려면 순차 검색은 O(n), 이분 검색은 O(log n)이 걸린다. 그런데 해시(Hash) 를 사용하면 O(1), 즉 데이터가 아무리 많아도 거의 한 번에 찾을 수 있다.
해시의 핵심 아이디어는 간단하다. 데이터를 저장할 때 "어디에 넣을지"를 데이터 자체로부터 계산 하는 것이다. 찾을 때도 같은 계산을 해서 바로 그 위치를 확인하면 된다. 처음부터 끝까지 훑을 필요 없이, 계산 한 번으로 위치를 알 수 있으니 빠른 것이다.
1-2. 해시 테이블
해시 테이블(Hash Table)은 해시를 구현하기 위한 자료구조다. 구조를 이해하려면 버킷(Bucket), 슬롯(Slot) 이라는 개념을 알아야 한다.
해시 테이블은 여러 개의 버킷 으로 구성된다. 각 버킷은 여러 개의 슬롯 으로 구성된다. 그리고 슬롯은 데이터가 실제로 저장되는 단위 다.
쉽게 비유하면 사물함이다. 사물함 전체가 해시 테이블이고, 각 칸(1번, 2번, 3번...)이 버킷이다. 한 칸 안에 물건을 여러 개 넣을 수 있다면 각 물건 자리가 슬롯이다.
해시 테이블
┌─────────────────────────┐
│ 버킷 0: [슬롯0][슬롯1][슬롯2] │
│ 버킷 1: [슬롯0][슬롯1][슬롯2] │
│ 버킷 2: [슬롯0][슬롯1][슬롯2] │
│ 버킷 3: [슬롯0][슬롯1][슬롯2] │
│ 버킷 4: [슬롯0][슬롯1][슬롯2] │
└─────────────────────────┘
이 구조를 보면 알 수 있듯이 해시 테이블은 본질적으로 2차원 배열 이다. 행이 버킷, 열이 슬롯이다.
버킷 수와 슬롯 수를 어떻게 잡느냐에 따라 성능이 달라진다. 총 용량이 같더라도 버킷 수가 많고 슬롯 수가 적은 것 이 검색에 유리하다. 버킷이 10개이고 슬롯이 5개(총 50칸)인 경우, 해시 함수로 버킷 번호를 구하면 해당 버킷의 슬롯 5개만 확인하면 된다. 반대로 버킷이 2개이고 슬롯이 25개(총 50칸)라면, 한 버킷 안에서 최대 25개를 뒤져야 한다. 데이터가 여러 버킷에 골고루 분산될수록 각 버킷에서 찾아야 할 양이 줄어든다.
1-3. 2차원 배열과 메모리 구조
해시 테이블이 2차원 배열이라고 했으니, 2차원 배열의 메모리 구조를 짚고 넘어가자.
C/C++에서 2차원 배열은 메모리에 행 우선(row-major) 으로 저장된다. int table[3][4]라면 0행의 4개 원소가 먼저 연속으로 놓이고, 이어서 1행, 2행 순서다.
int table[3][4];
메모리 상의 배치:
[0][0] [0][1] [0][2] [0][3] [1][0] [1][1] [1][2] [1][3] [2][0] [2][1] [2][2] [2][3]
│──────── 0행 ────────│──────── 1행 ────────│──────── 2행 ────────│
해시 테이블로 사용하면 table[버킷번호][슬롯번호]로 접근하게 된다. 해시 함수가 버킷 번호(행)를 결정하면, 그 행 안의 슬롯(열)을 순차적으로 확인하는 구조다.
#define BUCKET_SIZE 5
#define SLOT_SIZE 3
int hashTable[BUCKET_SIZE][SLOT_SIZE];
memset(hashTable, 0, sizeof(hashTable));
1-4. 해시 함수
해시 함수는 입력된 키 값으로 버킷의 번호를 찾아내는 함수 다. 어떤 데이터를 넣으면 그 데이터가 어느 버킷에 들어갈지를 결정한다.
가장 기본적인 해시 함수는 나머지 연산(모듈러) 이다.
int hashFunction(int key) {
return key % BUCKET_SIZE;
}
버킷이 5개라면 key % 5를 하면 결과가 항상 0~4 사이에 나온다. 키 값이 뭐든 5개 버킷 중 하나로 매핑되는 것이다.
키 13 → 13 % 5 = 3 → 버킷 3에 저장
키 27 → 27 % 5 = 2 → 버킷 2에 저장
키 8 → 8 % 5 = 3 → 버킷 3에 저장 (13과 같은 버킷!)
키 13과 키 8이 같은 버킷 3에 들어간다. 서로 다른 키가 같은 버킷에 매핑되는 것을 충돌(Collision) 이라 한다. 슬롯이 여러 개인 이유가 이것이다. 충돌이 발생하면 같은 버킷의 다음 슬롯에 저장한다. 만약 슬롯이 전부 차면 오버플로우 가 발생한다.
좋은 해시 함수는 데이터를 최대한 균등하게 분산시켜 충돌을 줄이는 함수다.
간단한 해시 테이블 구현을 보자.
#include <iostream>
#include <cstring>
using namespace std;
#define BUCKET_SIZE 7
#define SLOT_SIZE 3
int hashTable[BUCKET_SIZE][SLOT_SIZE];
int hashFunction(int key) {
return key % BUCKET_SIZE;
}
bool insert(int key) {
int bucket = hashFunction(key);
for (int i = 0; i < SLOT_SIZE; i++) {
if (hashTable[bucket][i] == 0) { // 빈 슬롯 찾기
hashTable[bucket][i] = key;
return true;
}
}
return false; // 슬롯 전부 참 → 오버플로우
}
bool search(int key) {
int bucket = hashFunction(key);
for (int i = 0; i < SLOT_SIZE; i++) {
if (hashTable[bucket][i] == key) {
return true; // 찾음
}
}
return false; // 못 찾음
}
int main() {
memset(hashTable, 0, sizeof(hashTable));
insert(13);
insert(27);
insert(8);
insert(42);
cout << search(27) << endl; // 1 (찾음)
cout << search(99) << endl; // 0 (못 찾음)
return 0;
}
insert에서 해시 함수로 버킷 번호를 구한 뒤, 해당 버킷에서 빈 슬롯을 찾아 저장한다. search에서도 같은 해시 함수로 버킷을 찾고, 그 버킷의 슬롯만 확인하면 된다. 전체 데이터를 훑을 필요 없이 하나의 버킷만 확인 하면 되므로 빠르다.
1-5. 해시맵
해시맵(HashMap)은 해시 자료구조를 사용해서 키-값(key-value) 쌍 을 저장하는 자료구조다. 키를 해시 함수에 넣어 저장 위치를 결정하므로 검색 속도가 매우 빠르다.
JavaScript의 객체({})나 Map이 바로 해시맵이다. obj["name"] = "홍길동" 하면 "name"이라는 키를 해시해서 값을 저장하고, obj["name"]으로 읽을 때도 같은 해시를 계산해서 바로 찾아간다.
C++에서는 STL의 unordered_map이 해시맵 구현체다.
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
unordered_map<string, int> scores;
// 삽입
scores["홍길동"] = 90;
scores["김철수"] = 85;
scores["이영희"] = 95;
// 검색 — O(1)
cout << scores["홍길동"] << endl; // 90
// 존재 여부 확인
if (scores.find("김철수") != scores.end()) {
cout << "김철수 발견: " << scores["김철수"] << endl;
}
// 순회
for (auto &pair : scores) {
cout << pair.first << ": " << pair.second << endl;
}
return 0;
}
unordered_map 은 내부적으로 해시 테이블을 사용하므로 삽입, 검색, 삭제 모두 평균 O(1) 이다. 순차 검색의 O(n), 이분 검색의 O(log n)과 비교하면 압도적으로 빠르다.
참고로 STL에는 map도 있는데, 이것은 해시가 아니라 레드-블랙 트리(균형 이진 탐색 트리) 로 구현되어 있어서 O(log n)이다. 대신 키가 자동으로 정렬된다는 장점이 있다. 정렬이 필요 없고 속도가 중요하면 unordered_map을, 키 순서가 필요하면 map을 사용한다.
문자열을 해시하는 간단한 예시도 보자. 문자열의 각 문자 ASCII 값을 합산하는 방식이다.
int stringHash(const string &key, int bucketSize) {
int hash = 0;
for (char c : key) {
hash += (int)c;
}
return hash % bucketSize;
}
// "abc" → 97+98+99 = 294 → 294 % 7 = 0 → 버킷 0
// "bca" → 98+99+97 = 294 → 294 % 7 = 0 → 버킷 0 (충돌!)
단순 합산은 문자 순서가 달라도 같은 해시값이 나오는 문제가 있다. 실제 해시 함수는 문자의 위치까지 고려한 더 정교한 수식을 사용한다.
2. 싱글톤 패턴
2-1. 싱글톤 패턴이란?
싱글톤 패턴(Singleton Pattern)은 클래스의 인스턴스가 프로그램 전체에서 단 하나만 존재하도록 보장하는 디자인 패턴 이다.
프로그램에서 특정 객체가 하나만 있어야 하는 경우가 있다. 데이터베이스 연결 관리자, 로그 기록기, 설정(Configuration) 관리자 같은 것들이다. DB 연결 객체가 여러 개 만들어지면 연결이 낭비되고, 설정 객체가 여러 개면 어떤 것이 진짜 설정인지 혼란스러워진다.
2-2. 일반적인 방식의 문제
그냥 전역변수를 쓰면 되지 않을까? 가능은 하지만 문제가 있다.
// 전역 객체 — 누구든 새로 만들 수 있음
Config config1;
Config config2; // 두 번째 객체 생성을 막을 수 없음
클래스를 new로 만들든 직접 선언하든, 아무런 제약 없이 여러 개를 만들 수 있다. 언어 차원에서 "하나만 만들어라"를 강제할 방법이 필요하다.
2-3. 싱글톤 구현
핵심 아이디어는 세 가지다.
생성자를 private으로 만들어서 외부에서 객체를 직접 생성하지 못하게 한다. 유일한 인스턴스를 static 멤버 로 클래스 내부에 보관한다. static 멤버함수 로 그 인스턴스에 접근하는 유일한 통로를 제공한다.
class Singleton {
private:
static Singleton *instance; // 유일한 인스턴스를 가리키는 포인터
int data;
// 생성자를 private으로 — 외부에서 new, 직접 생성 불가
Singleton() : data(0) {
cout << "싱글톤 생성" << endl;
}
// 복사 생성자, 대입 연산자도 막음
Singleton(const Singleton &) = delete;
Singleton& operator=(const Singleton &) = delete;
public:
// 인스턴스를 얻는 유일한 방법
static Singleton* getInstance() {
if (instance == nullptr) {
instance = new Singleton();
}
return instance;
}
void setData(int d) { data = d; }
int getData() { return data; }
// 프로그램 종료 시 정리
static void destroyInstance() {
delete instance;
instance = nullptr;
}
};
// static 멤버변수 초기화
Singleton* Singleton::instance = nullptr;
int main() {
// Singleton s; // 에러! 생성자가 private
// Singleton *p = new Singleton(); // 에러! 생성자가 private
Singleton *s1 = Singleton::getInstance();
Singleton *s2 = Singleton::getInstance();
s1->setData(42);
cout << s2->getData() << endl; // 42 — 같은 객체이므로
cout << (s1 == s2) << endl; // 1 (true) — 같은 주소
Singleton::destroyInstance();
return 0;
}
getInstance()를 처음 호출하면 instance가 nullptr이므로 new Singleton()으로 객체를 생성한다. 두 번째 호출부터는 이미 만들어진 객체의 주소를 그대로 반환한다. 결과적으로 s1과 s2는 같은 객체를 가리킨다.
복사 생성자와 대입 연산자를 = delete로 삭제한 것도 중요하다. 이것을 하지 않으면 Singleton s3 = *s1;으로 복사본을 만들어서 싱글톤의 의미가 깨질 수 있다.
2-4. 더 간결한 구현 (C++11 이후)
C++11부터는 지역 static 변수의 초기화가 스레드 안전하게 보장되므로, 더 간결하게 구현할 수 있다.
class Singleton {
private:
int data;
Singleton() : data(0) {}
Singleton(const Singleton &) = delete;
Singleton& operator=(const Singleton &) = delete;
public:
static Singleton& getInstance() {
static Singleton instance; // 최초 호출 시 한 번만 생성
return instance;
}
void setData(int d) { data = d; }
int getData() { return data; }
};
int main() {
Singleton &s1 = Singleton::getInstance();
Singleton &s2 = Singleton::getInstance();
s1.setData(42);
cout << s2.getData() << endl; // 42
cout << (&s1 == &s2) << endl; // 1 (true)
return 0;
}
static Singleton instance 는 함수가 처음 호출될 때 한 번만 생성되고, 프로그램 종료 시 자동으로 소멸된다. 포인터 대신 레퍼런스를 반환하므로 delete 를 신경 쓸 필요도 없고, nullptr 체크도 불필요하다.
2-5. 싱글톤의 활용과 주의점
싱글톤이 적합한 경우는 시스템에 하나만 존재해야 하는 자원을 관리할 때다. 데이터베이스 커넥션 풀, 로그 매니저, 앱 설정 관리자 같은 것들이 대표적이다.
class Logger {
private:
Logger() {}
Logger(const Logger &) = delete;
Logger& operator=(const Logger &) = delete;
public:
static Logger& getInstance() {
static Logger instance;
return instance;
}
void log(const string &message) {
cout << "[LOG] " << message << endl;
}
};
// 프로그램 어디서든 같은 로거 사용
Logger::getInstance().log("서버 시작");
Logger::getInstance().log("요청 처리 완료");
다만 싱글톤을 남용하면 문제가 생긴다. 싱글톤은 본질적으로 전역 상태 이므로, 많이 사용하면 전역변수를 남용하는 것과 같은 문제(결합도 증가, 테스트 어려움)가 발생한다. 꼭 하나만 존재해야 하는 명확한 이유가 있을 때만 사용하는 것이 좋다.
마무리
해시는 데이터를 빠르게 저장하고 찾기 위한 핵심 자료구조다. 해시 함수로 버킷 번호를 계산하고, 해당 버킷의 슬롯만 확인하면 되므로 평균 O(1)의 검색 속도를 달성한다. 싱글톤 패턴은 클래스의 인스턴스를 하나로 제한하는 디자인 패턴으로, private 생성자와 static 접근 함수가 핵심이다. 둘 다 실무에서 빈번하게 사용되는 개념이므로 원리를 이해해두면 큰 도움이 된다.