해시란? 뭘까…?

해시를 사용한적이 많다.

알고리즘을 할때나. 맵에 넣어서 사용할때.

해시가 빠르다고 알고잇으니까 그냥 사용했다.

키 맵 구조인것도 알고.

주소를 해시값 변환해서 사용한다는 것도 안다.

빅오표기법으로 1 의 시간이 걸려서 빠르다는것도 안다.

그런데 왜? 빠를까?

갑자기 이런 궁금증이 생겼다.

공부하다가 해시 조인이라는것도 있다고 하는데.

나는 해시라는 단어에 대해 완벽히 파악하고 있었는가…….

그래서 오늘은 해시에 대해서 이해해 보는 시간을 가져보자.

✅ 해시(Hash)란?

• 임의의 데이터를 일정한 규칙(해시 함수)에 따라 고정된 크기의 값(해시값)으로 변환하는 것.
• 예를 들어 문자열 "apple"을 해시 함수에 넣으면 3e23e816 같은 고정된 길이의 숫자/문자열로 바뀌는 거야.
• 해시의 핵심 목적은 데이터를 빠르게 찾거나(탐색), 비교하거나, 저장하는 데 있어.

✅ 왜 해시를 쓰면 빠를까?

• 해시 함수 덕분에, 원래는 O(N) 시간이 걸릴 선형 탐색이 → 거의 O(1) 시간에 원하는 데이터를 찾을 수 있어.
• 예를 들어 배열은 “인덱스”로 O(1)에 찾지만, 키가 숫자가 아닌 문자열일 때는 해시를 써서 문자열 → 숫자 인덱스로 바꿔서 빠른 탐색을 가능하게 하는 거야.

arr[0] arr[1] 0index ⇒ 주소값

여기까지 말하는게 무슨말인지 잘 이해가 안가서 추가 설명을 요청했다.

✅ 배열에서 탐색과 해시 탐색의 차이

1️⃣ 배열의 인덱스 탐색: 왜 O(1)인가?

• 배열은 메모리에 연속된 공간을 차지해.
• 예를 들어 배열 arr[0..9]가 있으면, arr[5]를 찾으려면
• ➔ 주소 계산식 = 배열 시작주소 + (5 × 요소 크기) 로 한 번에 위치를 계산해서 바로 접근 가능해.
• 이 계산이 CPU 수준에서 빠르게 되기 때문에 시간복잡도가 O(1)이야.

🔹 단점: 배열은 인덱스가 숫자로만 되어 있어야 함.

예: arr[5]처럼 정수 인덱스만 사용 가능.

---

2️⃣ 문자열 키로 탐색: 왜 그냥은 느린가?

• 예를 들어 {"apple":1, "banana":2}처럼 문자열을 키로 쓰고 싶을 때,

arr[apple] =

• 배열처럼 “apple번째 위치”라고 할 수 없음 → 배열은 숫자 인덱스만 받으니,
• 문자열이 몇 번째인지 찾으려면 처음부터 끝까지 하나씩 키를 비교 → O(N) 시간이 걸림.

이걸 보니까 살짝 이해된다.

즉 배열은 이미 인덱스 기반으로 값을 찾는다. 그래서 배열 탐색은 시간이 O(1)이 나온다. 하지만 배열 탐색을 위해서는 이미 해당 인덱스를 알고있어야하는 단점이 있음.

그러면 문자열 키로 탐색하고 싶을때, 그것도 빠르게 탐색하려면 해시맵을 사용하는 방법이 있다.

그럼 궁금한점.

왜 숫자로 탐색할때랑 문자로 탐색하는거랑 시간이 똑같지? 문자로 찾으면 더 오래걸려야 정상 아닌가?

3️⃣ 해시가 어떻게 문자열을 O(1)로 만들어주나?

여기서 해시 함수가 등장!

🔹 해시 함수 역할

• 문자열 "apple"을 → 정수로 바꿔줘 → 예: hash("apple") = 10293

10293 230303

• 이 숫자를 버킷 개수로 나눈 나머지로 배열 인덱스로 변환 → 예: 10293 % 1000 = 293 → 배열 293번째 슬롯에 저장.

즉,

✅ 문자열 키 ➔ 해시 함수 ➔ 숫자 ➔ 배열 인덱스 ➔ O(1)로 바로 접근!

이 부분을 보게 되면 해시함수를 통해 문자를 숫자로 바꿔버린다.

