Hash Table

Hash Table

해쉬 테이블은 키, 값 쌍을 저장하고 있는 자료 구조
키를 저장할 때에 메모리 공간을 덜 사용할 수 있도록, 키를 “해쉬 함수(Hash Function)”라는
함수를 통해 특정 숫자 값의 인덱스로 변환한다.
해쉬테이블은 필요할 때에만 메모리 크기를 늘리고, 가능한 작은 크기를 유지한다.

 

 

해쉬 함수

데이터의 효율적 관리를 목적으로 임의의 데이터를 고정된 길이의 데이터로 매핑하는 함수
매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value),
매핑하는 과정 자체를 해싱(hashing)이라고 한다.

 

시간복잡도(Time Complexity)

자료구조	가져오기	추가하기	삭제하기
Hash Table	O(1)	O(1)	O(1)

인덱스를 매개로 했기 때문에 데이터의 탐색, 추가, 삭제가 엄청 빠르다. 그러나 해시충돌이 있으면 bucket의

모든 tuple까지 탐색할 수도 있기 때문에 시간복잡도는 O(n)까지 늘어난다.

또 리사이즈를 하는 순간에도 모든 데이터를 재배치하기 때문에 O(n)이 걸린다.

 

리사이징(Resizing)

일반적으로 해시테이블의 사용률이 75% 이상으로 커지면 해시 테이블을 리사이징 하는데 대략 2배 정도의 크기로 공간을 늘린다.

리사이징 하여 크게 만든 이후에 해시 함수를 사용하여 기존 테이블에 있던 데이터를 새로운 해시 테이블에 다시 저장하게 된다.

 

해시 충돌(collision)

해시 테이블의 충돌이란 다른 키 2개를 해시 함수에 넣었는데 같은 값이 나오는 경우이다. 좋은 해시 함수를 쓸수록 충돌이 발생할 확률이 낮아지지만 많은 양의 데이터를 처리하다 보면 충돌이 발생하는 경우가 발생할 수 있다. 충돌이 발생할 때 해결하는 방법으로는 충돌하는 데이터를 연결 리스트(Linked List)로 처리하는 방법이다.

 

같은 값이 나왔을 때 해당 주소에 이미 데이터가 있으면 그 데이터를 연결 리스트로 연결하는 것이다. 이 방법의 단점은 충돌 횟수가 늘어나서 연결 리스트의 길이가 길어질수록 해시 테이블의 성능이 매우 낮아진다는 것이다. 해시 테이블은 데이터를 빨리 찾고 삭제하고 입력하는데 장점이 있는데 충돌 횟수가 늘어나서 연결 리스트가 길어지게 되면 리스트를 순회하는 과정이 길어지면서 성능이 떨어지게 된다.