노개북 - 챕터 26~29

오늘 TIL 3줄 요약

• 스택 , 큐
• 해시 테이블
• 클린 코드

 

 

책에서 기억하고 싶은 내용을 써보세요.

해시 테이블은 키 와 값을 짝지어 모은것 : { key : value} 

해시 테이블을 통해 프로그램을 더 빠르게 만들 수 있는데, 그 원리는 카페 메뉴를 컴퓨터에 저장하는 예시를 통해 알아보았다.

 

메뉴판 = [

{이름 : '아메리카노' , 가격 : 4000원},

{이름 : '카페모카' , 가격 : 5000원},

{이름 : '라떼' , 가격 : 5000원},

{이름 : '녹차' , 가격 : 6000원},

]

위 와 같이 배열로 메뉴들의 정보를 저장하면, 메뉴 하나의 정보를 찾을 때 선형 검색을 해야 하므로, 검색 시간이 오래 걸린다. - 시간 복잡도 O(N)

 

하지만, 아래 와 같이 해시 테이블로 저장하면 더 빠르게 찾을 수 있다.

메뉴 = {
아메리카노 : 4000원,
라떼: 5000원,
카페모카: 5000원,
녹차: 6000원
}

 해시 테이블로 검색하면 어떤 값을 찾더라도 딱 한 단계만 거친다 . 데이터를 추가 , 삭제 할 때도 마찬가지이다. - 시간복잡도 O(1) 

 

배열과 마찬가지로 해시 테이블도 인덱스와 데이터 값이 같이 저장되는데,  해시 테이블 검색이 빠른 이유는 데이터를 저장할때, 해시 함수를 통해 저장되고 검색 되기 때문이다.

 

해시 함수는 값은 조건의 데이터 , 예를 들어 글자 수가 같으면 같은 인덱스에 저장하게 한다. 이런 경우 하나의 데이터를 찾을 때 인덱스가 중복되어 원하는 값과 함께 다른 값도 검색될 수 있지만, 해시 함수는 그 중복되는 인덱스를 다시 배열 형식으로 데이터값을 저장하여 선형 검색으로 찾게 한다. ( 이러한 이유로 시간 복잡도가 항상 O(1)은 아니지만, 일반적인 검색 시나리오 상은 같다고 본다.)

 

 

오늘 읽은 소감은? 떠오르는 생각을 가볍게 적어보세요

배열과 객체 (해시 테이블) 의 시간 복잡도를 통해 효율적인 데이터 저장 방식에 대해 생각해 보게 되었다.

 

 

궁금한 내용이 있거나, 잘 이해되지 않는 내용이 있다면 적어보세요.

API를 이용할 때 객체와 배열로 이루어져 있는데 , 어떤 방식이 어떤 상황에 잘 맞는 방식인지 궁금하다.

이 부분 REST API 공부와 함께 알아보아야겠다.