하나의 문자는 해시함수를 통해 숫자로 변환되기에 같은 문자가 아닌이상 겹치는 숫자가 절대로 나오지않는다.

그러니까 저걸로 나온 숫자를 배열의 인덱스로 사용한다면?????

배열처럼 N(1)이라는 탐색 시간이 나온다는 것이다!!!!!

깨달앗다….

자 근데 숫자로 변환하는거까지는 알겟음.

근데 바로 그 숫자가 배열의 인덱스가 되는건아니고??

버킷 갯수라는걸로 나눈 나머지로 배열인덱스로 바꾼다네?

버킷 갯수는 뭐고 나머지를 사용하게 되면 인덱스가 겹쳐서 같은 주소에 다른값이 들어가버릴수도 있는거 아니야?

그리고 버킷 갯수는 누가정하는거임?

좋은 관찰이야! 이 질문에 답을 찾으면 해시의 진짜 핵심을 이해했다고 할 수 있어. 차근차근 풀어서 설명할게.

칭찬받음…

---

✅ 버킷(Bucket) 갯수란?

• 해시 테이블 내부에는 실제 데이터를 저장할 슬롯들을 담은 배열이 있어.
• 이 배열의 크기를 **버킷 갯수(bucket count)**라고 불러.
• 예: 버킷 갯수 8 ➔ index 0~7까지 슬롯 존재.
• 해시 함수 결과를 hash(key) % 버킷갯수로 계산해서
• ➔ 데이터가 들어갈 슬롯 위치를 결정해.

자바 해시맵은 버킷갯수가 자동으로 디폴트 16개로 되어잇음.

---

✅ 왜 나머지를 사용하나?

• 해시 함수는 보통 큰 수(예: 32비트 정수)를 반환해.
• 하지만 배열 인덱스는 버킷 갯수 범위 안(0 ~ 버킷갯수-1)으로 제한되어야 하니,
• ➔ 나머지 연산 %로 범위를 제한하는 거야.

배열을 엄청 크게만들지 않고 그냥 버킷만큼 만들어냄.

예를 들어:

• 버킷 갯수 8
• hash("apple")=23 ➔ 23%8=7 → 배열 index 7에 저장
• hash("banana")=15 ➔ 15%8=7 → 배열 index 7에 저장

---

✅ 인덱스가 겹치는 문제: 충돌(Collision)

맞아! 네가 짚은 대로, 해시 함수 결과가 다르더라도 % 버킷갯수로 인덱스를 구하면 겹칠 수 있어.

이걸 충돌이라고 하고, 해시 구조에서 반드시 고려해야 하는 부분이야.

🔹 예제:

• "apple"과 "banana"가 해시값은 달라도 % 버킷갯수 결과가 같으면 ➔ 같은 슬롯에 두 데이터가 들어가게 됨.

---

✅ 충돌 처리 방법

대표적으로 2가지가 있어:

1️⃣ 체이닝(Chaining)

• 버킷 슬롯 하나에 연결 리스트 형태로 여러 데이터 저장.
• 같은 슬롯에 들어온 데이터는 리스트로 이어서 저장하니 손쉽게 충돌 해결 가능.

2️⃣ 오픈 어드레싱(Open Addressing)

• 충돌 발생 시 빈 슬롯을 찾아 이동해 저장.
• 선형 탐사(Linear probing), 제곱 탐사(Quadratic probing) 등 다양한 방법이 있어.

그러면 같은 버킷 인덱스에 리스트 형태로 여러 데이터가 저장되는거면 더 느려야하는거 아니야? 일반 배열은 그냥 하나의 인덱스에 하나의 데이터가 저장되는거니까 다시 리스트에서 찾아야하는 과정이 없잖아.

ㅇㅇ 그래서 해시 함수는 가장 최적인 상황 즉 하나의 인덱스에 하나의 데이터일때 N(1) 시간이지만 최악의 시간일때는 N(n)까지 느려질 수 있다.

그러면 어떻게 해야? 버킷의 크기를 늘리거나, 해시테이블 설계를 잘하거나~

---

✅ 버킷 갯수는 누가 정하나?

• 대부분의 경우 프로그래머가 명시적으로 설정하거나 디폴트 설정 사용한다.
  • 예: Java HashMap은 기본적으로 16개의 버킷으로 시작하고, 적재량(load factor)이 일정 수준 넘으면 크기를 2배로 자동 증가시켜 리사이징함.
• 적절한 버킷 갯수는
• ➔ 저장할 데이터 개수, 충돌 허용 범위, 메모리 사용량 등을 고려해 정해.

