해시의 등장 배경

배열

• 내부 인덱스를 이용하여 자료의 검색이 한번에 이루어지기 때문에 빠른 검색 속도를 보인다.
• 반면 데이터의 삽입, 삭제 시 많은 데이터가 밀리거나 빈자리를 채우기 위해 이동해야 하기 때문에 많은 시간이 소요된다.

연결리스트

• 삽입, 삭제 시 인근 노드들의 참조 값만 수정해 줌으로써 빠른 처리가 가능하다.
• 처음 노드, 마지막 노드 이외의 위치에서 데이터를 삽입, 삭제할 경우나 데이터를 검색할 경우에는 해당 노드를 찾기 위해서 처음부터 순회 검색을 해야하기 때문에 데이터의 수가 많아질수록 효율이 떨어질 수밖에 없는 구조다.

이와 같이 배열과 연결리스트의 한계를 극복하기 위해 제시된 방법이 Hash이다.

1. Hash란?

해시(Hash)란 단방향 암호화 기법인 해시함수를 이용하여 생성된 고정된 길이의 비트열을 의미한다.

• 단방향 암호화 기법 : 암호화는 수행하지만 복호화는 불가능한 암호화 기법
• 해시 함수 :입력된 임의의 데이터를 고정된 길이의 데이터로 변경하여 출력해주는 함수
• 키(Key) : 변경 전 원래 데이터 값
• 해시값(Hash value) : 변경 후 데이터의 값
• 해싱(Hashing) : key와 value로 변환되는 과정
• 해시충돌(Hash Collision) : 변환이 이루어진 후 변환 값이 중복되는 경우

해시 충돌을 해결할 수 있는 방법에는 대표적으로 체이닝(Chaining), 개방 주소법(Open Addressing)이 있다. 해시 값 자체를 index로 사용하기 때문에 평균 시간 복잡도가 O(1)로 매우 빠름

특정 데이터가 저장되는 인덱스는 그 데이터만의 고유한 위치이기 때문에 삽입 시 다른 데이터의 사이에 끼어들거나 삭제 시 다른 데이터로 채울 필요가 없으므로 삽입과 삭제 시 데이터의 이동이 없도록 만들어진 구조이다.

2. HashTable, HashMap이란?

해시 함수를 사용하여 키를 해시값으로 매핑하고 이 해시값을 index 삼아 데이터의 값(value)를 키와 함께 저장하는 자료구조를 해시 테이블(Hash Table) 혹은 해시 맵(Hash Map)이라고 한다. Java에서는 이 둘의 자료구조가 다르다. 이 때 데이터가 저장되는 곳을 버킷(bucket) 또는 슬롯(slot)이라고 한다.

해시테이블의 기본 연산 : 삽입, 삭제, 탐색

Java에서 HashTable과 HashMap의 차이를 알고싶다면?

3. Hash Function

해시 함수란 임의의 길이를 갖는 데이터를 고정된 길이의 데이터로 변환시켜주는 함수이다.

• 계산이 복잡하지 않고 키값에 대해 중복없이 해시값을 고르게 만들어 내는 함수가 좋은 함수
  -> 충돌이 일어나지 않을수록 좋다

• 키들이 어떤 특정한 패턴을 가지더라도 해시함수 값이 불규칙적이 되도록 하는게 바람직함
  -> 해시 함수 값이 키의 특정 부분에 의해서만 결정되지 않아야함

4. Hash Collision

충돌이란 서로 다른 문자열이 해시 함수를 통하여 해싱한 해시값이 중복인 경우를 말한다.

• 같은 해시값을 갖는 데이터가 생간다는 것은, 특정 해시값의 버켓에 데이터가 집중된다는 뜻이다.
• 너무 많은 해시 충돌은 해시테이블의 성능을 떨어뜨린다.
• 충돌이 많아질수록 탐색의 시간복잡도가 O(1)에서 점점 O(n)에 가까워지게 된다.

충돌에 의한 해결 방법은 크게 두 가지 방식이 있다
- chaining
- open addressing

4.1 Chaining (체이닝)

• 버켓 내에 연결리스트를 할당하여, 버켓에 데이터를 삽입하다가 해시 충돌이 발생하면 연결리스트로 데이터를 연결하는 방식

• Sandra Dee라는 사람의 연락처를 삽입할 때, 충돌이 발생하여 버켓 내에서 연결리스트로 데이터를 연결한다.

4.2 Open Addressing (개방 주소법)

• Chaining의 경우 충돌이 발생해도 연결리스트로 계속 늘려가기에, 데이터의 주소값은 바뀌지 않는다. (Closed Address)
• 개방주소법의 경우, 해시 충돌이 일어나면 다른 버켓에 데이터를 삽입한다.
• 대표적으로 3가지가 있다
  • 선형 탐색: 해시 충돌 시 다음 버켓, 혹은 몇 개를 건너뛰어 데이터를 삽입
  • 제곱 탐색 : 해시 충돌 시 제곱만큼 건너뛴 버켓에 데이터를 삽입
  • 이중 해시: 해시 충돌 시 다른 해시 함수를 한 번 더 적용한 결과를 이용

5. 해싱 알고리즘 활용

5.1 블록체인과 해시 함수

블록체인에서 해시 함수는 '암호화' 역할을 한다. 해시값 비교를 통해서 위변조 여부를 판별하고, 무결성을 검증하는 데 사용된다.
비트코인의 블록체인에 사용된 해시 함수는 SHA-256(Secure Hash Algorithm-256)이다.

블록체인에서 해시 함수를 사용하는 이유

1. 해시 함수로 암호화한 값을 이용하여 입력값을 파악할 수 없다. -> 단방향 암호화 기법
2. 출력(결과)값으로 입력값을 찾을 수 있는 복호화 공식이 없다.
3. 결과 값이 중복될 가능성이 현저히 낮다.

5.2 JWT 토큰 암호화 알고리즘

JWT 토큰이란?

HS256 알고리즘

HS256는 JWT 토큰의 암호화 알고리즘으로 많이 쓰이는 암호화 알고리즘이다.

HS256 알고리즘을 이용한 JWT의 세부 동작 방식
1. 서버에서 Header, Payload는 Base64로 인코딩된다. (Base64는 복호화가 가능한 알고리즘)
2. Signature는 "Header + Payload + secret 값"을 HS256 알고리즘으로 암호화한다.

HS256( Base64(Header) + Base64(Payload) + secret key)

가 된다.

3. 생성된 Header, Payload, Signature로 JWT 토큰을 만들어 클라이언트로 보내고, 클라이언트는 로컬 스토리지에 토큰을 저장한다,
4. 클라이언트는 서버에 요청이 있을 경우, 토큰과 요청 내용을 같이 보낸다.
5. 서버에서는 Header와 Payload를 Base64 알고리즘으로 복호화한 뒤, 서버만 알고 있는 개인 키(secret 값)을 가지고 다시 HS256 알고리즘을 이용해 암호화하고, 클라이언트에서 보낸 토큰과 같은지 유효성 검증을 한다.