Hash Table

해싱이란 해시함수를 사용하여 고정된 크기의 값으로 변환하는 작업입니다.

해싱을 이용해 데이터를 저장하는 자료구조를 Hash Table이라합니다.

이는 기존 자료구조인 이진 탐색트리나 배열에 비해 빠른 속도로 탐색, 삽입, 삭제를 할 수 있습니다.

 

Collection	Data Structure	Add	Contains	Remove	Next
HashSet	Hash Table	O(1)	O(1)		O(h/n)
ArrayList	Array	O(1)	O(n)	O(n)

 

Hash Table이란 해시함수를 사용해 변환한 값을 index로 삼아 key, value를 저장하는 자료구조입니다.

기본 연산으로는 탐색,삽입 삭제가 있습니다.'

해시테이블을 이해하기 위해선 '충돌(Collision)'에 대해 이해해야합니다.

 

적재율

적재율이란 해시테이블의 크기대비하여 키의 갯수를 의미하는 것입니다.

현재 저장된 키의 갯수를 K, 해시 테이블의 크기를 N이라 했을 때 적재율은 K/N입니다.

적재율이 1초과인 경우 충돌이 발생하게 되는데 이는 저장된 데이터가 많지만 해시테이블의 크기는 이를 수용할 수 없는 크기란 의미입니다.