Hash 란?

Hash 란?

해시(Hash)는 어떤 길이의 데이터든 고정된 길이의 고유한 값으로 변환하는 기술이나 함수를 의미하는 용어이다.

이 고정된 길이의 고유한 값으로 변환하는 과정을 해싱(Hashing)이라고 하고, 원본 데이터를 암호학적으로 변환하여 해시 값(Hash Value)을 생성한다. 해시 값은 원본 데이터의 위치를 알려주는 인덱스 역할을 하여, 데이터 검색, 저장, 무결성 검사 등 다양한 분야에 활용된다. 해싱은 데이터의 양이 많아도 빠르게 데이터를 찾고 효율적으로 메모리를 사용하는 데 유용하며, 단방향 함수라는 특성상 원본 데이터를 해시 값에서 복구하는 것이 불가능하다.

이러한 특성으로 Hash는 데이터 관리(해시 테이블), 보안 강화(암호화), 데이터의 변조 확인(무결성 검증)에 주로 사용되고 있다.

Hashing 

입력된 데이터(키)에 대해 해시 함수를 적용하여 고정된 길이의 고유한 값(해시 값)을 생성하는 과정

데이터 검색, 저장, 무결성 검증 등에서 데이터를 효율적으로 관리하고 빠르게 접근하기 위한 기술이다.

 

특징

1. 빠른 속도 (직접적인 주소 접근, 배열의 활용)

해시 함수를 사용하여 데이터의 위치를 직접 계산하여 접근하기 때문에 데이터 검색 및 저장 속도가 매우 빠르다. 

일반적인 검색 방법처럼 데이터를 순차적으로 탐색할 필요가 없어 평균적으로 O(1)의 시간 복잡도를 가진다.

해시 테이블은 내부적으로 미리 정의된 크기의 배열(버킷)을 사용하여 데이터를 저장하는데, 이 배열은 인덱스를 통해 데이터에 직접 접근하는 구조이기 때문에, 해시 함수가 계산한 인덱스를 이용해서 매우 빠르게 데이터를 읽고 쓸 수 있는 것이다.

정렬되지 않은 배열은 순차적으로 모든 요소를 확인해야하지만(O(n)), 해싱은 해시 함수를 통해 데이터의 위치를 바로 계산하므로 그럴 필요가 없는 것이다.

2. 단방향성

원본 데이터로부터 해시 값을 생성하는 것은 가능하지만, 해시 값에서 원본 데이터를 복원하는 것은 불가능하다.

3. 무결성 보장

데이터가 변경되었는지 확인할 때 해시 값을 비교하여 데이터의 무결성을 검증하는데 사용된다.

 

Hash Function

임의의 크기를 가진 데이터를 고정된 길이의 해시 값으로 변환하는 함수다. 입력된 데이터를 해시 테이블의 인덱스(주소)로 사용할 수 있는 값으로 매핑한다.

일반적으로 크게 암호학적 해시 함수와 비암호학적 해시함수로 나뉘는데, 여기서 해시함수에 대해서는 자세히 다루지는 않을 것이다.

종류

1. 암호학적 해시 함수 (Cryptographic Hash Function)

단방향성(입력값을 복원할 수 없음)과 충돌 지향성(서로 다른 입력값에서 같은 해시값이 나올 가능성이 매우 낮음)이 중요하며, 데이터 무결성 검증, 디지털 서명 등에 사용된다. 

흔히 사용되는 SHA-256, SHA-512와 같은 것이 암호학적 해시 함수이다.

2. 비암호화 해시 함수 (Non Cryptographic Hash Function)

데이터 인덱싱 또는 해시 테이블과 같이 보안보다 효율이필요할 때 사용되는 해시 함수

3. 패스워드 기반 해시 함수

암호화된 비밀번호 저장에 특화된 해시 함수로, 일반적인 해시 함수보다 더 강력한 보안성을 제공하며 무차별 대입 공격(brute-force attack)에 강하다.

흔히 사용하는 Bcrypt와 Scrypt, Argon2 가 해당된다.

 

해시 충돌(Hash Collision)

두 개의 다른 입력이 동일한 해시 값을 생성하는 충돌이 얼마나 자주 발생하는지를 의미하며, 좋은 해시 함수는 이 충돌이 적어야 한다.

또한, 충돌이 발생했을 때 얼마나 효율적으로 처리하는지도 중요하다. 대표적으로는 체이닝(Chaining), 개방 주소법(Open Addressing)이 있다.

