📌해시 테이블이란?

• 키와 값을 짝지어 모은 것
• 데이터를 더 쉽게 정리할 수 있게 해준다.
• 해시 테이블은 사전에 비유 가능
  - 키 = 단어, 값 = 단어의 뜻

✏️예시

배열

menu = [
	{name: "아메리카노", price: 10}
	{name: "라떼", price: 12}
	{name: "카모마일차", price: 15}
	{name: "케이크", price: 45}
];

• 배열의 데이터를 처음부터 모두 확인하면서 "라떼"를 찾는다. (선형 검색)

해시테이블

menu = {
	커피: 10,
    리떼: 12,
    카모마일차: 15,
    케이크: 45
};

• 해시 테이블은 사전처럼 사용할 수 있어 모든 데이터를 다 찾는 게 아니라 "라떼"를 검색하면 된다.

📌배열 검색과 해시 테이블 검색의 시간 복잡도 차이

구분	시간복잡도
선형 검색	O(N)
해시 테이블	O(1)

• 해시 테이블에서는 어떤 값을 찾거나 추가, 삭제할 때 딱 한 단계만 거치기 때문에 효율이 엄청 좋다!

📌해시 함수

• 해시 테이블은 배열과 해시함수의 세트
• 해시 함수 : 검색할 때 쓰는 키를 숫자, 즉 인덱스로 바꿔 준다.
  
  

❗해시 충돌(hash collison)

• 글자 수를 그대로 인덱스로 반환하도록 구성했다고 생각했을 때
• 글자 수가 같은데 값이 서로 다른 상황을 해시 충돌이라고 한다.
• 이 때는 같은 인덱스에 또 다른 배열을 넣는다.
  ⇒ 해시 테이블에서 검색이 항상 O(1)은 아니다.