Hash Table
Hash Table은 중요한 자료구조이다.
유용하고 코드를 빠르게 만들어 줄 수 있다.
Hash Table은 Key Value System을 이용하여 자료를 정리한다.
Key Value System의 한 예시로는 사전을 들 수 있겠다.
Key = 단어를 찾고 Value = 해당 단어의 뜻과 설명으로 표현 할 수 있을 것 같다.
Array를 선형 탐색한다고 가정해 보면 걸리는 시간은 O(N)
Hash Table 에서 검색을 한다고 가정하면 걸리는 시간은 O(1) 상수 시간의 시간이 걸린다.
즉, Hash Table에서 값을 찾거나, 삽입하거나 삭제할 때도 마찬가지로 1개의 Step 만 필요로하다.
Hash Table에서 Key 랑 Value를 함께 저장하는 것 외에 Value 만 저장하여 빠르게 처리할 수 있는 방법도 있다.
예를 들어 음식이 Key값이 되고 Value는 True로 저장해놓으면 음식이 있는지 없는지 찾는데 1번의 스텝만 필요로 하면 된다.
Hash , Tables
해시 테이블 내에 Array 같은 구조 가 있다고 하는데 왜 Array 보다 빠른걸까? 살펴보자면, Hash Function 때문이다.
Hash Function은 여러분이 저장하고 싶은 Key를 숫자로 바꾸고 그 숫자가 index가 된다. 해당 index에 Value가 저장되고
예를 들어,
Hash Function 만든다고 가정하면
Pizza 는 5개의 알파벳이 있고, 5번째 배열에 pizza 가격을 저장한다고 하자.
Pizza -> Hash Function -> 5 -> list 5 = pizza price
Key를 가져다가 해시함수에 넣고 해시함수가 준 순자에 Value를 저장하면 된다.
Collision (해시 충돌) - 각기 다른 Key에 대하여 해시함수가 동일한 숫자를 준 경우 (4개의 단어를 가진 음식을 Hash Table에 저장한다고 가정 했을 때)
여러 대처방법이 있는데
1번째 방법은
같은 Key를 가진 공간에 또 다른 배열을 넣는 방법 거기에 2개의 쌍을 저장한다.
여기서 같은 Key에 이동하고 여기서 선형 탐색을 하기 때문에 항상 상수 시간은 아니다, 충돌이 있을 수 있고, 이러한 경우에 선형탐색을 해야하니까.
그래도 전반적인 평균 시나리오 중심으로 판단해야하고, 따라서 Hash Tables 의 시간 복잡도는 O(1)이 될것이다.
Hash Tables들은 수많은 프로그래밍 언어에 이미 깔려 있기 떄문에, 스스로 해시함수를 만들고 그럴 필요가 없다.
그래도 어떻게 작동하는지 작동원리를 알아두면 유용할 것 같다.