Hashing: overview - 해싱: 개요

hyperskill - Hashing: overview 영어 원문

Hashing(해싱) 은 프로그래밍에서 넓게 사용되는 기술입니다.

당신이 인터넷을 넘어 메세지를 보내거나, 웹사이트에 로그인하거나,

혹은 당신의 컴퓨터에서 파일을 검색할 때,

hash function (해싱 기능) 을 사용 하는 겁니다!

하지만 해싱은 무엇이고, 해싱은 무엇을 하는 걸까요?

What is hashing? - 해싱이란?

---

형식적으로, hash function 은 임의의 크기로 고정되어 있는 맵핑 데이터를 사용 할 수 있게 해 주는 기능입니다.

이건 꽤 희미한 설명이므로, 실 생활과 비교하며 이들을 더 이해 해 봅시다.

당신의 친구 Paul이 전화번호 책을 가지고 있다고 가정 해 봅시다.

당신의 친구는 게으르고, 연락처에 모든 이름을 작성하는 데 많은 시간을 소비하지 않고 싶어 합니다.

예를 들어, 만약에 연락처에 John Smith 를 적어야 한다면,

Paul은 Jhn Smth 라고 대신 작성합니다.

여러가지 방면에서, 이 과정은 hashing(해싱) 과 비슷합니다.

우리는 이 과정을 "모든 모음을 제거한다" 라고 고려 할 수 있습니다.

해시 펑션에 적용된 몇 가지 입력을 hash value (해시 값) 이라고 부르며,

혹은 간단하게 hash(해시) 라고 부릅니다.

이 경우, Jhn Smth 는 John Smith 의 hash value 라고 합니다.

모든 해시 값(hash values) 들이 구별된다고 할 수는 없습니다. :

Tim Black, Tom Black 이라는 이름을 가진 두 사람을 생각 해 보세요.

이러한 두 이름의 해시 값은 Tm Blck 이 됩니다.

우리는 이러한 것을 충돌 (Collision) 이라고 부릅니다.

flowchart LR

subgraph original-원본
    direction LR
    John-Smith("John Smith");
    Jill-White("Jill White");
    Tom-Black("Tom Black");
    Tim-Black("Tim Black");
    Jane-Doe("Jane Doe")
end

subgraph Hash-Values-해시값들
    Jhn-Smth("Jhn Smth");
    Jll-Wht("Jll Wht");
    subgraph Coliision-충돌
        Tm-Blck1("Tm Blck");
        Tm-Blck2("Tm Blck"); 
    end
    Jn-D("Jn D");
end

John-Smith --> Jhn-Smth
Jill-White --> Jll-Wht
Tom-Black --> Tm-Blck1
Tim-Black --> Tm-Blck2
Jane-Doe --> Jn-D

우리의 경우, 우리의 예제와 실제 해시 펑션 간의 주요한 차이점은,

해시 값들이 고정된 값을 가지고 있지 않다는 겁니다.

더 정확한 예제로 삼는다면,

Paul 이 사람들의 이름을 순서대로 5 문자를 작성하는 겁니다.

John Smith 는 John S 로,

Tim Black 은 Tim Bl 으로,

이런 식으로 작성합니다.

5 문자로 이름을 작성하는 방식은 더 있습니다.

따라서, 우리는 충돌이 보장됩니다.

문맥을 살펴보았는데, 이거 충돌이 난다는 건지, 충돌이 나지 않는다는 건지 헷갈림

해시 함수의 경우에도 같습니다.

해시 함수들은 정말로 거대할 수 있는 입력값을 받으며,

고정된 크기의 무언가를 반환하므로,

충돌을 완벽하게 피할 수 있는 방식은 없습니다.

위의 문맥으로, 여러 방식으로 해시 함수가 적용 될 수 있으므로, 충돌은 거의 무조건 일어난다는 의미로 된다.

Applications of hash functions - 해시 함수의 응용 사례

---

우리가 시작 부분에서 말했듯이, 해시 함수들은 정말 많은 응용 사례들을 가지고 있습니다.

