archive

해싱(Hashing)이란, 임의의 길이의 값을 해시함수를 사용하여 고정된 크기의 값으로 변환하는 작업이다. 해싱을 사용하여 데이터를 저장하는 자료구조를 해시 테이블이라고 한다. 이진 탐색 트리나 배열에 비해서 빠른 속도로 탐색/삽입/삭제가 가능하다. 해시함수를 사용하여 변환한 값을 index로 삼아, key-value를 저장한다. 기본연산으로는 Search, Insert, Delete가 있다. ● Direct Address Table 키 값을 주소(인덱스)로 사용하는 테이블이다. - 장점 탐색, 삽입, 삭제가 O(1)에 가능하다. - 한계점 최대 키 값을 알고 있어야 한다. 키 값이 퍼져있다면 메모리 낭비됨. ● Hash Table 해쉬함수를 이용해 특정 해쉬값을 알아내고 이를 인덱스로 변환하여 해당 위..