Hash
Hash는 크게 Hash, Hash functiong, Hashing, Hash table로 4가지로 나뉘어진다.
Hash
해시는 데이터를 다루는 기법 중 하나로 검색과 저장을 아주 빠르게하는 자료구조이다.
데이터를 저장할 때 Key-Value 형태로 데이터가 존재하고, Key값이 배열의 인덱스로 저장되기 때문에 검색과 저장이 빠르게 일어난다.
해시의 특징은 다음과 같다.
- Hash는 임의의 크기를 가진 데이터(Key)를 고정된 크기의 데이터(Value)로 변화시켜 저장하는 것이다.
- Key에 대한 해시 값을 사용해 값을 저장하고 Key-Value 쌍의 개수에 따라 동적으로 크기가 증가하는 연관 배열(associate array)이다.
- Key에 대한 해시 값을 구하는 과정을 Hashing이라고 부른다. 이때 사용하는 함수(알고리즘)을 해시함수라고 한다.
- 해시 값 자체를 Index로 사용하기 때문에 평균 복잡도가 O(1)로 매우 빠르다.
Hash function, Hashing
해시 함수는 Key값을 고정된 길이의 hash로 변환하는 역할을 한다.
해시 함수는 다음과 같은 특징이 있다.
- 해시 함수는 임의의 길이의 데이터를 입력받아 일정한 길이의 비트열로 반환시켜주는 함수이다.
- 원래의 값이나 Key를 색인하는데 사용되며, 그 Value가 관련된 데이터가 검색될 때마다 다시 사용된다.
- 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.
- 계산이 복잡하지 않고 Key값에 대해 중복없이 해시 값을 고르게 만들어내는 함수가 좋은 함수이다. 충돌이 일어나지 않을수록 좋다.
- 문자열(String)을 받아서 숫자를 반환하는 함수이다. 함수는 문자열에 대해 숫자를 Mapping(할당)한다.
대표적으로 나눗셈법(Division Method)와 곱셈법(Multiplication Method)가 있다.
해시 함수에서 key값을 hash로 변환하는 과정을 해싱(Hashing)이라고 한다.
해싱은
- Key 값에 직접 산술적인 연산을 적용해 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근한다.
- 매핑하는 과정을 말한다.
- 해시테이블을 이용해 탐색한다.
해시 함수에서는 Key값을 해싱 과정을 통해 해시 값(hash value) 또는 해시코드(hash code)로 변경하며 이 해시 값이 저장위치가 된다.
서로 다른 Key가 같은 hash가 되는 경우를 해시 충돌(Hash Collision)이라고 하는데, 해시 충돌을 일으키는 확률을 최대한 줄이는 함수를 만드는 것이 중요하다.
Hash Table
해시 테이블은 연관 배열구조를 이용해 데이터를 Key와 Value로 저장하는 자료구조이다.
해시 테이블은 해시 함수를 사용해 index를 bucket이나 slot의 배열로 계산한다.
Keys [이름] -> hash function [해싱 과정] -> buckets [index(hash value) : data]
- bucket 또는 slot : 데이터가 저장되는 곳이다.
- 해시테이블의 기본 연산 : 삽입, 삭제, 탐색이다.
장단점
장점
- 중복을 제거할 수 있다.
- 데이터 캐싱, 보안에 주로 사용된다.
- 배열의 인덱스로 접근하기 때문에 삽입, 삭제등의 연산이 빠르다.
단점
- 공간 복잡도가 커진다.
- 충돌이 발생할 수 있다. 충돌이 발생할 경우 복잡도는 O(n)에 가까워진다.
- 순서가 있는 배열에는 어울리지 않는다.
참고자료
https://coding-sojin2.tistory.com/entry/%ED%95%B4%EC%8B%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-hash-algorithm
https://power-overwhelming.tistory.com/42
https://velog.io/@hanif/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%95%B4%EC%8B%9C
