조회, 삽입, 삭제 모든 부분에서 성능이 필요하다면 해시테이블을 고려해보자

• 조회보다 삽입 및 삭제가 중요할 때 -> 연결 리스트 (Linked List)
• 삽입 및 삭제보다 조회가 중요할 때 -> 배열 (Array)

조회, 삽입, 삭제 모두에 높은 성능이 요구되는 상황에서는 어떤 자료구조를 써야 할까?
이런 경우 해시 테이블(Hash Table)을 고려해볼 수 있다. 해시 테이블은 삽입, 삭제, 그리고 조회 모든 연산에서 평균적으로 O(1)의 성능을 보인다.

h = Hash.new
h[:foo] = 17
h[:bar] = 34

puts h[:foo]  # 17
puts h[:bar]  # 34

h.delete(:foo)
puts h[:foo] # nil

장점이 있는 만큼 단점도 있다.

1. 메모리 사용량 증가
2. 코드 복잡도 증가
3. Hash 알고리즘에 기반하는 hash key 충돌 가능성
   • 나쁜 hash 알고리즘 -> 충돌 가능성 ⬆️
   • 좋은 hash 알고리즘 -> 충돌 가능성 ⬇️

위 단점들은 주로 해시테이블을 직접 구현할 때 문제가 된다. 하지만 대부분의 프로그래밍 언어는 이미 최적화된 해시테이블을 제공하기 때문에, 일반적인 사용 환경에서는 메모리 사용량을 제외하면 큰 단점으로 작용하지 않는다.

확장 🌱

• 좋은 hash 알고리즘이란?
• hash key가 충돌하는 경우의 해결책은?
  • 해결책에 따라 성능이 달라질까?
• 테이블 크기를 키우면 충돌 가능성이 낮아질까? 충돌을 피하기 위해 메모리 사용량을 늘리는 것이 좋은 선택일까?

관련 노트 📘

• 250511090805 - 배열이 조회 연산에 강점을 보이는 이유
• 250513050442 - 연결리스트의 경우 O(1)에 삽입 및 삭제가 가능하다