“해시(Hash)”

#1. 해시(Hash)란 무엇인가?

데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터(Key)를 고정된 길이의 데이터(Value)로 변화시켜 저장하는 것

해시(Hash)란 데이터를 다루는 기법 중 하나로, 데이터를 검색할 때 사용할 key값과 실제 데이터인 value값이 한 쌍으로 존재하는 형태입니다.

Key에 대한 해시 값을 사용하여 값을 저장하고, Key-Value 쌍의 갯수에 따라 동적으로 크기가 증가하는 연관 배열(associate array) 입니다.

key값은 배열의 index로 변환되기 때문에 검색과 저장의 평균적인 시간 복잡도가 O(1)에 수렴하게 되므로 검색과 저장이 아주 빠르게 진행되는 것이 특징입니다.

Key값을 사용함으로써 해시 테이블 크기와 상관 없이 데이터에 빠르게 접근할 수 있으며, 모든 데이터를 살피지 않아도 검색, 삽입/삭제를 빠르게 실행할 수 있다는 장점이 있습니다.

#2. 해시 함수

Key에 대한 해시값을 만드는(구하는) 함수(알고리즘)

Key에 대한 해시값을 구하는 과정을 **‘해싱(Hashing)’**이라고 합니다.

이 해싱(Hashing) 과정에서 사용하는 함수를 **‘해시 함수’**라고 합니다.

[좋은 해시 함수의 조건]

#3. 충돌 (Collusion)