• 체이닝(Chaining) : 서로 다른 키가 같은 해시 값을 가질 경우, 동일한 해시 주소에 저장될 여러 데이터들을 연결 리스트(Linked list) 형태로 엮어서 관리하는 방법이다. 버킷이 꽉 차더라도 연결 리스트를 통해 계속 데이터를 추가할 수 있다.
  결론적으로 이 경우, 해시 테이블에는 데이터가 직접 저장되지 않고, 각 버킷이 해당 버킷의 해시 값을 갖는 데이터들의 연결 리스트를 가리키는 포인터를 가지게 된다.
• 개방 주소법(Open Addressing) : 충돌이 발생했을 때, 해당 해시 테이블 내의 비어있는 다른 공간을 찾아 데이터를 저장하는 방법.
  계산된 해시 값이 가리키는 슬롯이 비어있으면 데이터를 저장하고, 비어있지 않으면 이전에 저장된 데이터의 키와 비교하여 같으면 값을 업데이트하고, 다르면 다음 비어있는 인덱스를 찾아 데이터를 저장한다.

 

활용 분야

1.  데이터 무결성 검증

데이터가 변조되었는지 확인할 때 해시값을 비교하여 알 수 있다.

데이터를 해시 함수에 넣어 얻은 해시값을 함께 저장하거나 전송하여, 수신 측에서 동일한 해시 함수를 적용해 값이 같은지를 체크해서 확인하는 방식이다. 

예: 파일 다운로드 시 제공되는 SHA-256 체크섬 비교, 이메일 첨부파일 무결성 확인

2. 데이터베이스 및 자료구조

데이터를 효율적으로 저장하고 빠르게 검색하기 위해 해시 테이블과 같은 자료구조에서 사용된다.

Key를 해시 함수로 변환하여 인덱스를 계산하고, 이를 통해 원하는 데이터를 빠르게 접근할 수 있다.

예: 자바스크립트의 Map 객체, 파이썬의 dict, 데이터베이스 인덱스 설계(해시 인덱스)

3. 암호화 및 보안

데이터의 무결성을 보장하고 보안 목적으로 활용된다. 해시의 암호화는 단방향성을 가진다.

예: 비밀번호 저장(비밀번호를 평문이 아닌 해시로 저장, 비밀번호는 원문은 본인만 암)

4. 블록체인

거래 데이터의 무결성을 확인하고, 블록들을 연결하는 데 해시 함수가 중요한 역할을 한다.

예: 트랜 잭션 무결성 (각 거래 데이터에 대해 해시값을 기록해 변조 불가능하게 함)

 

자료구조로서의 Hash

임의의 길이 데이터를 고정된 길이의 해시 값으로 변환하여 데이터를 효율적으로 관리하고 빠르게 검색하기 위한 기술이다.

해시 함수를 사용하여 키(Key)를 해시 값(Hash value)으로 매핑하고, 이 해시 값을 해시 테이블의 인덱스로 사용하여 데이터에 직접 접근하는 방식이다. 이를 통해 데이터의 삽입, 삭제, 검색 속도를 크게 향상시킬 수 있다.

데이터 입력 -> 해시 함수 적용 -> 인덱스 결정 -> 데이터 저장/검색

 

이 자료구조 해시에서 쓰이는 해시 함수로는 여러가지가 있는데 여기서 자세히 다루지는 않을 것이다.

1. 제산 함수 (Modulo Function)
   특정 키(k)를 해시 테이블의 크기(M)로 나눈 나머지를 해시 값으로 사용하는 방식 (h(k) = k mod M)
2. 중간 제곱 함수 (Mid-square Method)
   키를 제곱한 후, 그 결과의 중간 부분을 취하여 해시 주소로 사용하는 방식
3. 비트 추출 함수 (Bit Extraction)
   키의 이진수 표현에서 특정 위치의 비트들을 뽑아 해시 주소로 사용하는 방식
4. 숫자 분석 방법 (Digit Analysis)
   키의 숫자들 중 편향되지 않는 부분을 선택하고 조합하여 해시 테이블 크기에 맞게 사용하는 방식
5. 폴딩 함수 (Folding Method)
   키를 여러 부분으로 나누어 더한 뒤 해시값으로 만드는 방식
6. CityHash, FarmHash, SpookyHash
   구글에서 개발한 고성능 해시 알고리즘

각 언어별 기본 해시 함수

