들어가며
자료구조를 본격적으로 공부하려고 이 글을 써보려고 합니다. 자료구조를 제대로 공부해야만 훗날 근무를 할 때, 혹은 더 좋은 코드를 작성할 수 있다고 생각하기 때문입니다. 자료구에 대해 깊이 있는 개발자가 되기 위해 공부해보겠습니다.
Hash(해시)
Hash function: 임의 길이 데이터(input)를 암호화된 고정 길이(output)의 데이터로 매핑(전환)하는 함수
예를 들어 유저가 회원가입을 한다고 생각해 봅시다. 아이디와 비밀번호를 DB에 저장하게 될텐데 입력받은 데이터를 내부 DB에 저장해야 합니다. 하지만 입력값을 그대로 저장 할 경우 해커에 의해 뚫리게 되는 순간 개인정보 유촐로 이어질 수 있습니다. 이 때 해시 함수를 활용해서 비멀번호를 임의의 값으로 변환합니다. 임의의 값으로 변환하는 과정을 Hasing 이라고 합니다.
Hasing(해싱)
매핑 전 원래 데이터의 값을 키, 매핑 후 데이터의 값을 해시값 매핑하는 과정
- input 약간만 달라져도 정말 크게 변합니다.
- input 값이 다르면 해시값 항상 다릅니다.
Hash table(해시테이블)
Hash table: key를 value에 매핑하는 array 형태의 자료구조.
해시테이블은 해시 함수를 사용하여 데이터를 저장하고 검색하는 자료구조 입니다. 예시를 들어 전화번호부를 떠올리면 쉽습니다. 전화번호부에서 친구를 검색하면 이름과 전화번호가 나오는데, 이 때 이름=Key,전화번호=value 라고 생각하면 됩니다.
무언가를 찾기 위한 검색어 = 이름(key)
그 검색어로 나온 결과 = 전화번호(value)해시 테이블이 빠른 검색 속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다. 해시 테이블은 각각의 key값에 해시 함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 화용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.
예를들어 (Key,Value)가 ("John Smith",521-1234")인 데이터를 크기가 15인 해시 테이블에 저장한다고 하자. array[index] = "521-1234"로 전화번호를 저장하게 된다. 이러한 해싱 구조로 데이터를 저장하면 Key값으로 데이터를 찾을 때 함수를 1번만 수행하면 되므로 빠르게 데이터를 저장/삭제/조회 할 수 있다. 해시테이블의 평균 시간복잡도는 0(1) 이다.
