해시테이블

키와 값을 짝지어 모은 것

이를 통에 데이터를 쉽게 정리할 수 있게 해준다.

비유하자면 사전, 키는 단어, 값은 단어

 

카페 사장이고, 메뉴를 컴퓨터에 저장한다고 가정한다.

 

Menu = [

{name: "아메", price: 10 }

{name: "라떼", price: 12}

{name: "차", price: 15}

];

이 상태에서 라떼의 가격이 알고 싶을 때 라떼를 검색하기 때문에 빠르다. 해시테이블의 시간 복잡도는 O(1)

추가 삭제도 똑같음

 

해시테이블은 배열 형태, 속도의 비결은 해시 함수가 세트라서다.

해시 함수는 검색할 때 쓰는 키를 숫자, 즉 인덱스로 바꿔주는 역할을 한다. 검색어 입력 > 해시함수 > (인덱스) > 찾아줌

만약에 글자수가 같은 값을 반환하도록 되어있는데

피자와 치킨이 있다면? 해시충돌이 일어난다.

대처 방법 중 하나: 같은 인덱스에 또 다른 배열을 넣는다.

그래서 항상 1은 아닌데 암튼 빠름