• python : 파이썬의 dict 자료구조는 내장된 hash() 를 사용한다.
• Java : 자바의 HashMap은 객체의 hashCode() 메서드가 반환하는 값을 기본 해시값으로 사용한다.
• JavaScript : 자바스크립트에서 해시 자료구조는 Object 또는 Map 객체를 통해 구현된다. 자바스크립트 엔진이 객체의 키를 효율적으로 해싱하는 자체적인 메커니즘을 가지고 있다고 한다. 자바스크립트 개발자는 해시 함수의 구현에 직접적으로 관여할 수 없도록 되어있다.

Hash Table

해시 테이블은 (key, value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다.

구조 및 동작 방식

1. 배열 (버킷)

해시 테이블은 미리 정의된 크기의 배열을 가지고 있으며, 이 배열의 각 요소를 버킷이라고 부른다.

이 버킷의 크기는 프로그래밍 언어별로 각각 다른 내부 로직을 사용하고 있으며, 대부분의 언어는 로드 팩터(load factor, 부하율)라는 개념을 기반으로 버킷 수를 동적으로 조절하여 초기 크기를 설정하고 필요에 따라 크기를 두 배로 늘리는 재해싱(Rehashing) 방식을 사용한다.

각 언어별 해시테이블 버킷 크기 결정 방식

• JAVA : HashMap의 기본 버킷 크기 16, 기본 로드 팩터 0.75, 해시맵에 저장된 요소 개수가 현재 버킷 크기 * 로드 팩터를 초과 시 버킷 크기를 두 배로 늘리는 재해싱 발생
• Python : 딕셔너리 (dict)는 처음 생성될 때 8개의 버킷을 가지고, 저장량이 2/3를 초과하면, 더 큰 크기로 버킷 배열을 재할당
• JavaScript 
  • Map, Set : JS의 Map 객체는 해시테이블로 구현되어 있다. Map을 처음 생성하면 내부 해시 테이블은 2개의 버킷으로 시작하고, 용량은 4개 엔트리(버킷당 2개)이다. 자바스크립트의 V8엔진은 Load Factor (부하율 : 테이블에 채워진 엔트리 수 / 총 버킷 수)이 특정 임계치를 초과할 때 크기를 조정한다. 이 부하율은 2로 설정되어 있어, 버킷 수의 두 배인 용량이 차면 리해싱이 발생한다.
  • Object : JS의 일반 객체는 전통적인 해시 테이블과 달리 성능 최적화를 위해 히든 클래스와 딕셔너리 모드라는 두 가지 모드를 사용한다.
    • Fast Mode(Hidden Class) : 객체가 처음 생성되고 속성이 추가될 때, V8은 히든 클래스를 만들어 속성의 메모리 오프셋을 관리한다. 고정된 메모리 크기를 사용하며 해시 테이블을 사용하지 않는다.
    • Slow Mode(Dictionary Mode) : 객체의 속성이 너무 많아지면 딕셔너리 모드로 전환되며 이때 해시 테이블이 사용된다.
      Map과 마찬가지로 2의 제곱수 크기를 사용하고, 충돌을 피하기 위해 50% 부하율을 유지하도록 동적으로 크기를 조절한다.

2. 해시 함수 

• Key가 주어지면 해시 함수는 이 키를 입력받아 고유한 정수 값(해시 코드)을 생성한다.

3. 인덱스 생성

• 생성된 해시 코드를 배열의 크기로 나눈 나머지를 계산하여 해당 버킷의 인덱스로 사용한다.

4. 데이터 저장

• 키-값 쌍은 계산된 인덱스에 해당하는 버킷에 저장된다.

5. 충돌 처리

• 두 개 이상의 서로 다른 키가 동일한 인덱스로 매핑될 때 '충돌'이 발생한다.
  일반적으로 각 버킷은 연결 리스트를 포함하며, 충돌이 발생하면 새로운 데이터를 해당 버킷의 연결 리스트에 추가한다. 데이터를 검색할 때는 키를 해시 함수에 통과시켜 해당 인덱스의 연결 리스트를 순회하여 원하는 키를 찾는다.

 

충돌이 발생할 경우 체이닝과 오픈 어드레싱 (위에 설명 참고)를 사용하여 충돌을 해결한다.

JS/TS 에서의 Hash

자바스크립트에서 해시 테이블은 객체(Object), Map, Set과 같은 내장 자료형을 통해 구현할 수 있고, 평균적으로 O(1)의 시간 복잡도로 키-값 쌍을 저장하고 빠르게 조회, 삽입, 삭제하는 데 사용된다.

Object는 가장 간단하지만, Map은 다양한 데이터 타입을 키로 사용할 수 있고, Set은 키와 값을 동일하게 저장하는 등의 장점이 있다.

 

Object

자바스크립트에서 가장 기본적이고 간단한 해시 테이블 구현체이다.

key-value 사전 구조의 기본형이며, 키는 문자열 또는 심벌만 가능하다.(숫자 키도 내부적으로 문자열로 취급 1 -> "1")

삽입 순서가 보존되지만 정수형 키처럼 보이는 이름은 먼저 정렬되는 등 세부 규칙이 존재한다.

(더 정확히는 객체의 프로퍼티는 ES6 이후 삽입 순서를 대체로 유지하지만, 원칙적으로는 순서가 중요하지 않다)

키를 통해 값에 접근, 수정, 삭제가 가능하며 속성(property)이라고도 부른다.

1. 선언
const myObject = {};

2. 삽입
myObject['apple'] = 1; 

3. 접근
myObject.apple

4. 조회
console.log(myObject['apple']);

5. 삭제
delete myObject['apple'];

6. 활용: 빈도 구하기
cost str = "banana";
const counts = {};

for (const ch of str){
  counts[ch] = (count[ch] || 0) + 1;
}

사용하기 좋은 경우

• 정적이고 단순한 데이터 구조: 키가 미리 정해져 있고 변경이 자주 발생하지 않는 작은 데이터 묶음을 저장할 때
• 키가 문자열 또는 심볼일 때
• JSON 데이터 처리: Object는 JSON 형식과 직접적으로 호환되므로 데이터를 주고받을 때 편리하다.
• 개별 속성에 로직이 적용될 때 : 특정 속성에 따라 다른 로직을 적용해야 하는 경우

키를 객체로 설정하면 자동 문자열화 되어 [object Object]로 형태가 무너진다. 객체를 키로 사용하고 싶다면 Map을 사용해야 한다.

(Hash)Map

키 타입에 제한이 없기 때문에 숫자, 문자열, NaN, 객체, 함수 등 모든 값을 키로 사용 가능하다.

또한 입력 순서를 보존하여 순회 시 삽입한 순서대로 나오며, 비교 규칙으로 * SameValueZero 을 사용한다.

대량, 빈번한 업데이트의 경우 Object보다 메모리/성능적으로 안정적이고 예측 가능한 경우가 많기 때문에 빈도수 집계나 캐시 등 대량 갱신/ 조회가 반복될 때나 순회 순서가 의미가 있을 때 Object보다 확실히 장점이 있다.

1. 생성
const m = new Map(iterableOfpairs?)

2. 조작
m.set(key, value)
m.get(key)
m.has(key)
m.delete(key)
m.clear()

3. 순회
for (const [k, v] of map)
map.keys()
map.values()
map.forEach((v, k) => ... )

4. 크기
m.size

사용하기 좋은 경우

• 다양한 자료형을 키로 사용해야할 때
• 잦은 추가 및 삭제 작업이 있을 경우
• 사용자 입력 데이터 처리 : 사용자로부터 입력받은 키-값 쌍을 다룰 때 프로토타입 체인과 충돌할 염려가 없어 안전

(Hash)Set

Set은 값의 유일성을 보장해주어 중복을 허용하지 않는 집합이다. 동등성을 확인하기 위해 SameValueZero을 사용한다.

핵심은 유일성 보장, 중복 제거, 입력 순서 보존 이다.

1. 생성
const s = new Set(iterable?)

2. 조작
s.add(v)
s.has(v)
s.delete(v)
s.clear()

3. 크기
s.size

4. 순회
for (const v of set)
set.forEach(v => ...)
set.values()

5. 전개
[...]

 

---

SameValueZero

자바스크립트의 내부 비교 알고리즘으로, 두 값이 동일한지 판단하는 데 사용된다.
=== (일치 비교)와 대부분 동일하게 동작하지만, 결정적으로 두 값을 비교할 때 둘 다 NaN이면 같다, 그리고 _+0과 −0도 같다_라고 보는 규칙이다.

 

• 타입이 다르면 : 다름
• 숫자(Number)
  • 둘 다 NaN이면 : 같음
  • +0과 −0 :  같음
  • 그 밖에는 수치값이 같아야 같음 (예: 1과 1은 같고, 1과 2는 다름)
• 문자열(String) : 글자(코드 유닛) 시퀀스가 완전히 같아야 같음
• 불리언(Boolean) : true는 true와만, false는 false와만 같음
• 심벌(Symbol) : 같은 심벌(동일 식별자)일 때만 같음
• 객체(Object) : 같은 참조(동일 객체)일 때만 같음 (모양이 같아도 참조가 다르면 다름)