---

✅ 버킷 갯수는 왜 2의 거듭제곱이 많은가?

• 해시 테이블 구현에서는 버킷 갯수를 2, 4, 8, 16, … 처럼 2의 거듭제곱으로 유지하는 경우가 많아.
• 이유는 % 대신 비트 마스크 연산(hash & (bucketCount-1))으로 인덱스를 구할 수 있어 훨씬 빠르기 때문.

---

🔎 정리하자면

• 버킷 갯수는 해시 테이블의 배열 크기.
• 충돌은 같은 인덱스에 여러 키가 들어가는 상황.
• 충돌은 체이닝, 오픈 어드레싱 등의 방법으로 해결.
• 버킷 갯수는 사용자가 설정하거나 라이브러리에서 자동 관리.

와…잠만….그러면…… 처음에 배운 해시로 찾는거 연결리스트 이거나온이유가 버킷이 겹치니까였음?

미쳣다 진짜………… 전율………

진짜 개소름돋았다.

개소름돋은 시간 메모….역사적인 순간임(2025.06.29 약 오후 3시53분경, 압구정로데오역 근처 스타벅스 리저브)

해시의 역사

---

🕰️ 해시의 역사 개요

1. 1950~1960년대: 해시 개념의 기초 등장

• 데이터 검색 최적화를 위한 구조로서 해시 테이블(Hash Table)의 개념이 등장합니다.
• 1953년, Hans Peter Luhn이 IBM에서 비슷한 개념을 사용해 정보를 정렬하고 검색하는 방법을 제안했습니다.
• 1960년, D. H. Lehmer와 Gene Amdahl 등의 연구를 통해 키 기반 검색 최적화를 위한 기술로서 해싱이 체계화됩니다.

🔍 용도:

• 대용량 데이터의 빠른 검색
• 키-값 쌍 기반의 데이터 저장

---

2. 1970~1980년대: 암호학적 해시 함수의 탄생

• 해시가 보안 목적으로 사용되기 시작한 시기입니다.
• 1970년대 후반, 암호학적 해시 함수라는 개념이 생기고, 충돌 저항성(Collision resistance), 일방향성(One-wayness) 등의 요구사항이 정의됩니다.

🔐 대표적인 초기 해시 함수:

• MD4 (1990) – Ronald Rivest가 개발
• MD5 (1991) – MD4의 개선판, 많이 사용되었지만 현재는 보안상 취약

---

3. 1990~2000년대: 강력한 해시 함수의 발전

• 보안 공격 기법이 고도화됨에 따라 더 안전한 해시 함수가 요구됩니다.
• SHA 시리즈가 미국 NIST(National Institute of Standards and Technology)에 의해 표준으로 도입됩니다.

🧱 주요 해시 함수들:

• SHA-1 (1995): 널리 쓰였지만 2005년에 충돌 가능성이 발견됨.
• SHA-2 (2001): SHA-256, SHA-512 등으로 나뉘며, 현재까지도 사용 중.
• SHA-3 (2015): Keccak 알고리즘 기반으로 차세대 해시 함수로 채택.

---

4. 2010년대~현재: 블록체인과 해시의 대중화

• *비트코인(2009)**과 같은 블록체인 기술의 핵심으로 해시가 널리 알려지게 됩니다.
• 해시는 블록의 위변조 방지, 작업 증명(Proof of Work), 주소 생성 등에 사용됨.
• SHA-256은 비트코인, **Keccak(SHA-3)**는 이더리움에서 활용.

📦 해시 활용 분야 확장:

• 디지털 서명
• 무결성 검증
• 인증서(Certificate)
• 중복 제거(Deduplication)
• 디지털 포렌식

해시값 만드는 방법

---

진짜 설명 진짜찐짜 어려운데

내가 예시를들어서 잘 설명해보겟숨

1. 문자열 “abc”를 해시값으로 만든다고 가정
2. a 는 16진수로 0x61 로 변환. 아스키코드값으로는 97
3. 해당 진수를 2비트로 변환하면 01100001 01100010 01100011
4. 여기에 1비트를 추가함. 1비트는 10000000
5. 그러면 총 32개의 비트가 만들어진다. 근데 여기에 64개를 더해야하는데.
6. 이 64개의 의미는 원본 메세지의 길이를 즉 비트갯수 24개를 의미한다. 3번을 보면 24개가 보인다. 24를 표현한 비트이다.
7. 그러면 32 + 64 = 96이다. 그런데 512개의 비트로 만들어야 이후 암호화를 하기 때문에 그사이에 있는 비트를 다 0으로 넣어준다.
8. 512 비트를 쪼갠다. 16개의 워드 집합으로 만든다. 즉 하나의 집합에 32비트가 들어있음.
9. 추가 48개 워드를 W[t] = σ1(W[t-2]) + W[t-7] + σ0(W[t-15]) + W[t-16] 공식으로 만든다.
10. 그러면 총 64개의 워드가 생성.

