Hash란?

해시 함수(hash function) 또는 해시 알고리즘(hash algorithm) 또는 해시함수알고리즘(hash函數algorithm)은 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드, 해시 체크섬 또는 간단하게 해시라고 한다.

• wikipidia

• Hash의 용도 중 하나는 Hash table이라는 자료구조에 사용되며, 매우 빠른 데이터 검색을 위한 컴퓨터 소프트웨어에 사용된다.

Hash 간단 그림

• Hash는 잘게 다진 고기라는 뜻의 유래로써, 간단하게 설명하자면

<aside> 💡 해시테이블은 해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인(인덱스) 또는 주소삼아 데이터를 key와 함께 저장하는 자료구조이다. 단순하게 key - value로 이루어진 자료구조라고 생각하면 된다.

</aside>

Hash function

• Hash Function은 key를 고정된 길이의 Hash로 변경해주는 역할을 하며, 이 과정을 hashing이라고 한다. key를 hash function에 input으로 넣어서 Output으로 나오는 것이 Hash라고 생각하면 되고, 이 Hash가 저장위치가 된다고 생각하면 된다.

Hash Table의 구성

• key
  • 고유한 값, hash function의 Input이 된다.
  • key값을 그대로 저장소의 색인으로 사용할 경우 key의 길이만큼의 정보를 저장해야한 공간도 따로 마련해야 하기 때문에(key의 길이가 제각각 일수 있다.), 고정된 길이의 해시로 변경한다.
• hash function
  • key를 고정된 길이의 hash로 변경해주는 역할을 한다.
  • 서로 다른 key가 hashing 후 같은 hash값이 나오는 경우가 있다. 이를 해시충돌이라고 부른다. 해시 충돌 발생확률이 적을 수록 좋다.
  • 해시충돌이 균등하게 발생하도록 하는것도 중요하다. 모든 키가 같은 해시값이 나오게 되면 데이터 저장시 비효율성도 커지고 보안이 취약해져서 좋지 않다.
• value
  • 저장소(버킷,슬롯)에 최종적으로 저장되는 값으로, hash와 매칭되어 저장되어진다.
• hash table
  • 해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 주소 또는 색인 삼아 데이터(value)를 key와 함께 저장하는 자료구조이다.
  • 데이터가 저장되는 곳을 버킷, 슬롯이라고 한다.

<aside> 💡 해시는 색인 또는 인덱스, hash function은 key->hash로 만들어 주는 함수, 해시테이블은 hash를 주소로 삼아 데이터를 저장하는 자료구조이다.

</aside>