해시(HASH)

• 해시는 저장 또는 검색 등에서 자주 활용되는 자료구조이다.

1. 특정한 함수(알고리즘)를 통해서 값을 추출하고 활용.
2. 함수(알고리즘)를 어떻게 구현하는지에 따라 사용 용도와 성능이 달라짐.
3. 암호, 블록체인, 메시지 인증 코드 등 활용됨.

• 해시는 입력 데이터를 고정된 길이의 데이터로 변환된 값을 말한다.

1. 해시 값, 해시 코드, 체크섬 이라고도 불림.
2. 해시 함수는 다양한 길이의 입력 데이터를 고정된 길이의 출력으로 매핑하고 결과적으로, 해시 함수를 통해 변환된 정수 값은 데이터의 고유한 식별자(Key) 역할을 하며 이는 배열의 인덱스, 데이터의 위치를 결정하거나 데이터 값을 저장 및 검색하는 데 활용된다.

01. 자료구조의 특징

• 키(Key)에 데이터(Value)를 매핑할 수 있는 데이터 구조이다.
• 해시 함수를 통해 키의 데이터를 배열에 저장할 수 있는 주소(인덱스 번호)를 계산한다.
• 키를 통해서 저장된 데이터를 빠르게 찾고, 저장 및 탐색 속도가 획기적으로 빨라짐.

알아둘 용어

1)해시 함수(Hash Function)

임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수

• 해시 함수는 입력받은 데이터를 해시 값으로 출력시키는 알고리즘을 말한다.

이렇게 출력된 해시 값은 알고리즘에 따라 다양한 결과를 보인다. 그렇기 때문에 함수는 목적에 맞게 다양하게 설계되고 자료구조, 캐시, 검색, 에러 검출, 암호 등으로 활용된다.

2)해시 테이블(Hash Table)

키 값의 연산에 의해 직접 접근이 가능한 데이터 구조

• 해시 테이블은 키와 값을 함께 저장해 둔 데이터 구조이다

테이블에 데이터를 저장할 때 위치는 무작위로 지정되어 작성된다 따라서 중간에 여유 공간이 발생할 수 있다.

• 추가 용어

1. 버킷(bucket) : 하나의 주소를 갖는 파일의 한 구역, 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수
2. 슬롯(slot) : 한 개의 레코드를 저장할 수 있는 공간, 한 버킷 안에 여러 개의 슬롯이 있다

3)해싱(Hashing)

해싱은 해시 함수에서 해시를 출력하고, 해시 테이블에 저장하는 과정까지의 행위를 말한다.

해시 자료구조의 장, 단점과 용도

1) 장점

1. 데이터 저장 / 읽기 속도가 빠르다 (검색 속도가 빠름)
2. 해시는 키에 대한 데이터가 있는지 확인이 쉬움

2) 단점

1. 일반적으로 저장공간이 많이 필요
2. 여러 키에 해당하는 주소(인덱스)가 동일한 경우 충돌을 해결하기 위한 별도 자료구조 필요

3) 주요 용도

1. 검색이 많이 필요한 경우
2. 저장, 삭제, 읽기가 빈번한 경우
3. 캐쉬 구현

자바에선 주로 HashMap 클래스를 사용한다.