for (int t = 0; t < 64; t++) {
    int S1 = (ROTR(e,6)) ^ (ROTR(e,11)) ^ (ROTR(e,25));
    int ch = (e & f) ^ ((~e) & g);
    int temp1 = h + S1 + ch + K[t] + W[t];

    int S0 = (ROTR(a,2)) ^ (ROTR(a,13)) ^ (ROTR(a,22));
    int maj = (a & b) ^ (a & c) ^ (b & c);
    int temp2 = S0 + maj;

    h = g;
    g = f;
    f = e;
    e = d + temp1;
    d = c;
    c = b;
    b = a;
    a = temp1 + temp2;
}

위와같은 과정을 포문 64번을 돌리고 안에 있는 W[t] 배열에 담아서 진행한다.

여기서 W[t]는 정확히 뭐에 쓰이냐?

👇 요기! 핵심 줄:

temp1 = h + S1 + ch + K[t] + W[t];

• W[t]는 각 라운드에서 새로운 영향을 주는 메시지 기반 데이터입니다.
• W[t]는 입력 메시지에 따라 달라지므로,
• 이 값이 매 라운드의 결과에 강력한 비틀림(혼합) 역할을 합니다.

즉,

📌 W[t]는 메시지의 정보를 해시 계산에 주입하는 역할을 합니다.

함께 쓰이는 K[t]는 뭐예요?

• K[0] ~ K[63]은 SHA-2에서 정의한 고정된 상수
• W[t]는 입력 메시지 기반 동적 값
• → 이 둘을 합쳐서 매 라운드마다 다른 결과를 만들어냄

1. 위 과정을 거쳐서 8개의 32비트 문자가 만들어진다.
2. 각각이 32비트인데 32비트는 4바이트임. = 1바이트 = 8비트 알지?
3. 즉 h[0] 에는 32비트 정수가 있으며 이건 4바이트임.
4. h[7]까지있으니까 8곱하면 32바이트임.

여기부분 잘모르겟넹….히히

✅ 1단계: 32비트 정수 → 바이트 배열(byte[])로 변환

각 32비트 정수(int)를 big-endian 순서로 바이트 4개로 나눕니다:

예시: H0 = 0xBA7816BF

→ 32비트 정수 → 4바이트

java
복사편집
byte[0] = (byte) ((H0 >>> 24) & 0xFF); // 0xBA
byte[1] = (byte) ((H0 >>> 16) & 0xFF); // 0x78
byte[2] = (byte) ((H0 >>> 8)  & 0xFF); // 0x16
byte[3] = (byte) ( H0         & 0xFF); // 0xBF

📦 이렇게 H0~H7을 각각 4바이트씩 분해해서 → 총 32바이트짜리 byte[]가 됩니다.

---

✅ 2단계: 바이트 배열을 사람이 읽을 수 있는 16진수 문자열로 변환

Java에서는 다음과 같이 처리합니다:

java
복사편집
StringBuilder sb = new StringBuilder();
for (byte b : hash) {
    sb.append(String.format("%02x", b & 0xFF));
}
String result = sb.toString();

여기서 무슨 일이 일어나냐면...

• b & 0xFF → 부호 없는 0~255 범위의 정수로 변환
• String.format("%02x", ...) → 2자리 16진수 문자열로 변환
  • 예: 186 → "ba", 120 → "78", ...

📌 이걸 32바이트(=256비트) 전체에 대해 수행하면

→ 64자리의 16진수 문자열이 완성됩니다.

요약

"abc"
  ↓ (UTF-8 인코딩)
[0x61, 0x62, 0x63]
  ↓ (패딩 + 블록화)
512비트 블록
  ↓ (SHA-256 알고리즘: 64라운드)
32바이트 해시값 (byte[])
  ↓ (각 바이트 → 2자리 16진수)
64자리 16진수 문자열
→ "ba7816bf8f01cfea...15ad"