가장 중요한 것들 몇 개를 살펴 봅시다 :

Message digests - 메세지 다이제스트

인터넷을 넘어 당신의 친구에게 메세지를 보내고 싶지만,

친구에게 메세지가 도달하기 이전에 내부 콘텐츠가 변경 될 수 있음을 무서워 한다고 말해 봅시다.

당신이 할 수 있는 것 중 하나는 메세지를 전송하기 전에 메세지에 대한 해시 값을 계산하는 것입니다.

당신의 친구들이 메세지를 받았을 때,

친구는 당신처럼 동일한 해시 함수를 사용하여 메세지의 해시 값을 계산 할 겁니다.

그리고 나서 당신은 두 개의 해시를 비교하고 이들이 동일한지 확인할 수 있습니다.

이에 대해 사용되는 해시 함수들은 충돌을 찾기 어렵다는 속성을 가지고 있습니다.

이들은 서로 다른 속성을 가지고 있습니다.

Password Storage - 패스워드 저장소

왜 당신이 웹 사이트에서 당신의 비밀번호를 잊었을 경우,

사이트에서 당신의 패스워드를 전송하는 선택지를 가지지 않고, 리셋시키는 지 궁금 해 본 적 있나요?

다시 비밀번호를 보내기 위해서는,

사이트들이 기본 텍스트로 데이터베이스에 비밀번호를 저장해야 합니다.

이렇게 한다면, 만약 누군가 패스워드 데이터베이스에 대한 접근 권한을 얻을 경우,

이들은 모든 계정의 비밀번호를 쉽게 훔쳐 갈 겁니다!

이럴 때 웹사이트가 하는 것은 당신 패스워드의 해시를 저장하는 겁니다.

당신이 로그인하기 위해 패스워드를 전송했을 때,

이들은 이 비밀번호에 대한 해시를 계산하고, 사이트가 저장 한 패스워드와 동일한지 확인합니다.

이러한 경우, 충돌을 찾는 것은 그렇게 큰 문제가 아닙니다.

만약 누군가 당신의 비밀번호에 대한 해시를 찾았을 경우,

그러한 누군가는 그곳으로 부터 당신의 비밀번호를 알 수 없다는 것을 알아야 합니다.

Hash tables - 해시 테이블

일상적인 프로그래밍에서 저 흔하게 사용되는 것은 Hash Table (해시 테이블) 입니다.

해시 테이블은 빠르고, 해싱을 사용하는 편리한 데이터 구조입니다.

해시 테이블로, 엘리먼트 검색, 삽입, 제거를 할 수 있습니다.

해시 테이블의 뒤에 있는 주요한 생각은,

배열에 있는 데이터를 해시 값을 사용하여 인덱싱한다는 것 입니다.

예를 들어, 만약 당신이 전화번호부를 저장하기 위해 해시 테이블을 사용하고 싶을 때,

Tm Blck 이라는 인덱스에 (Tim Black, 0123456789) 쌍을 저장 할 수 있습니다.

그리고 나서, Tim 의 전화번호를 찾기 위해서,

단지 Tm Blck 인덱스를 검색하면 됩니다.

해시 테이블에 사용되는 해시 함수들은 메세지 다이제스트나 패스워드 저장소에 사용되는 것 보다는 덜 제한적입니다.

그리고 이러한 경우들의 해시 값(Hash Values)들은, 일반적으로, 숫자입니다.

추후에 다른 주제에서 Hash Table 에 대한 것을 더 가까이 살펴보겠습니다.

Conclusion - 결론

---

이제 당신은 해싱과 해시 함수에 대한 생각을 하게 되었으며,

이들이 무엇인지, 어디에 사용 할 수 있는지 알게 되었습니다.

해시에 대한 중요성을 강조하는 데에는 지금이 충분합니다.

이에 대한 다음 주제로는, 해시 함수와 해시 테이블, 충돌에 대해서 더 자세히 배울 겁니다.

words to remember

---

arbitrary : 임의의, 멋대로인, 독단적인