해시테이블이란?
해시테이블이란 키(key)와 값(value)를 저장하는 자료구조입니다.
시간복잡도가 O(1)이기 때문에 많이 사용하는 자료구조 중 하나이며 해시테이블이 빠른 이유는 내부적으로 배열을 사용하기 때문입니다.
키(key)값에 해시 함수를 적용해서 index가 생성되고 index를 활용하여 값을 저장하거나 찾습니다.
해시 값이 충돌하는 경우
해시 값을 생성하여 key값으로 적용하게 되는데 아무리 완벽하게 만들었다고 하더라도 충돌이 나는 경우가 있습니다. 충돌이 날 경우 해결하는 방법 2가지가 있습니다.
체이닝
체이닝이란 해당 인덱스에 값이 있다면 연결리스트를 생성하여 key-value로 저장하는 방법 입니다.
개방주소법
개방주소법이란 해당 인덱스에 값이 존재한다면 빈 인덱스를 찾아 key-value값을 저장하는 방법 입니다.
개발자 성장일기