해시(Hash)와 해시테이블

# 정의

해시테이블은 해시함수를 이용하여 키를 해시값으로 매핑하고 이 해시값을 인덱스삼아

데이터를 key와 함께 저장하는 자료구조이다.

 

# 해시함수

해시 함수의 정의는 key를 고정된 길이의 hash로 변경해주는 역할을 한다.

이 과정을 해싱이라고 한다.

key ---(해시함수)---> 해시

해시는 저장위치 즉 인덱스가 된다.

 

# 해시테이블 구성

key : 해쉬 함수의 input이고, key를 그대로 인덱스로 사용할 경우에는 key의 길이만큼의 정보를

저장해야하는 공간도 따로 마련해야 해서 고정된 길이의 해시로 변경하는 것이다.

 

해시 함수 : key를 고정된 길이의 해시로 변경해주는 역할을 한다.

서로 다른 key가 해싱후 같은 해시 값이 나오는 경우가 있다. 이를 해시충돌이라고 한다.

이 충돌이 안나올수록 좋다.

 

해시테이블 : 해시값을 주소나 인덱스 삼아 데이터와 함께 저장하는 자료구조.

 

# 장점

-- 빠른 검색 속도 : 평균적으로 O(1)
-- 빠른 삽입 및 삭제 : 평균적으로 O(1)
-- 키-값 쌍
-- 가변 크기

 

# 단점

-- 공간 효율성 : 메모리 사용이 비효율적일 수 있다. 충돌을 방지하기 위해
추가적인 공간을 할당해야 할 수도 있다.
-- 충돌 : 두 개 이상의 키가 동일한 해시 값을 가지는 경우를 충돌이라 한다.
해결 방법으로는 개방 주소법, 체이닝이 필요하다.
-- 해시 함수의 중요성 : 좋은 해시 함수는 데이터를 균일하게 분산시키지만, 나쁜 해시 함수는 많은 충돌을 일으킨다.
-- 순서 정보 부재 : 데이터의 순서를 유지하지 않는다.

 

# 해시 충돌시 해결 방법

1. Chaining

체이닝은 저장소에서 충돌이 일어나면 기존 값과 새로운 값을 연결리스트로 연결

장점 : 미리 충돌을 대비해 공간을 많이 잡을 필요가 없다.

단점 : 같은 해쉬에 자료들이 많이 여녀되면 검색시 효율이 낮아진다.

 

2. 개방주소법

비어있는 해시를 찾아 저장하는 방법. 그래서 1:1관계를 유지하도록 한다.

선형으로 찾거나 제곱으로 탐색하는 등 여러 방법이 있음.

 

3. division method

기본적인 해시함수로 숫자로 된 키를 해시테이블 크기 m으로 나눈 나머지를 해시값으로 변환.