해시테이블이란
key - value로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조입니다
해시테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 버킷을 사용하여 데이터를 저장하기 때문에
해시테이블은 각각 key에 해시함수를 적용하여 고유한 index를 생성하고 이 index를 활용해 값을 저장하거나 검색 합니다
*실제 값이 저장되는 장소를 버킷 또는 슬롯이라 한다
평균 O(1) 의 시간 복잡도로 접근할 수 있다 체이닝으로인해 O(n) 까지 증가할 수 있다
list / set / map 의 차이에 대해 설명하세요
list - 순서가 있는 요소들의 컬렉션
/ 중복된 요소 허용
/ 순서를 보장한다 추가된 순서대로 저장되고 인덱스를 통해 접근관리를할 수 있다
set- 고유한 요소들의 컬렉션
/ 중복된 요소를 허용하지 않는다
/ 순서를 보장하지 않으며 특정 구현체에 따라 순서가 달라질 수 있다
map - 키 -값 쌍을 저장하는 컬렉션
/ 키는 중복불가 값을 중복가능하다
/ 순서를 보장 하지 않으며 특정 구현체에 따라 순서가 달라질 수 있다
B+Tree 가 무엇인가요
B Tree의 변형으로 모든 값이 리프노드에 저장됩니다
모든 리프노드는 링크드 리스트의 형태로 저장되어있습니다
- 장점
- 탐색 삽입 삭제가 평균적으로 O(log n)의 시간 복잡도를 가진다
- 리프 노드에만 데이터를 저장하기 때문에 또한 그 리프 노드들이 링크드리스트 형태로 저장되기 떄문에
선형 검사를 수행할수 있습니다 또한 효율적인 메모리 사용과 대용량 데이터처리에 유용합니다
- 단점
- b tree는 루트에서 검색이 끝날수도 있지만 무조건 리프노드까지 내려가야한다
- 구현이 상대적으로 복잡하고 내부노드는 키 만 저장되고 리프노드에 같은 키 값이 각각 저장됩니다
추가적인 인덱스 공간이 필요합니다
HashMap은 어떤 식으로 동작하나요
HashMap은 각 키를 해시 함수에 통과시켜, 해당 키를 해시 코드로 변환합니다.
이 해시 코드는 배열의 인덱스를 결정하는 데 사용됩니다
키 hashCode() 메서드로 해시코드를 생성하고 생성된 해시 코드를 HashMap의 배열 크기로 나눈 나머지를 계산하여,
해당 키-값 쌍이 저장될 배열의 인덱스를 결정합니다
이때 해당 인덱스에 이미 값이 저장되어 있는지 확인합니다.
만약 이미 저장된 값이 있다면, 이는 충돌이 발생한 것으로 체이닝 기법을 사용하여,
기존의 값이 저장된 위치에 새로운 키-값 쌍을 리스트에 추가합니다.
또는 개방 주소법을 사용하여 빈 공간을 찾아 값을 삽입합니다
Hash충돌이 발생하는 경우는 무엇인가요
해시 충돌은 여러개의 키의 해시 함수의 출력값이 동일한 인덱스를 가지는 상황에서 발생합니다.
즉, 서로 다른 데이터 입력이 동일한 해시 값을 출력하게 되는 경우를 말합니다
Hash 충돌시 내부 데이터탐색은 어떻게 하나요
두가지 방법이 있는데
체이닝 (Chaining): 가장 일반적인 충돌 처리 방식으로,
같은 해시 인덱스에 여러 값을 저장하기 위해 각 배열 요소가 리스트(또는 다른 자료구조)로 연결되는 방식을 사용합니다.
충돌이 발생하면, 해당 인덱스의 리스트에 새 요소를 추가합니다.
개방 주소법 (Open Addressing): 충돌이 발생했을 때, HashMap은 다른 빈 인덱스를 찾기 위해 탐색을 시도합니다.
이 방법에는 선형 탐사, 이중 해싱, 제곱 탐사 등이 포함될 수 있습니다.
개방 주소법은 배열을 채우는 빈 공간을 이용하여 충돌을 해결합니다.