Hash Table 은 Key Value System 을 이용해서 자료를 정리한다.
Key Value System의 한 예시로는 사전이 있다.
단어를 찾고 = Key , 단어의 뜻과 설명 = Value
Hash Table과 Array를 비교해보자.
Ex) 레스토랑의 메뉴를 배열에 저장한다면,
menu = [
{ name : "coffee", price : 10 },
{ name : "burger", price : 15 },
{ name : "pizza", price : 30 },
{ name : "juice", price : 13 }
];
메뉴가 위처럼 있는데 피자의 가격을 알고 싶다면 Linear Search(선형검색)를 하면서 찾는다. 선형 검색은 각각 아이템을 첫번째부터 끝까지 체크하는 방법이다. 이 방법이 시간이 오래걸린다. 하나하나 찾기 싫을때 Hash Table을 쓰는것이다.
같은 메뉴지만 Hash Table로 정리한다면
menu = {
coffee : 10,
burger : 15,
pizza : 30,
juice : 13
};
피자의 가격을 알고싶다면 pizza가 key가 될것이고 Hash Tables는 가격을 value로 제공할것이다.
시간복잡도로 본다면 Array => O(N) , Hash Table => O(1) 이다. 고로 Array와 비교할때 Hash Table가 빠르다.