99클럽 코테 스터디 10일차 TIL + Hash Table

학습 키워드

- Hash Table

 

공부한 내용

Hash Table 해시 테이블

• 배열과 해시 함수(Hash function)를 사용한 Map의 구현체이다.
• Map의 구현체 중에서 가장 초기에 만들어진 구현체이고, HashMap과 LinkedHashMap은 HashTable에서 새로운 기능이 추가되거나 개선된 버전이라고 볼 수 있다.
• 해시 테이블(Hash Table)은 효율적인 검색과 삽입 연산을 위해 설계된 자료구조이다.
• 키(key) - 값(value) 쌍의 데이터를 저장하는데 사용되며, 각 키는 해시 함수를 통해 고유한 인덱스로 변환되어 배열 내에 저장된다.

해시 테이블(Hash Table)의 장단점

장점

• 빠른 검색 및 삽입 : Hash Table은 해시 함수를 사용해 데이터를 저장하므로 데이터에 접근하는 데 상수 시간(O(1))이 소요된다.

→ 매우 빠른 검색과 삽입이 가능하다.

• 유연한 크기 조정 : Hash Table은 데이터의 개수에 따라 자동으로 크기를 조정할 수 있다. 메모리 공간의 효율성을 유지하면서도 높은 성능을 유지할 수 있다.
• 다양한 용도로 활용 가능 : Hash Table은 캐싱, 데이터베이스 인덱싱, 중복 검사 등에 사용될 수 있다.

단점

• 해시 충돌 : 서로 다른 키가 동일한 해시 값에 매핑될 수 있는 해시 충돌이 발생할 수 있다. 충돌이 자주 발생하면 검색 및 삽입 연산의 성능이 저하될 수 있다.
• 메모리 사용량 : Hash Table은 해시 버킷과 해시 함수를 사용하기 때문에 일정한 메모리 공간을 필요로 한다. 특히 데이터의 수가 많을 경우 메모리 사용량이 증가할 수 있다.
• 순서의 랜덤화 : Hash Table은 키의 해시 값을 기반으로 데이터를 저장하기 때문에 데이터의 순서가 무작위로 보여진다. 데이터를 순차적으로 접근하는 것이 필요한 경우에는 Hash Table보다는 다른 자료구조를 고려하는 것이 좋다.

 

회고

발생한 문제

- Hash에 대해 공부했었는데 해시 테이블에 대한 공부가 부족하다고 느꼈다. 

 

해결 방법

- 해시 테이블에 대한 정리를 하고 공부를 해보았다. 그러나 아직은 어렵게 느껴진다. 

 

알게된 내용

- 해시 테이블이 Map의 초기에 만들어진 구현체인 것과 해시 테이블의 장단점을 알게 되었다.

 

 

참고 자료

- https://ittrue.tistory.com/153