16일까진 정해진 일정이 있어서 조금 소홀 할 수 있지만 할 수 있는 공부는 계속 진행하고 있다.
카카오톡 공채시험 대비 알고리즘 문제 풀기나 JS와 React 공부등 만족할 만큼은 아니지만 할 수 있는 만큼 진행중에 있다.
10월에 서울로 올라가기로 한만큼 올라가면 온전히 내 시간으로 공부할 수 있지 않을까 싶다.
해시배열
연관 배열(associative array)의 일종으로, 키(key)를 값(value)에 매핑할 수 잇는 자료구조이다.
※연관 배열(associative array) : (키,값) 쌍으로 구성된 추상 자료형으로 연관 배열에서 키는 유일한 값을 갖는다.
맵(map),사전(dictionary)으로 불리기도 한다.
해시테이블
연관 배열의 구현 형태로, 해시, 해시 함수, 해싱, 버킷, 슬롯 등의 개념을 포함한다.
버킷(bucket)과 슬롯(slot)
해시 테이블에서 값은 버킷(bucket)과 슬롯(slot)으로 이루어진 형태의 테이블에 저장된다.
- 버킷 : 여러개의 슬롯을 저장하는 레코드 형태의 자료구조로, 버킷의 갯수는 고정적이다.
- 슬롯 : 해시와 매핑되는 값이 저장되어 있는 공간으로, 하나의 버킷 안에는 여러개의 슬롯이 존재할 수 있다. 슬롯은 하나 이상의 값을 저장할 수 있다.
해시
해시 함수(hasy function)를 통해 얻는 값으로, 해시를 인덱스 또는 주소로 삼아 직접 접근이 가능하도록 한다.
(해시 값(hash value) 또는 해시 코드(hash code)라고도 한다.)
해시를 이용해서 해시 테이블의 버킷 또는 슬롯에 접근한 뒤 탐색, 삽입, 삭제등의 연산을 수행한다.
해시 함수
임의의 길이의 데이터(key)를 고정된 길이의 데이터(해시)로 매핑하는 함수.
매핑 전 원래 데이터의 값을 키, 매핑 후 데이터의 값을 해시라고 한다.
즉, key -> hash로 매핑 시켜주는 함수를 해시 함수라고 한다.
좋은 해시 함수의 조건
- 해시 값이 해시 테이블 주소 영역 내에서 고르게 분포 되어야 한다.
- 충돌이 적어야 한다.(중복값 최소)
- 계산이 빨라야 한다.
해싱(hashing)
key -> hash -> value 로 값을 탐색하는 과정, 해시 함수를 사용한 탐색
해싱은 매우 빠른 검색을 위한 용도로 사용되며 평균적으로 O(1)의 탐색시간을 갖는다.
해싱의 성능은 해시 함수의 성능과 해시 테이블의 크기에 따라 달라진다.
해시충돌(hash collision)
해시 함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 경우로, h(k1) === h(k2) 성립하면 해시 충돌이 발생 했다고 한다.(h:해시함수 / k1,k2 : 임의의 key값)
이때, k1과k2를 동의어(synonym)라 한다.
해싱을 할 때, 해시 충돌이 발생할 수 있기 때문에 해시 충돌에 대한 처리가 반드시 필요
매우 큰 집합을 비교적 작은 크기의 공간에 매핑 시킬 때, 해ㅑ시 충돌이 발생할 수 있따.
이 경우 table size가 입력 가능한 집합의 크기보다 작기 때문에 완전히 해시 충돌을 피할 수 있는 알고리즘은 존재하지 않음
John Smith, Sandra Dee에 대한 해시값이 동일하기 때문에 해시 충돌이 발생
